1
$\begingroup$

Suppose we are flipping a coin with probability $p$ of coming up heads and $q$ of coming up tails. We start with $n$ dollars, and the game is over when we either lose all our money or win $m$ dollars. Each toss wins (if heads) or loses (if tails) $\$1.$ We play the game for $t$ turns (or until we hit one of the barriers). Question: what is our expected capital at the end of the game? Obviously, if $p>q,$ and $t\gg 1,$ we asymptote to $m+n,$ and if $t < \min(m, n),$ the expectation is simply $n+t(p-q).$ But in between it seems a bit less obvious.

$\endgroup$
2
  • 1
    $\begingroup$ This seems to be equivalent to finding the probability distribution of the first hitting time of $\{0,n+m\}$ (together with the hitting distribution). I do not think there is a closed-form expression for this. $\endgroup$ Nov 30, 2019 at 8:10
  • $\begingroup$ @MaxAlekseyev of course, yes. $\endgroup$
    – Igor Rivin
    Nov 30, 2019 at 18:53

3 Answers 3

2
$\begingroup$

Let $k:=m+n+1$, and consider $k\times k$ transfer matrix: $$M := \begin{bmatrix} 1 & q & 0 & 0 & \dots & 0 & 0 & 0\\ 0 & 0 & q & 0 & \dots & 0 & 0 & 0\\ 0 & p & 0 & q & \dots & 0 & 0 & 0\\ 0 & 0 & p & 0 & \ddots & 0 & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & \ddots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & \ddots & 0 & q & 0\\ 0 & 0 & 0 & 0 & \dots & p & 0 & 0\\ 0 & 0 & 0 & 0 & \dots & 0 & p & 1 \end{bmatrix}$$ Then the expected capital at the game end is $$[0,1,\dots,m+n]\cdot M^t\cdot e_{n+1},$$ where the $e_{n+1}$ is the unit column vector with the $(n+1)$-st component equal 1.

Matrix $M$ is tridiagonal and almost Toeplitz, and so it should be possible to get an explicit formula. For example, its characteristic polynomial can be expressed in terms of Lucas sequences as $(1-\lambda)^2 U_{k-1}(-\lambda,pq)$. Its eigenvalues are $1, 1$, and $2\sqrt{pq}\cos\frac{j\pi}{k-1}$ for $j=1,2,\dots,k-2$.

$\endgroup$
2
$\begingroup$

UPD. Formulae corrected.

Second approach, which follows the ideas from this answer to other question.

Consider the game as a random walk on the real line, starting at vertex $n$ and making steps +1 with probability $p$ and $-1$ with probability $q=1-p$. To answer the question, we need to find the probabilities of the following outcomes:

1) Path of length $\ell\leq t$ from $n$ to $n+m$, not visiting $0$ and not visiting $n+m$ except at the end.

2) Path of length $\ell\leq t$ from $n$ to $0$, not visiting $n+m$ and not visiting $0$ except at the end.

3) Path of length $t$ from $n$ to $k$, where $0<k<n+m$, not visiting $0$ or $n+m$.


1) First, we notice that the probability of a path of length $\ell-1<t$ from $n$ to $n+m-1$, not visiting $0$, equals

$$[x^{n+m-1}]\ x^n (px + qx^{-1})^{\ell-1} - [x^{-(n+m-1)}]\, x^n (px + qx^{-1})^{\ell-1}$$ $$=[x^0]\ (x^{-(m-1)}-x^{2n+m-1})(px + qx^{-1})^{\ell-1}$$

Second, the probability of a path of length $\ell-1<t$ from $n$ to $n+m-1$, not visiting $0$ and $n+m$, equals $$[x^0]\ (x^{-(m-1)}-x^{n+2m-1}-x^{-(m+1)}+x^{n+2m+1})(px + qx^{-1})^{\ell-1}$$

Finally, the probability of a path of length $\ell\leq t$ from $n$ to $n+m$, not visiting $0$ and not visiting $n+m$ except at the end, equals $$p\cdot [x^0]\ (x^{-(m-1)}-x^{n+2m-1}-x^{-(m+1)}+x^{n+2m+1})(px + qx^{-1})^{\ell-1}$$

For all these paths the capital at the end is $n+m$ and their contribution to the expectation is given by the sum over $\ell=1,\dots,t$, i.e., $$(n+m)p\ [x^0]\ (x^{-(m-1)}-x^{n+2m-1}-x^{-(m+1)}+x^{n+2m+1})\frac{1-(px + qx^{-1})^t}{1-(px + qx^{-1})}$$

2) The probability of such paths can be computed similarly, but their contribution to the capital expectation is zero.

3) Similarly, the probability of a path of length $t$ from $n$ to $k$, where $0<k<n+m$, not visiting $0$ or $n+m$, equals $$[x^0]\ (x^{n-k}-x^{n+k}-x^{n+k-2m}+x^{n+2m-k})(px + qx^{-1})^t.$$

Their contribution is given by \begin{split} [x^0]\ &\sum_{k=1}^{n+m-1} k(x^{n-k}-x^{n+k}-x^{n+k-2m}+x^{n+2m-k})(px + qx^{-1})^t \\ =[x^0]\ &\big(\frac{x^{n+1+2m}-x^{n+1-2m}-(x^{1+m}+x^{1-m})+(x^{1+2n+m}+x^{1+2n-m})}{(1-x)^2} \\ +& (n+m)\frac{x^{1+m}+x^{1-m}+x^{2n+m}+x^{2n-m}}{1-x}\big)(px + qx^{-1})^t. \end{split}

The expectation can now be computed routinely.

$\endgroup$
1
$\begingroup$

Call $X_k$ the amount of money at time $k$, $T_0:=\inf\{k,X_k=0\}$, $T_{n+m}:=\inf\{k,X_k=m+n\}$ and $T=T_{0}\wedge T_{n+m}$

First we have that $M_k:=X_k-(p-q)k$ is a martingale then (as already mentioned by Matheus) we have $$ n =\mathbb{E}(M_0)= \mathbb{E}(M_{k\wedge T})=\mathbb{E}(X_{k\wedge T})+(p-q)\mathbb{E}(k\wedge T). $$

Second we have that $N_k = \big(\frac{p}{q}\big)^{-X_k}$ is a martingale, then $$ \mathbb{P}(T_0<\infty)\leq \lim_{k\rightarrow \infty} \mathbb{E}(N_{k\wedge T_0}) = \mathbb{E}(N_{0})=\big(\frac{p}{q}\big)^{-n}$$ that decay exponentially with $n$. Therefore if $(p-q)\gg\frac{1}{n}$, I guess we can just forget about the $0$ boundary, and then $T=T_{n+m}$.

Third, for all $i\geq k$, $Y_i :=(T_{i+1}-T_i)$ are iid random variable with mean $\mathbb{E}(Y)=\frac{1}{p-q}$. And then by CLT $$\frac{T_{m+n}-m(p-q)^{-1}}{\sqrt{m}}=\frac{\sum_{i=n}^{n+m-1}(Y_i-(p-q)^{-1})}{\sqrt{m}}\rightarrow \mathcal{N}(0,\sigma^2) $$ as $m\rightarrow \infty$ with $\sigma^2$ the variance of $Y$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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