- rimaephosie
**Posts:**59**Joined:**

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 ?

- cdmurray80
**Posts:**64**Joined:**

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.

Suppose we double the stake every game. Does this make a difference?

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?

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?)

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

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.

i realized it wrong, just after posting. any paper/links on boundary option.

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).

gentinex has hit the nail, thinking about the right martingale is crucial, rest is mechanical.

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.

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?

Last edited by boy on October 18th, 2006, 10:00 pm, edited 1 time in total.

- iwanttobelieve
**Posts:**141**Joined:**

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.

GZIP: On