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