• 1
• 2 rimaephosie
Topic Author
Posts: 59
Joined: May 21st, 2006, 7:40 pm

### a gambler's ruin problem

Here is a game from a gs interview:Two gamblers A and B have initially 7 £ and 13 £. Each time, they throw a coin: If stake, A give 1 £ to B, else B give 1 £ to A.The game is finish only if A or B is ruined (the time is infinite).What about the probability for A to win ? mhughes
Posts: 85
Joined: May 8th, 2006, 1:48 pm

### a gambler's ruin problem

7/20 cdmurray80
Posts: 64
Joined: November 30th, 2005, 3:28 am

### a gambler's ruin problem

Thats a random walk on a bridge right? e.g. a drunk man stands on position 7 of a bridge that has length 20, and takes one step left or right every turn. If he falls of the closer side A wins.I've seen this problem but I don't know an easy solution technique...maybe someone could point one out?The only solution technique I know is this: considering the gambling problem:Let P(1) be the chance for A to win when B has 1 dollarLet P(2) be the chance for A to win when B has 2 dollars...Let P(N) be the chance for A to win when B has N dollars, which is the total,so P(N) = 0Let P(0) is the chance for A to win when B has 0 dollars, which means A won, so P(0) = 1Then we can get N equations:P(0) = 1P(1) = 0.5*1 + 0.5*P(2)P(2) = 0.5( P(1) + P(3) )P(3) = 0.5( P(2) + P(4) )...P(N) = 0We could invert this matrix, but these equations always specify P(i) as the midpoint of P(i+1) and P(i-1), so solution is a line, with P(N)=0, P(0)=1, giving P(i) = (N-i)/(N)(OK, notation should have been better).That is, the chance for A to win when B has i dollars and there's a total of N dollar on the table is (N-i)/(N) = (20-13)/20 = 7/20Is there an easier way????(Sorry before I had 8/21 on the last line...that was from a bad calculation)
Last edited by cdmurray80 on October 30th, 2006, 11:00 pm, edited 1 time in total. MikeCrowe
Posts: 388
Joined: January 16th, 2006, 8:20 am

### a gambler's ruin problem

Suppose we double the stake every game. Does this make a difference? mhughes
Posts: 85
Joined: May 8th, 2006, 1:48 pm

The easy way is to observe that person A's fortune is a martingale. Thus if p is the probability that A wins, and X is his fortune at the game's end, on the one hand E(X) = 7 (since his fortune is a martingale), but on the other hand, E(X) = (1-p) * 0 + p * 20. Hence p = 7/20.8/21 doesn't really make any sense because due to the symmetry of the problem, you'd also get that the probability B wins is 14/21, but these probabilities don't sum to 1.For doubling the stakes each game, we need a bit of rules clarification. For example if A wins the first three coin tosses, then it's 14 - 6. Then the next bet should be $8, but B can't finance that amount, so what happens? Kamtsa Posts: 11 Joined: June 4th, 2006, 11:01 am ### a gambler's ruin problem Quotemhughes wrote:The easy way is to observe that person A's fortune is a martingale. Thus if p is the probability that A wins, and X is his fortune at the game's end, on the one hand E(X) = 7 (since his fortune is a martingale), but on the other hand, E(X) = (1-p) * 0 + p * 20. Hence p = 7/20. [...] The martingale solution is really elegant, would it be possible to generalize it to the 'unfair coin' (q != 0.5)and get the same closed form expression summing up of the recurrence-relation delivers?(Maybe something similar to transforming the probabilities in the expectations, which is done for the exponential BM in introductory finance books to get rid of the drift term?) amit7ul Posts: 571 Joined: December 7th, 2004, 8:36 am ### a gambler's ruin problem let A win$1 on head and p(head)=p>q=p(tail) then i think p_A/p_B=(7+p-q)/(13-p+q) shud hold which gives p_A=(7+p-q)/20please comment!thanks mhughes
Posts: 85
Joined: May 8th, 2006, 1:48 pm

### a gambler's ruin problem

Kamtsa: This is analagous to pricing a boundary option, which is definitely a nontrivial procedure if your process has drift. If you do come up with an analytic way to do it, I'd be interested to see it.amit7ul: Intuitively, this doesn't look right to me. Consider, e.g. the case when p = 1. amit7ul
Posts: 571
Joined: December 7th, 2004, 8:36 am

### a gambler's ruin problem

i realized it wrong, just after posting. any paper/links on boundary option. gentinex
Posts: 143
Joined: June 8th, 2006, 1:16 pm

### a gambler's ruin problem

I don't know anything about pricing boundary options, but the discrete version of the problem also has a martingale argument. If X_t is the net amount of money won by A by time t (so that X_0 = 0), then ((1-p)/p)^(X_t) is a martingale---check this for yourself! So you'll have that if f(x) = ((1-p)/p)^x, then f(13) * P(A wins) + f(-7) * P(B wins) = 0, and P(A wins) + P(B wins) = 1, from which you can find the probabilities of A or B winning.I know the function f(x) seems to come out of nowhere, but it makes more sense if you think about the problem the way that Kamtsa suggested: given a function g(x) which satisfies g(x) = p * g(x+1) + (1-p) * g(x-1) (i.e., you stipulate right from the start that you only want to look at martingales), with, say, g(0) = a and g(1) = b, what is g(x) for arbitrary x? If you pick a = 0 and b = 1, I think you'll get that g(x) is the sum of a bunch of powers of (1-p)/p, and there should also be some way to pick a and b so that you get f(x). amit7ul
Posts: 571
Joined: December 7th, 2004, 8:36 am

### a gambler's ruin problem

gentinex has hit the nail, thinking about the right martingale is crucial, rest is mechanical. mhughes
Posts: 85
Joined: May 8th, 2006, 1:48 pm

### a gambler's ruin problem

Nice, I like that gentinex. The only slight problem in there is that in fact f(13) * P(A wins) + f(-7) * P(B wins) = f(0) = 1. But yeah, that's a nice solution. gentinex
Posts: 143
Joined: June 8th, 2006, 1:16 pm

### a gambler's ruin problem

Maybe I'll use this opportunity to resurrect another question about this kind of random walk which I couldn't resolve before.Let's look back at the fair coin problem, so that p = q = 1/2. Now using a martingale argument (namely, the fact that X_t^2 - t is a martingale), we can deduce that the expected number of coin flips that it takes for the game to finish is given by 13*7 = 91 (or in general, a*b if A has fortune and B has fortune b to start off). This number, 91, is a weighted average of two things: the average amount of time it takes for A to win given that A wins (weighted by the probability of A winning), and the average amount of time that it takes for B to win given that B wins (weighted by the probability of B winning):91 = E(time for A to win given that A wins) * 7/20 + E(time for B to win given that B wins) * 13/20.So what are the exact values of these two conditional expected amounts of time, in terms of the numbers 13 and 7 (or in general, in terms of a and b)? Obviously, if we can solve for one of them, then the other one is straightforward to figure out. And also obviously, in the case that a = b, either expected amount of time equal a^2, by symmetry. But what about the non-symmetric case? boy
Posts: 101
Joined: May 30th, 2004, 10:44 pm

### a gambler's ruin problem

Last edited by boy on October 18th, 2006, 10:00 pm, edited 1 time in total. iwanttobelieve
Posts: 141
Joined: August 20th, 2006, 7:09 am

### a gambler's ruin problem

I agree with the martingale approach, but you have to use an optimal stopping theorem to be completely rigorous.- If the game doesn't stop, then it's obvious that the earnings of A is a martingale, but the game stops at a time T.- Here it works because: * the stopping time T is finite almost surely * and the martingale stopped at time T is bounded (and thus uniformly integrable).This problem has a continuous counterpart related to hitting time of a brownian motion, which is also a typical interview question.
Last edited by iwanttobelieve on October 28th, 2006, 10:00 pm, edited 1 time in total.  