Bounding survival probability of an asymmetric random walk by a symmetric one

Question

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?

Answer 1

$\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.