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)

  • 1
    $\begingroup$ Please explain what you call $P(X_j\mid X_i)$. $\endgroup$ – Did Jan 15 '15 at 6:55
  • $\begingroup$ @Did It is the transition probability from state $X_i$ to state $X_j$. $\endgroup$ – hengxin Jan 15 '15 at 7:05
  • $\begingroup$ 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? $\endgroup$ – Did Jan 15 '15 at 7:07
  • $\begingroup$ @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. $\endgroup$ – hengxin Jan 15 '15 at 7:16
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$.


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.