13: Consider the gambler's ruin problem as follows: The gambler starts with 5k. with probability a. the gambler wins $1, with probability 3) the gambler loses $1 and with probability (3 the round is declared a tie and the gambler neither wins nor loses. (You could also interpret that with probability c the gambler decides to sit out the round.) Note that a + b+ c : 1. The gambler stops on winning 71 2 k dollars or on reaching $0. Find the probability pk of winning. Intuitively sitting out some rounds should not change the probability of winning (assuming c k dollars or on reaching $0. Find the probability pk of winning before reaching $0: (a) lfthe gambler has $2' currently, condition on the first step (win or lose $1) to get an equation relating pi_1,pi,pi+1 and a,b then manipulate (using a + b : 1) to show that (p.41 p2-) : 3(1),; pi_1). (b) Use part (a) to show that (gm-+1 p1-) : (Sign. (c) Sum the expression in part (b) over i = 1, 2, . . . ,k 1 to get an expression for pk p0 2 pk 0 in terms of a sum of powers and p1, since the left side telescopes (terms cancel). Then use a basic formula to simplify the sum. Finally, using this formula when k = n and the fact that pm 2 1 determine p1 and hence all pk. 12 INTRODUCTION AND REVIEW Using the law of total probability in this way is called conditioning. Here, we nd the total probability of being colorblind by conditioning on sex. Example 1.9 In a standard deck of cards, the probability that the suit of a random card is hearts is 13/52 = 1/4. Assume that a standard deck has one card missing. A card is picked from the deck. Find the probability that it is a heart. Solution Assume that the missing card can be any of the 52 cards picked uniformly at random. LetM denote the event that the missing card is a heart, with the complement M5 the event that the missing card is not a heart. Let H denote the event that the card that is picked from the deck is a heart. By the law of total probability, P(H) = P(HlM)P(M) + P(H|M5)P(M') =(%)i+($)i=i The result can also be obtained by appealing to symmetry. Since all cards are equally likely, and all four suits are equally likely, the argument by symmetry gives that the desired probability is 1 / 4. l Example 1.10 (Gambler's ruin) The gambler's ruin problem was introduced in Example 1.6. A gambler starts with k dollars. On each play a fair coin is tossed and the gambler wins $1 if heads occurs, or loses $1 if tails occurs. The gambler stops when he reaches $n (n > k) or loses all his money. Find the probability that the gambler will eventually lose. Solution We make two observations, which are made more precise in later chapters. First, the gambler will eventually stop playing, either by reaching n or by reaching 0. One might argue that the gambler could play forever. However, it can be shown that that event occurs with probability 0. Second, assume that after, say, 100 wagers, the gambler's capital returns to $k. Then, the probability of eventually winning $n is the same as it was initially. The memoryless character of the process means that the probability of winning $n or losing all his money only depends on how much capital the gambler has, and not on how many previous wagers the gambler made. Let pk denote the probability of reaching n when the gambler's fortune is k. What is the gambler's status if heads is tossed? Their fortune increases to k + 1 and the probability of winning is the same as it would be if the gambler had started the game with k + 1. Similarly, if tails is tossed and the gambler's fortune decreases to k 1. Hence, Pk =Pk+1 () +Pk1 () , OI' pk+1pk=pk pk_1, for k=1,..,,nl, (1.2) CONDITIONAL PROBABILITY 13 with pa = 0 and p,1 = l. Unwinding the recurrence gives Pk _Pkl =Pk1 'Pk2 =Pk2 'Pk3 = \"=P1 'Po =P1, for k =1,...,n. We have that p2 p1 =p1, giving p2 = 2p1. Also, [)3 p2 =p3 21)] = p1, givingp3 = 3171. More generally, pk = kpl, for k =1,...,n. Sum Equation (1.2) over suitable k to obtain \"1 \"1 201k\" '1'!) = 20% 'Pk1)- k=1 k=1 Both sums telescope to Pu 'Pi = pnl 'POa which gives 1 pl =pn_1 = (n 1)p1, sop1 = l. Thus, k pk =kp1= ;,fork =0,...,n. The probability that the gambler eventually wins $n is k/ n. Hence, the probability of the gambler's ruin is (n k). l R : Simulating Gambler's Ruin The le gamblersruin.R contains the function gamble (k, n, p) , which sim- ulates the gambler's ruin process. At each wager, the gambler wins with prob- ability p, and loses with probability 1 p. The gambler's initial stake is $k. The function gamble returns 1, if the gambler is eventually ruined, or 0, if the gambler gains $n. In the simulation the function is called 1,000 times, creating a list of 1,000 ruins and wins, which are represented by Is and 0s. The mean of the list gives the proportion of 1s, which estimates the probability of eventual ruin. > k n p trials simlist mean(sim1ist) # Estimate of probability of ruin [1] 0.664 # Exact probability of ruin is 2/3 Sometimes, we need to nd a conditional probability of the form P(BIA), but what is given in the problem are reverse probabilities of the form P(AlB) and P(AlBC). Bayes' rule provides a method for inverting the conditional probability. The nal example is gambler's ruin. The limiting matrix encodes long term probabilities of absorption from various states. We then rearrange the matrix so transient states are rst to natch standard notation, extract the matrices Q corresponding to rows and columns of transient states and R corresponding to rows of transient states and columns of absorbing states. We compute (I Q)_1 and (I Q)_1R to see th eexpected steps to absorption and the absorption probabilities. A5