In the gamblers ruin problem of Section 451 let Mi denote th

In the gamblers ruin problem of Section 4.5.1, let Mi denote the expected number of games that must be played until the gambler either goes broke or reaches a fortune of N, given that he starts with i, i = 0, 1, . . . , N. Show that

In the gamblers ruin problem of Section 4.5.1, let Mi denote the expected number of games that must be played until the gambler either goes broke or reaches a fortune of N, given that he starts with i, i = 0, 1, . . . , N. Show that

Solution

Consider a game that gives a probability a of winning 1 dollar and a probability b = 1-a of losing 1 dollar. If a player begins with (say) 10 dollars, and intends to play the game repeatedly until he either goes broke or increases his holdings to N dollars, what is his probability of reaching his desired goal before going broke? This is commonly known as the Gambler\'s Ruin problem. For any given amount h of current holdings, the conditional probability of reaching N dollars before going broke is independent of how we acquired the h dollars, so there is a unique probability Pr{N|h} of reaching N on the condition that we currently hold h dollars. Of course, for any finite N we can immediately set Pr{N|0} = 0 and Pr{N|N} = 1. The problem is to determine the values of Pr{N|h} for h between 0 and N.

Suppose the player

Consider a game that gives a probability a of winning 1 dollar and a probability b = 1-a of losing 1 dollar. If a player begins with (say) 10 dollars, and intends to play the game repeatedly until he either goes broke or increases his holdings to N dollars, what is his probability of reaching his desired goal before going broke? This is commonly known as the Gambler\'s Ruin problem. For any given amount h of current holdings, the conditional probability of reaching N dollars before going broke is independent of how we acquired the h dollars, so there is a unique probability Pr{N|h} of reaching N on the condition that we currently hold h dollars. Of course, for any finite N we can immediately set Pr{N|0} = 0 and Pr{N|N} = 1. The problem is to determine the values of Pr{N|h} for h between 0 and N.

Suppose the player