1

Two gamblers, A and B, make a series of bets, where each has probability 1/2 of winning a bet, but A gets \$2 for each win and loses \$1 for each loss (a very favorable game for A!). Assume that the gamblers are allowed to borrow money, so they can and do gamble forever. Let $p_k$ be the probability that A, starting with \$k will ever reach \$0 for $k \geq 0$. (Probability by Blitzstein and Hwang Chapter 3 no. 46)

My attempt: I found that the recurrence relationship is $p_k = \frac{1}{2} p_{k+2} + \frac{1}{2} p_{k-1}$. This is because there is a $\frac{1}{2}$ chance we get to $p_k$ from $p_{k+2}$ and a $\frac{1}{2}$ chance we get to $p_k$ from $p_{k-1}$. Solving the characteristic equation $\lambda^3 - 2 \lambda + 1$ gives roots $\lambda = 1, \frac{-1 + \sqrt{5}}{2}, \frac{-1 - \sqrt{5}}{2}$. Extrapolating from what I know about solving recurrence relationships with characteristic equations which have two roots, I find $p_k = c_1 + c_2 \left( \frac{-1 + \sqrt{5}}{2} \right)^k + c_3 \left( \frac{-1 - \sqrt{5}}{2} \right)^k.$ I can get one equation for the coefficients with $p_0 = 1$, but I don't see any other obvious initial values. I suppose that perhaps I could use symmetry of $p_1 = p_{-1}$ and $p_2 = p_{-2}$, but before I make that ugly computation, does this approach look generally correct? Given that it is defined for $k \geq 0$, I feel like I'm doing something wrong if I'm having to use the imaginary $k < 0$ as a scaffolding for my computation.

Tarang Saluja
  • 391
  • 1
    Everything you've done is correct, but I don't think it's true that $p_1=p_{-1}$. – saulspatz Mar 04 '21 at 03:24
  • Oh shoot, I didn't think about the imbalance of $2 vs. $1. Thanks for noting that. Do you have suggestions on how to get three initial values? – Tarang Saluja Mar 04 '21 at 03:31
  • 1
    My guess would be $p_k=1$ if $k<0$. $p_{-1}$ is the probability that if we start at $-1$, there is some point when we are exactly $1$ ahead. Suppose for the moment that $p_{-1}$ really is $1$. Then so is $p_{-2}$, because the probability that we get from $-2$ to $-1$ is also $1$ and the probability that we get from there to $0$ is $1$. Now we have have to figure $p_1$. We want all solutions of $2W-L=1$ in non-negative integers $W,L$. The probability of this case is $$\binom{W+L}L2^{-W-L}$$ I haven't tried to compute this. If it isn't $1$, we could compute $p_1$ similarly. – saulspatz Mar 04 '21 at 03:39
  • 1
    My last comment overlooks the fact that we are only interested in the first time we get to $0$. The calculation described there would substantially overstate the probability. The sum would probably diverge to $\infty$. If we have $2$ wins and $3$ losses, for example, we should not count strings that start WL or LW. Instead of $10$ strings of $5$ games, we should only count $4$. This seems like it will get very complicated. There must be a better way. – saulspatz Mar 04 '21 at 04:03
  • I ended up finding a really ugly expression for it, but left it there without any simplification (Using what you said in your last comment). Thanks for the thoughts though. – Tarang Saluja Mar 13 '21 at 17:28
  • If you have a solution, you can answer your own question. I'd like to see it, unless it's so ugly that typing it is more trouble than it's worth. :-) – saulspatz Mar 13 '21 at 17:32

0 Answers0