14 BRANCHING PROCESSES events (27) Gk={lS-Snl≤2-kVn≥nk} occur only finitely many times,with probability one.For this,it is enough to prove that (28) >P(G)=E∑1Gs<o∞， k=1 k=1 because if the expectation is finite then the random count itself must be finite,with probability one.This is the Borel-Cantelli criterion for convergence of a random series. Proof of Theorem 9.Assume then that the random variables Sn are the partial sums(23)of independent random variables X;with means EX;=0 and variances EX?=o?such that the total variance2<.Then for everyk1there exists n<such that o≤8-k j=nk By the Maximal Inequality, P(G)=P{sup S-Snl≥2}≤8*/4-k=2k nznk Since<,the Borel-Cantelli criterion is satisfied,and so the sequence S is,almost surely,Cauchy,and therefore has a finite limit S.Exercise:If you know the basics of measure theory,prove that ES=0 and ES2=o2.Hint:First show that SS in L2,and conclude that the sequence S is uniformly integrable. ▣ 4.THE POLYA URN 4.1.Rules of the game.The Polya urn is the simplest stochastic model of self-reinforcing be- havior,in which repetition a particular act makes it more likely that the same act will be re- peated in the future.Suppose that every afternoon you visit a video-game arcade with two games:Ms.PAC-MAN and SPACE INVADERS.On the first day,not having played either game before,you choose one at random.With each play,you develop a bit more skill at the game you choose,and your preference for it increases,making it more likely that you will choose it next time:In particular,if after n visits you have played Ms.PAC-MAN Rn times and SPACE INVADERS Bn=n-Rn times,then on the(n+1)st day the chance that you decide to put your quarter in SPACE INVADERS iS 0n= Bn+1 n+2 It is natural to ask if after a while your relative preferences for the two games will begin to sta- bilize,and if so to what? It is traditional to re-formulate this model as an urn model.At each step,a ball is chosen at random from among the collection of all balls(each colored either RED or BLUE)in the urn,and is then replaced,together with a new ball of the same color.More formally:14 BRANCHING PROCESSES events (27) Gk := {|Snk −Sn | ≤ 2 −k ∀n ≥ nk } occur only finitely many times, with probability one. For this, it is enough to prove that (28) X∞ k=1 P (G c k ) = E X∞ k=1 1G c k <∞, because if the expectation is finite then the random count itself must be finite, with probability one. This is the Borel-Cantelli criterion for convergence of a random series. Proof of Theorem 9. Assume then that the random variables Sn are the partial sums (23) of independent random variables X j with means E X j = 0 and variances E X 2 j = σ 2 j such that the total variance σ2 = P j σ 2 j <∞. Then for every k ≥ 1 there exists nk <∞ such that X∞ j =nk σ 2 j ≤ 8 −k . By the Maximal Inequality, P (G c k ) = P { sup n≥nk |Sn −Snk | ≥ 2 −k } ≤ 8 −k /4 −k = 2 −k. Since P k 2 −k < ∞, the Borel-Cantelli criterion is satisfied, and so the sequence Sn is, almost surely, Cauchy, and therefore has a finite limit S. Exercise: If you know the basics of measure theory, prove that E S = 0 and E S2 = σ2 . Hint: First show that Sn → S in L 2 , and conclude that the sequence Sn is uniformly integrable. 4. THE POLYA URN 4.1. Rules of the game. The Polya urn is the simplest stochastic model of self-reinforcing be￾havior, in which repetition a particular act makes it more likely that the same act will be re￾peated in the future. Suppose that every afternoon you visit a video-game arcade with two games: MS. PAC-MAN and SPACE INVADERS. On the first day, not having played either game before, you choose one at random. With each play, you develop a bit more skill at the game you choose, and your preference for it increases, making it more likely that you will choose it next time: In particular, if after n visits you have played MS. PAC-MAN Rn times and SPACE INVADERS Bn = n − Rn times, then on the (n + 1)st day the chance that you decide to put your quarter in SPACE INVADERS is θn := Bn + 1 n + 2 . It is natural to ask if after a while your relative preferences for the two games will begin to sta￾bilize, and if so to what? It is traditional to re-formulate this model as an urn model. At each step, a ball is chosen at random from among the collection of all balls (each colored either RED or BLUE) in the urn, and is then replaced, together with a new ball of the same color. More formally: