# Couple/Compare two stochastic processes and prove an intuitive proposition

Consider a stochastic process (denoted $X$) $X_0, X_1, X_2, \ldots$ (not necessarily a Markov Chain) over state space $\{0, 1, \cdots, n \}$.

The transition probabilities are ($n$ is the sink state)

$$P(X_{i+1} = 1 \mid X_i = 0) = 1;$$ $$P(X_{i+1} = j+1 \mid X_i = j) > 0.5, \quad P(X_{i+1} = j-1 \mid X_i = j) < 0.5 \quad (1 \le j \le n-1).$$

Consider the following Markov Chain (denoted $Y$) $Y_0, Y_1, Y_2, \ldots$: $$Y_0 = X_0;$$ $$P(Y_{i+1} = 1 \mid Y_i = 0) = 1;$$ $$P(Y_{i+1} = j+1 \mid Y_i = j) = 0.5, \quad P(Y_{i+1} = j-1 \mid Y_i = j) = 0.5 \quad (1 \le j \le n-1).$$

It seems quite intuitive that

$P:$ The expected time to reach $n$ starting from any state is larger for $Y$ than for $X$.

In this sense, the process $Y$ can be regarded as a pessimistic version of $X$ because $X_i$ which increases at the next step with probability $> 0.5$ in $X$ now increases with probability exactly 0.5 in $Y$.

My question is

How to prove the intuitive proposition $P$?

I was hinted to use some techniques like coupling of Markov Chains. But I don't know how.

Note: The problem is adapted from "A Randomized Algorithm for 2-Satisfiability" in Section 7.1.1 of the book "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Eli Upfal et al. (2005)

• Please explain what you call $P(X_j\mid X_i)$. – Did Jan 15 '15 at 6:55
• @Did It is the transition probability from state $X_i$ to state $X_j$. – hengxin Jan 15 '15 at 7:05
• Hence this is a probability measure, not a number. What could "$\gt0.5$" mean in $P(X_{i-1} \mid X_i)\gt0.5$ then? – Did Jan 15 '15 at 7:07
• @Did From state $X_i$, the process can go to either state $X_{i+1}$ or state $X_{i-1}$. The (discrete) probability from $X_i$ to $X_{i-1}$ is a number (am I right?) and is larger than 0.5. Similarly, the probability from $X_i$ to $X_{i+1}$ is less than 0.5. Of course, they sum to 1. – hengxin Jan 15 '15 at 7:16
• Hmmm... This is most unclear. Are you considering some stochastic process $X$ on the state space $\{0,1,\ldots,n\}$ and writing $P(X_{i\pm1}\mid X_i)$ for $p(i\pm1\mid i)$? Then the next mystery is what could $p(i\pm1\mid i)$ mean if $X$ is not Markov. – Did Jan 15 '15 at 7:20

If we allow $k_i$ to represent the expected number of steps required to reach node $n$ from node $i$ we can summarize this problem with a system of equations. In general: $$k_i = 1 + \sum_{j\neq i}p_{i,j}k_j$$ So for this problem $$k_n = 0, k_0 = 1 + k_1$$$$k_i = 1 + (1-p_i)k_{i-1} + p_ik_{i+1}$$ where $i\in\{1,...,n-1\}$ and $p_i = p_{i,i+1}$. Notice that $k_0 = k_1+1$ and $$k_1 = 1 + (1-p_1)k_0 + p_1k_2 = 1 + (1-p_1)(1+k_1) + p_1k_2$$ $$\implies k_0 = k_1 + 1= \frac2{p_1} + k_2$$ So $k_0 > k_1 > k_2$. Further, if we assume that $k_{i-1} > k_i$ we can show that: $$k_i = 1 + (1-p_i)k_{i-1} + p_ik_{i+1}\implies k_i > 1 + (1-p_i)k_i + p_ik_{i+1}$$ $$\implies k_i > \frac1{p_i} + k_{i+1} > k_{i+1} \implies k_i - k_{i+1} > \frac1{p_i}$$
Now, consider $b_i$ which is similar to $k_i$ but $p_i = \frac12$ for all $i$. Then $b_i \geq 2 + b_{i+1}$
Because of this, and the fact that $b_n=k_n = 0$ $$b_0 - k_0 = \sum_{j=0}^{n-1}(b_j - b_{j+1}) + b_n - \sum_{j=0}^{n-1}(k_j - k_{j+1}) - k_n$$ $$b_0 - k_0 \geq 2(n) - \sum_{j=0}^{n-1}\frac{1}{p_i}> 2n - 2n = 0$$ So $b_0 > k_0$. In fact a similar argument can be made for all $b_i - k_i$.