3 ms·
I think it is so (I seem to recall it and the example from Feller's book).
by pfortuny 1y ago
I think it is so (I seem to recall it and the example from Feller's book).
- madcaptenor 1y agoIt's definitely on the order of sqrt(N). But it's a bit smaller than sqrt(N) typically: (1) H is asymptotically normally distributed with mean N/2 and variance N/4 (central limit theorem) (2) So H - T = H - (N - H) = 2H - N is ~normally distributed with mean 0 and variance N, or st.dev. sigma = sqrt(N) (3) So |H-T| is "half-normal" (https://en.wikipedia.org/wiki/Half-normal_distribution https://en.wikipedia.org/wiki/Half-normal_distribution). This has mean sigma * sqrt(2/pi) or approximately 0.8 sqrt(N). This can be checked with a quick simulation. For example in R I run 1000 simulations with N = 10000 with the one-liner mean(abs(2*rbinom(1000, 10000, 0.5)-10000)) which returns 79.944. The mean square of H-T will be approximately N, though (basically we can ignore the absolute value when computing the variance). In fact, it's exactly N. H is Binomial(N, 1/2) which has variance N/4. H - T = 2H - N has variance N/4 * 2^2 = N, and mean 0, so its mean square is N.