11
$\begingroup$

In the "gambler's ruin" game, you start with 'n' dollars. You keep betting 1 dollar (on heads), on coin tosses. The coin is biased to come out heads with probability = p. A game ends when you have gotten N dollars, N>n, (you won the game) or you go broke ( you have $0 --you lost the game). Many sources derive the average length of a game, win OR lose . But, considering ONLY the WON games,-- what is the average length of a WON game? i.e. how many coin tosses happen, on the average, in the won games? Give the average number of tosses in a won game as a function of 'p' and 'N'.

$\endgroup$
  • 1
    $\begingroup$ This definitely does not deserve to be closed for context. $\endgroup$ – Eric Stucky Oct 26 '16 at 6:21
  • 1
    $\begingroup$ Possible duplicate of Proving a property of hitting times of a simple random walk on $\mathbb{Z}$ $\endgroup$ – Aaron Montgomery Apr 26 '18 at 0:23
  • 1
    $\begingroup$ @AaronMontgomery The item you refer to is not a duplicate of this problem. The result given there would only apply to the the case of unbiased coins where p is exactly .5 My question is for the general case of p being any value >0 and <1. $\endgroup$ – steve newman Apr 27 '18 at 5:24
  • $\begingroup$ Oh my -- yes, that's a rather embarrassing mistake on my part. Please accept my apology; I have retracted my vote to close this topic. (Also, now I have a fun problem to think about!) $\endgroup$ – Aaron Montgomery Apr 27 '18 at 13:57
4
$\begingroup$

The answer is $E_n = \frac{r+1}{r-1} (\frac{r^N+1}{r^N-1} N - \frac{r^n+1}{r^n-1} n)$ where $r = \frac{1-p}{p}$, except that $E_n = (N^2-n^2)/3$ at $r=1$.

Let:
$E_k$ be the expected length of the game starting at $k$ conditioned on winning the game
$F_K$ be the expected length of the game starting at $k$ (win or lose)
$v_k$ be the winning probability at point $k$
$w_k$ be the probability of moving up at point $k$ conditioned on winning the game

Also, note that $p = \frac{1}{r+1}$ and $\frac{r+1}{r-1}=\frac{1}{1-2p}$.

To compute $v_k$, we have $v_k = p v_{k+1} + (1-p) v_{k-1}$ with $v_0 = 0$ and $v_N = 1$.
Thus, $v_k = \frac{r^k-1}{r^N-1}$, except that at $r=1$, $v_k = k/N$.

(Note: One way of computing $v_k$ from the recurrence is that if we rescale the currency so that the difference between $k$ and $k+1$ is $r^k$, the resulting $v$ becomes linear (as a function of the rescaled currency), with $v = 0$ at 0 and $v=1$ at $1+r+...+r^{N-1} = \frac{r^N-1}{r-1}$.)

Key properties of $w_k$:
- $w_k = \frac {p v_{k+1}} {p v_{k+1} + (1-p) v_{k-1}} = \frac{r^{k+1}-1}{r^k-1} p$
- (when defined) $w_k$ is independent of $N$
- $w_k$ is identical for $p$ and $1-p$
- for large $k$ (and $p≠1/2$), $w_k≈\max(p,1-p)$.

A recurrence and some properties of $E$

We can compute E as follows:
$E_N=0$
$E_2-E_1 = -1$
$E_k = 1 + w_k E_{k+1} + (1-w_k) E_{k-1}$
After rearranging terms, we get a recursive formula for computing $E$:
$E_{k+1}-E_k = \frac{1-w_k}{w_k} (E_k-E_{k-1})-\frac{1}{w_k}$

If $p = 1/2$, then $w_k = \frac{k+1}{2k}$, and $E_n = (N^2-n^2)/3$, as noted in the link in Aaron Montgomery's comment on the question (or as computed by taking the limit $p→1/2$ of the general closed-form solution).

If $p ≠ 1/2$, we have a simple asymptotic approximation: $E_n = \frac{N-n}{|1-2p|} - O(r^{-n})$ (or $r^n$ for $r<1$).

The closed form of $E$

The recurrence for $E$ may look hopeless, but $E$ has a special symmetry: It does not change if $p$ is replaced with $1-p$ (equivalently, $r$ with $1/r$), which allows us to express $E$ in terms of $F$:
$F_n = v_n E_n + (1-v_n) E_{N-n}$
$F_{N-n} = (1-v_{N-n}) E_n + v_{N-n} E_{N-n}$

The recurrence for $F$ is
$F_k = 1 + p F_{k+1} + (1-p) F_{k-1}$ with $F(0) = F(N) = 0$.
Since the coefficients do not vary with $k$, we can solve this using standard techniques for solving recurrences (for example, see here):
$F_n = (n - v_n N) / (1-2p)$, except that $p=1/2$, $F_n = n(N-n)$.

After substituting and simplifying, we get the desired $E$.

$\endgroup$
  • $\begingroup$ +1 for digging out this interesting question and answering it! :-) $\endgroup$ – joriki Aug 3 '18 at 16:21
  • $\begingroup$ @Dmytro taranovsky Excellent job! Thank you. I solved this in a completely different way, using only elementary techniques. I wrote up my solution in LaTex and don't want to go through the labor of writing it again in MathJax, so I'll just provide the link to the pdf file with my solution.-- drive.google.com/file/d/1AN3_LD7tSN5ipZ6HAcXNpY7LE66M23e6/view. My solution also depends on the unexpected symmetry between p and (1-p).. $\endgroup$ – steve newman Aug 5 '18 at 5:14
  • $\begingroup$ For some reason the link to my file left out the https:// that precedes the link in the comment above. Add that by hand if you want to access the file. $\endgroup$ – steve newman Aug 5 '18 at 5:19
  • $\begingroup$ Does this mean that there is no lower boundary (i.e. the player is infinitely rich?) $\endgroup$ – Jinhua Wang Apr 15 at 23:11
  • $\begingroup$ @JinhuaWang The lower boundary is 0. Incidentally, if there were no lower boundary, the expected length conditioned on winning would still be finite unless $p=1/2$. $\endgroup$ – Dmytro Taranovsky Apr 16 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.