What is the probability this Markov chain does not reach state $r$?

Question

Consider a random walk on the non-negative integers.

You start at $0$, and in each step you either move $1$ higher, or $2$ lower (but can't go below $0$). The direction is picked w.p. $1/2$ independently at any step.

From $0$ you can either stay at $0$, or go to $1$.

From $1$ you flip a coin and go either to $0$ or to $2$.

From $i>1$, you go to $i-2$ or to $i+1$.

• What is the probability that during $n$ steps, the process never reaches state $r$?

  If this does not have a simple form (as a function of $n,r$), can we derive an upper bound for it?

This seems to be solvable by a recurrence formula, but I couldn't reach an explicit expression.

Answer 1

As I mentioned in my comment, if $n>r$, then we can have atmost $r-1$ steps that move up. So the probability that after $n$ steps, we do not reach $r$ is,

$$P_{n,r} = \sum_{i=0}^{r-1} {n \choose i} {1 \over 2^{n}}$$

To include the constraint that we remain above 0, notice that if we move up $p$ times up, we have to move $q$ times down such that $p+q=n$ and $p-2q>=0$. Solving for minimum value of $p$, we get $p>={2n \over 3}$. This also puts a contraint that $r>=2n/3$. Adjusting the value of $i$ in our original eqution, we get

$$P_{n,r} = \sum_{i={2n \over 3}}^{r-1} {n \choose i} {1 \over 2^{n}}$$

Answer 2

Since it is a Markov process, these probabilities satisfy recursive equations. Namely, since in your case reaching $r$ is the same as reaching any number from $r$ till $\infty$ (upwards move are of size $1$), you solve a reachability problem for the interval $[r, +\infty)$. In general you have $V_0(x) = 1_A(x)$ and $$ V_{n+1}(x) = 1_A(x) + 1_{A^c}(x) \cdot PV_n(x) $$ where $1_A$ is an the indicator function of $A$ and $P$ is the stochastic matrix. So over $A$ the solution is obviously $1$ for all $n$, and we can simplify this for $x\notin A$: for those $$ V_{n+1}(x) = \sum_{y\notin A}p(x,y)V_n(y) + \sum_{y\in A^c}p(x,y) $$ here $p(x,y)$ is the probability of going from $x$ to $y$. In your case only two values are probable when departing from $x$, let's say $x^+$ and $x^-$, each with probability $\frac12$. So you get $$ V_{n+1}(x) = \frac12\left(V_n(x^-) + V_n(x^+)\right) $$ with the following boundary conditions: $V_0(x) = 1_A(x)$ and $V_n(x) = 1$ for all $x\in A$. That should be enough for you to carry on computations.

P.S. Just realized you look for the probability of not reaching $r$. In that case, you can compute what I have proposed and subtract it from $1$. Or, if you want to have a neater solution, just substitute $U_n := 1 - V_n$ in the equations above: you'll get an even simpler recurrent scheme.