[M37] Consider one-way infinite binary sequences generated by a (p, 1 − p) Bernoulli process. Let Sn be as in Exercise 1.10.1.

(a) Show that for every  > 0, we have probability one that |pn−Sn| < n for all but finitely many n.

(b) Define the reduced number of successes S∗

n = (Sn −pn)/

np(1 − p).

Prove the much stronger statement than Item

(a) that with probability one, |S∗

n| < √

2a ln n (where a > 1) holds for all but finitely many n.

Comments. Item

(a) is a form of the strong law of large numbers due to F.P. Cantelli (1917) and G. P´olya (1921). Note that this statement is stronger than the weak law of large numbers. The latter says that Sn/n is likely to be near p, but does not say that Sn/n is bound to stay near p as n increases. The weak law allows that for infinitely many n, there is a k with n

(b) is due to A.N. Kolmogorov [Math. Ann., 101(1929), 126–135]. Source: [W. Feller, Ibid.].