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...


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$ – Mathemagical Nov 22 '17 at 5:03

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.