Probability – How Gamblers Ruin Difference Equation Predicts Goals with p=1/2

markov chainsprobabilitysequences-and-series

I was reading about the gamblers ruin problem here, and they approach it with a difference equation.

The issue is that when I plug $p=\frac 1 2$, I get that the probability that the gambler will ever reach his goal becomes zero which is clearly not true.

Here is how I'm getting that:

The gambler starts with $a$ dollars and aims to get to $c$ dollars. He tosses a coin that has a probability $p$ of heads until he reaches either $c$ or $0$. The difference equation is given by:

$$s_c(a) = p s_c(a+1)+ (1-p)s_c(a-1)$$

Then, assuming $s_c(a) = z^n$ we get the characteristic polynomial:

$$pz^2-z+(1-p) = 0$$

We get the two solutions: $z = 1$, $z=\frac 1 p -1$.

So the general solution becomes:

$$s_c(a) = c_1 + c_2\left(\frac 1 p – 1\right)^a$$

Then we plug in the boundary conditions, one of which is $s_c(0)=0$.

Now here is where things get weird. If we plug $p =\frac 1 2$, the equation becomes:

$$s_c(a) = c_1$$

And since we know $s_c(0)=0$, this means $c_1 = 0$. So this implies that for $p=\frac 1 2$, $s_c(a)=0$. But this is obviously not true. What am I missing here?

Best Answer

What you are missing is that if $p=\frac{1}{2}$, then the two roots of the characteristic polynomial coincide. The general solution becomes $$s_c(n)=c_11^n + c_2n1^n=c_1+nc_2$$

Related Solutions

Probability – How to Get the Closed Form for the Race of the Wealthy Gamblers?

Let $a_t \triangleq \left( \frac{\begin{pmatrix} 2t+1 \\ t \end{pmatrix}}{2^{2t+1}} \right)^2 \frac{1}{t+2}$. We need $S_p \triangleq \sum\limits_{t=0}^p a_t$ in closed form.

First, note that $$\frac{a_{t+1}}{a_t} = \frac{t+2}{t+3} . \frac{1}{2^4} . \left( \frac{ \begin{pmatrix} 2t+3 \\ t+1 \end{pmatrix} }{ \begin{pmatrix} 2t+1 \\ t \end{pmatrix} } \right)^2 = \frac{t+2}{t+3} . \frac{1}{2^4} . \left( \frac{ (2t+3)(2t+2) }{ (t+1)(t+2) } \right)^2 = \frac{(t+3/2)^2}{(t+2)(t+3)} \tag 1$$

Using $(1)$ repeatedly starting with $a_0 = 1/8$, we get:

$$a_t = \frac{1}{8} . \frac{(3/2)^2}{2.3} . \frac{(5/2)^2}{3.4} \ldots \frac{(t+1/2)^2}{(t+1).(t+2)} \text{ for $t\geq 1$} \tag 2$$

Using $(2)$, we have

$$S_0 = a_0 = \frac{1}{8} = \frac{9}{8} - 1 = \bbox[yellow]{\frac{1}{8}.3^2 - 1}$$ $$S_1 = a_1 + a_0 = a_1 + S_0 = \frac{1}{8}.\frac{(3/2)^2}{2.3} + \frac{3^2}{8} - 1 $$ $$ = \bbox[yellow]{\frac{1}{8}.\frac{(3/2)^2}{2.3}. 5^2 -1}$$ $$S_2 = a_2 + S_1 = \frac{1}{8} . \frac{(3/2)^2}{2.3} . \frac{(5/2)^2}{3.4} + \frac{5^2}{8}.\frac{(3/2)^2}{2.3} -1 $$ $$= \bbox[yellow]{\frac{1}{8} . \frac{(3/2)^2}{2.3} . \frac{(5/2)^2}{3.4}. 7^2 - 1}$$ The general pattern we observe is (can be proved formally via induction) $$ \begin{align} S_p &= \frac{1}{8}. \frac{(3/2)^2}{2.3}. \frac{(5/2)^2}{3.4} \ldots \frac{((2p+1)/2)^2}{(p+1)(p+2)}.(2p+3)^2 -1 \\ &= \frac{1}{16}. \frac{(3/2)^2}{3^2}. \frac{(5/2)^2}{4^2} \ldots \frac{((2p+1)/2)^2}{(p+2)^2}.(2p+3)^2.(p+2) -1 \\ &= \frac{1}{2^{2p+4}}. \frac{3^2}{3^2}. \frac{5^2}{4^2} \ldots \frac{(2p+1)^2}{(p+2)^2}.(2p+3)^2.(p+2) -1 \\ &= \frac{p+2}{2^{2p+4}} \left[ \frac{3.5.7 \ldots (2p+1)(2p+3)}{2.3.4 \ldots (p+1)(p+2)}.2\right]^2 -1 \\ &= \frac{p+2}{2^{2p+4}} \left[ \frac{3.5.7 \ldots (2p+1)(2p+3)}{(p+2)!}.\frac{(p+1)! 2^{p+1}}{(p+1)! 2^{p+1}}.2\right]^2 -1 \\ &= \frac{p+2}{2^{2p+4}} \left[ \frac{(2p+3)!}{(p+2)!(p+1)!}.\frac{1}{ 2^{p}}\right]^2 -1 \\ &= \frac{p+2}{2^{4p+4}} \begin{pmatrix} 2p+3 \\ p+1 \end{pmatrix}^2 -1 \\ \end{align} $$ which is what we want.

Paths on a grid that don’t go below $0$ or above $l$ before reaching their target.

The problem can be solved in a similar way to the Bertrand's ballot problem.

Preliminarily we consider alternative reflections of the point $(0,0)$ in two lines $y=x+a$ and $y=x+b$. It can be easily shown that the $k$-th reflection has the coordinates: $$ (-1)^k\left(\left\lceil\frac k2\right\rceil a -\left\lfloor\frac k2\right\rfloor b,\left\lfloor\frac k2\right\rfloor b-\left\lceil\frac k2\right\rceil a\right),\tag1 $$ if the point is first reflected about $y=x+a$. If it is first reflected about $y=x+b$, $a$ and $b$ in (1) are to be interchanged.

Let us represent the toss sequence as a lattice path on the Cartesian plane as follows:

Start the path at $(0, 0)$.
Each head is a move right 1 unit.
Each tail is a move up 1 unit.

Our aim is to hit the point $(p,q)=(t+l,t)$ never crossing the lines $y=x$ and $y=x-l$. The overall number of paths is $\binom{2t+l}t$ which should be decreased by the number of paths which cross at least once the above mentioned lines.

To compute the number of the 'bad' paths we proceed very similar to the procedure described in the link given in the beginning of the answer. The end point of every path crossing the line $y=x$ from below lies on the line $y=x+1$, and the end point of every path crossing the line $y=x-l$ from above lies on the line $y=x-l-1$.

For each 'bad' path $P$, define a new path $P′$ by reflecting the part of $P$ up to the first point it touches the line across it. $P′$ is a path from $(−1, 1)$ to $(p, q)$ if we touch the line $y=x+1$ or from $(l+1,-l-1)$ to $(p, q)$ if we touch the line $y=x-l-1$ (cf. (1) with $k=1,a=1,b=-l-1$).

This is however not yet the end of story, since there can exist the paths which cross both $y=x+1$ and $y=x-l-1$. By the above counting each such path will be count as 'bad' twice. So we need to add number of such paths, which can be computed as follows. Assume a path $P'$ with already reflected initial part (about the boundary line it meets first) crosses the other boundary line. Define a new path $P''$ by reflecting the part of $P'$ up to the first point it touches the second boundary line across the line. The initial point of all such paths (which cross both boundary lines in the same order) will be reflection of the point $(0,0)$ first about the first line and then about the second one. Observe that the initial point is again $2t+l$ steps apart from the final point $(p,q)$. This process of reflecting can be repeated for the longer paths which repeatedly cross the upper and lower boundary lines in alternating order.

Substituting in (1) $a=1,b=-l-1$ one obtains that the $y$-coordinate of the $k$-th reflection of the point $(0,0)$ is $$ \begin{cases} -(-1)^k\left\{k+\left\lfloor\frac k2\right\rfloor l\right\},& \text{if the first reflection is across }y=x+1\\ \hphantom{-}(-1)^{k}\left\{k+\left\lceil\frac k2\right\rceil l\right\},& \text{if the first reflection is across }y=x-l-1 \end{cases}. $$

With this at hand the final expression for the number of ways for reaching the final point without crossing the boundary lines reads: $$ \binom{2t+l}t+\sum_{k\ge1}(-1)^k \left[\binom{2t+l}{t+(-1)^k\left\{k+\left\lfloor\frac k2\right\rfloor l\right\}} +\binom{2t+l}{t-(-1)^k\left\{k+\left\lceil\frac k2\right\rceil l\right\}} \right]. $$

Best Answer

Related Solutions

Probability – How to Get the Closed Form for the Race of the Wealthy Gamblers?

Paths on a grid that don’t go below $0$ or above $l$ before reaching their target.

Related Question