In the gambler's ruin model, $X_n$ is a gambling player's fortune after the $n^{th}$ game, when making 1 dollar bets at each game.

Also, for fixed $0<p<1$, we can find random variables $\{Z_i\}$ which are i.i.d. with $P(Z_i=1)=p$ and $P(Z_i=-1)=1-p$. So, we can set $$X_n=a+Z_1+Z_2+...Z_n$$ with $X_0 = a$.

Suppose that $0<a<c$, and let $\tau_0=\inf\{n\ge0:X_n=0\}$ and $\tau_c=\inf\{n\ge0:X_n=c\}$ be the first hitting time of $0$ and $c$, respectively.

The Question is,

For the gambler's ruin model mentioned above, let $\beta_n=P(min(\tau_0,\tau_c)>n)$ be the probability that the player's fortue has not hit $0$ or $c$ by time $n$.

(a) Find any explicit, simple expression $\gamma_n$ such that $\beta_n<\gamma_n$ for all $n \in N$, and such that $\lim_{n \to \infty}\gamma_n=0$.

(b) Also, find any explicit, simple expression $\alpha_n$ such that $\beta_n>\alpha_n>0$ for all $n \in N$.

I have no idea where to start to find $\gamma_n$ which is greater than $\beta_n$ for all $n$.

For (b), I thought about $\alpha_n=P(\tau_0>n)$, the probability that player's fortune is not hitting $0$ by time $n$. But I'm not sure how to show $\beta_n>\alpha_n>0$ for all $n \in N$.

Thanks for any help...


1 Answer 1


To get an upper bound, note that if the gambler hasn't hit the boundary by time $n$, then he hasn't had a win or loss streak of length $c$. The latter event is contained in the event that none of the sequences $(Z_1, \ldots, Z_c), (Z_{c+1}, \ldots, Z_{2c}), \ldots, (Z_{(m-1)c+1}, \ldots, Z_{mc})$ are the identically $+1$ or $-1$ sequence, where $m = \lfloor \frac{n}{c} \rfloor$. Excluding just these sequences is enough, and it makes the analysis easier.

The probability that a given sequence of $Z_i$'s of length $c$ is not all $+1$'s or all $-1$'s is $1-p^c-(1-p)^c.$ Thus

$\beta_n < (1-p^c-(1-p)^c)^{\lfloor \frac{n}{c} \rfloor} = \gamma_n$,

and $\gamma_n \to 0$ (exponentially quickly!) as $n \to \infty$. (Is this simple enough?)

Getting a positive lower bound is easy: just choose any sequence of wins and losses of length $n$ that doesn't hit the boundary! For example, if the gambler repeatedly wins, then loses, then wins, etc., he will never hit the boundary (as long as $c > 2$). This event has probability

$\mathbb{P}(Z_i = (-1)^i, 1 \leq i \leq n) \geq p^{n/2}(1-p)^{n/2}. $

So $\beta_n > (p(1-p))^{n/2} = \alpha_n$ works.

As an aside: the distribution of your two-sided hitting time $\min\{\tau_c, \tau_0\}$ can be computed exactly, using the optional stopping theorem with some clever martingales. (I can't find a good reference right now, but the method you need to do this is standard.)

  • $\begingroup$ Nice. I knew the upper bound (a somewhat standard result) but was flummoxed with the lower bound. I like the interpretation here as the measure of a set of trajectories that keep going past time n. You have found a superset and a subset of that set to create your bounds. Show some upvoting love for this answer, people. $\endgroup$ Nov 22, 2017 at 5:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .