Consider two random walks that start from point $x=0$ and time $t=0$ and move either to right $x+1$ or left $x-1$:

1) Walker 1's first move is with equal probability to the right/left. However, any other move depends on the previous move: if he moves to the right in the $k$th step, he is more likely to move to the left in the $(k+1)$th step. Denote its location after the $n$th step by $X_n$.

2) Walker 2 is a symmetric random walker that in every step goes to either right or left with equal probability. Denote its location after the $n$th step by $Y_n$.

Prove that for all $m,n\geq 0$: $$\mathbb{P}\left(\max\limits_{1 \leq k \leq n}X_k\geq m\right) \leq \mathbb{P}\left(\max\limits_{1 \leq k \leq n}Y_k\geq m\right)\tag{1}$$

Intuitively, the Walker 1's location is more centered around the origin since everytime it moves to the right, it has a tendency to go to the left in the next step, but I found it hard to prove. I have verified it using simulation. I thought about induction:

Base case: Let $n=m$. Eq. (1) follows immediately since for $n=m$ means the Walkers have to make $m$ steps to the right, which is less likely for the Walker 1.

Now, assume (1) is true for $m,n$. We want to conclude (1) for $m,n+1$. Observe:

$$\mathbb{P}\left(\max\limits_{1 \leq k \leq n+1}X_k\geq m\right)= \mathbb{P}\left(\max\limits_{1 \leq i \leq n}X_n\geq m\right)\\+ \mathbb{P}\left(\left\{\max\limits_{1 \leq i \leq n}X_n\leq m-1\right\} \cap\{ X_{n-1}=m-1\} \cap \{X_{n-1}=m\} \right).$$

The first term on the right-hand side of above immediately is proved from (1), but the second term cannot be easily bounded. Any idea?


$\def\aseq{\stackrel{\mathrm{a.s.}}{=}}\def\peq{\mathrel{\phantom{=}}{}}$Too long for a comment.

It seems that this proposition is not necessarily true. The proposition can be restated as:

Given that $U_1, U_2, \cdots$ are random variables taking values in $\{-1, 1\}$ with\begin{gather*} P(U_1 = -1) = P(U_1 = 1) = \frac{1}{2},\\ P(U_{n + 1} = U_n \mid \mathscr{F}_n) = P(U_{n + 1} = U_n \mid U_n) \leqslant \frac{1}{2}, \end{gather*} where $\mathscr{F}_n = σ(U_1, \cdots, U_n)$, and $V_1, V_2, \cdots$ are i.i.d. with $P(V_1 = -1) = P(V_1 = 1) = \dfrac{1}{2}$. Define $X_n = \sum\limits_{k = 1}^n U_k$, $Y_n = \sum\limits_{k = 1}^n V_k$, then$$ P\left( \max_{1 \leqslant k \leqslant n} X_k \geqslant m \right) \leqslant P\left( \max_{1 \leqslant k \leqslant n} Y_k \geqslant m \right). \quad \forall n \geqslant 1,\ m \geqslant 0 $$

Equivalently, it claims that$$ P(X_1 < m, \cdots, X_n < m) \geqslant P(Y_1 < m, \cdots, Y_n < m). \quad \forall n \geqslant 1,\ m \geqslant 0 $$

Now, inductively construct $\{U_n\}_{n \geqslant 2}$ like this: Suppose that $U_1, \cdots, U_n$ are already constructed, then choose an event $A_n$ independent from $σ(U_1, \cdots, U_n)$ such that $P(A_n) = p_n \leqslant \dfrac{1}{2}$ and take $U_{n + 1} = U_n I_{A_n} - U_n I_{A_n^c}$. Such constructed $\{U_n\}$ satisfies$$ P(U_{n + 1} = U_n \mid \mathscr{F}_n) = P(U_{n + 1} = U_n \mid U_n) = P(A_n \mid U_n) \aseq p_n \leqslant \frac{1}{2}. $$

For $m = 0$, if $n = 2$ and $p_1 < \dfrac{1}{2}$, then$$ P(X_1 < 0, X_2 < 0) = P(U_1 = -1, U_2 = -1) = \frac{1}{2} p_1 < \frac{1}{4} = P(Y_1 < 0, Y_2 < 0). $$ For $m = 1$, if $n = 3$ and $(1 - p_1) p_2 > \dfrac{1}{4}$, then\begin{align*} &\peq P(X_1 < 1, X_2 < 1, X_3 < 1)\\ &= P(U_1 = -1, U_2 = 1, U_3 = -1) + P(U_1 = -1, U_2 = -1, U_3 = 1)\\ &\peq + P(U_1 = -1, U_2 = -1, U_3 = -1)\\ &= \frac{1}{2} (1 - p_1)(1 - p_2) + \frac{1}{2} p_1 (1 - p_2) + \frac{1}{2} p_1 p_2\\ &= \frac{1}{2} (1 - (1 - p_1) p_2) < \frac{3}{8} = P(Y_1 < 1, Y_2 < 1, Y_3 < 1). \end{align*} Thus it seems that the given proposition is not necessarily true in general.

  • $\begingroup$ Thank you for your comment/answer. Can you say what additional conditions are required to make it work? $\endgroup$ – Susan_Math123 Oct 23 '18 at 3:01
  • $\begingroup$ Thanks, sure, I will wait. I think $m\geq 2$. I have to check. $\endgroup$ – Susan_Math123 Oct 23 '18 at 3:15
  • $\begingroup$ @Susan_Math123 For $m=2$, if $n=4$ and $(1-p_1)p_2(1-p_3)<\dfrac18$, the claim is still false. $\endgroup$ – Saad Oct 23 '18 at 4:07
  • $\begingroup$ (1) this is a GREAT answer +1. (2) the $m=0$ case was never gonna be true anyway since $X$ has more of a tendency to return to $0$ than $Y$ does. (3) Alex's counterexamples for $m=1,2$ all rely on unequal $p_i$, because if $p_1 = p_2$ then $(1-p_1)p_2 \le 1/4$ with equality at $p_i = 1/2$, and similarly (I think?) for the $m=2$ case. So perhaps this conjecture is true if all $p_i$ are equal (i.e. "time invariance")? (4) Alternatively I wonder if the conjecture is true if we're talking about final position as opposed to maximum position? $\endgroup$ – antkam Oct 23 '18 at 13:05
  • $\begingroup$ @antkam Thanks for the comment. However, I have to mention that the $U_i$'s constructed above is only one possibility, and in general $P(U_{n+1}=1\mid U_n=1)=P(U_{n+1}=-1\mid U_n=-1)$ may not hold. $\endgroup$ – Saad Oct 23 '18 at 13:23

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.