Alice and Bob play the following game. Both players start with a pile of n chips. On

Chapter 32, Problem 32.33

(choose chapter or problem)

Alice and Bob play the following game. Both players start with a pile of n chips. On each turn, they flip a coin. With probability p, Alice wins the toss and Bob gives her a chip; conversely, with probability 1 p, Bob wins the toss and Alice gives him a chip. The game is over when one player (the winner) has all 2n chips. What is the probability that Alice wins this game? To help you work this out, please do the following: a. Let ak denote the probability that Alice wins the game when she has k chips and Bob has 2n k. What are the values of a0 and a2n? b. Find an expression for ak in terms of ak1 and akC1. This expression is valid when 0 < k < 2n. c. Using the techniques of Section 23, solve the recurrence relation from part (b) usingthe boundary conditions you deduced in part (a).(If you have not studied Section 23, please see the hints in Appendix A.)d. Your answer to part (c) should be a formula for ak. Substitute k D n into thatformula to find the probability that Alice wins.In expressing your answers to (b), (c), and (d), it is useful to let q D 1p.