From: ikastan@alumni.caltech.edu (Ilias Kastanas) Newsgroups: sci.math Subject: Re: law of large numbers question Date: 1 Nov 1997 17:46:56 GMT In article <345A6BF3.1676@telerama.com>, Richard J. Tony wrote: >Hi all, I understand the law of large numbers as follows (in the 'flip a coin' >context): If one flips a fair coin enough then the long run behavior is that the Let the m-th flip be X_m = 1 (heads) or -1 (tails), and S_n = sum of X_1,... X_n. Then your absolute error is S_n /2. >percentage of heads will approach 50% (as a limit) but the absolute error gets large >(positively or negatively), where absolute error= actual number of heads flipped - total >number of flips/2. My question is this: Will the absolute error = 0 infinitely many >times (oscillation around the 'expected numbers') or after some (possibly very large) >number of tosses will the absolute error never come back to 0? In essence, is it >necessarily true that if heads is "behind" then if one flips enough it will eventually >"catch up" so that the error =0? My first feeling was that the error eventually goes to >infinity and never comes back to 0, but, as with so many probability questions, I don't >feel to sure about it. Is there a theorem out there (by Bernoulli perhaps) that answers >this? Thanks, Rick If S_n can go to +inf, it can equally well go to -inf... since the random walk is symmetric! There is a theorem, the Hewitt-Savage 0-1 Law, implying that for random walks on R there are four possibilities, and for each walk one of the four happens with probability 1. First, S_n = 0 for all n; not so, here. Second, S_n -> +inf; no, by symmetry. Third, S_n -> -inf; likewise. (They would obtain if the coin were unfair). So the fourth one is the case: lim_sup S_n = +inf, lim_inf S_n = -inf. This means: with probability 1, S_n assumes every single integer value... each one of them infinitely many times. Yes, it is 0 infinitely often, and same for +1000000 or -1000000000. You can consider the probability of one-sidedness, p(S_n <= 0 for all n = 1, 2, ..., k); it behaves like C / sqrt(k) for large k. C is sqrt(2/pi), I think. Now suppose that for n = 1, 2, ... 2k the last time we had S_n = 0 was for n = 2m; so the ratio L_2k = 2m/2k is between 0 and 1 (note: 1 - L_2k is the fraction of time since S_n last was = 0). For large k, the probability p(a <= L_2k <= b) -> the integral (from a to b) of 1/pi * sqrt(x(1-x)) dx ... the "arcsine law". By the shape of the integrand, L_2k is much more likely to have an extreme value, close to 0 or to 1, rather than 1/2 or so. And by its symm- etry, p(L_2k <= 1/2) -> 1/2. So if you flip a coin 1000 times there is a 50% probability that either you or your opponent will be continuously ahead throughout the second half of the game, from flip 501 to flip 1000! Ilias