Question about a random walk

Question

Let $(X_i)_i$ be a sequence of i.i.d. random variables such that $\Pr(X_i=1)=1-\Pr(X_i=-1)=p$, and assume that $p<1/2$. Define the random walk $S_i = \sum_{j=1}^iX_i$. Then, is it true to claim that for any even $n\geq4$, $$ \Pr\left(S_1>0,S_2>0,\ldots,S_{\frac{n}{2}}>0,S_{\frac{n}{2}+1}\leq0,\ldots,S_n\leq0\right)\leq \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \Pr\left(S_1\leq0,S_2\leq0,\ldots,S_{\frac{n}{2}-1}\leq0,S_{\frac{n}{2}}>0,S_{\frac{n}{2}+1}\leq0,\ldots,S_n\leq0\right) $$ The above means that the probability of the random walk being positive up to $i=n/2$ and then negative, is smaller than the probability that the walk is always negative except at $i=n/2$. Intuitively, this seems to be correct becasue $p<1/2$ and thus the walk is drifted to the negative. However, I am not sure how this property can be proven.

Answer 1

Let $n=2m$ be the given even number. So we need to understand $$ \begin{aligned} p_1 &=\Bbb P\left(\ S_0=0,\ S_1>0,\ S_2>0,\ \ldots,\ S_{m-1}>0,\ S_m>0,\ S_{m+1}\leq0,\ S_{m+2}\leq0,\ \ldots,\ S_n\leq0\ \right) \\ &=\Bbb P\left(\ S_0=0,\ S_1>0,\ S_2>0,\ \dots,\ S_{m-1}>0,\ S_m>0,\ S_{m+1}=0,\ S_{m+2}\leq0,\ \ldots,\ S_n\leq0\ \right) \\ &=\Bbb P\left(\ S_0=0,\ S_1>0,\ S_2>0,\ \dots,\ S_{m-1}>0,\ S_m>0,\ S_{m+1}=0\ \right) \\ &\qquad\qquad \cdot{\color{blue}{\Bbb P\left(\ T_{m+1}=0,\ T_{m+2}\leq0,\ \ldots,\ T_n\leq0\ \right)}} \\ &\qquad\text{ and} \\ p_2 &= \Bbb P \left(S_0=0,\ S_1\leq0,\ S_2\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}\leq0,\ S_{m}>0,\ S_{m+1}\leq0,\ \ldots,\ S_n\leq0\ \right) \\ &= \Bbb P \left(S_0=0,\ S_1\leq0,\ S_2\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}\leq0,\ S_{m}>0,\ S_{m+1}\leq0,\ \ldots,\ S_n\leq0\ \right) \\ &= \Bbb P \left(S_0=0,\ S_1\leq0,\ S_2\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}=0,\ S_{m}=1,\ S_{m+1}=0,\ \ldots,\ S_n\leq0\ \right) \\ &= \Bbb P \left(S_0=0,\ S_1\leq0,\ S_2\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}=0\ \right) \\ &\qquad\qquad \cdot\Bbb P\left(X_{m}=1\right) \cdot\Bbb P\left(X_{m+1}=-1\right) \\ &\qquad\qquad \cdot{\color{blue}{\Bbb P\left( T_{m+1}=0,\ T_{m+2}\leq 0,\ \ldots,\ T_n\leq0\ \right)}} \end{aligned} $$ Above, $T$ is "an other similar random walk" starting at time $m+1$.

So we (eliminate the blue factors, and) have to compare the simpler expressions: $$ \begin{aligned} p_1' &= \Bbb P\left(\ S_0=0,\ S_1>0,\ S_2>0,\ \dots,\ S_{m-1}>0,\ S_m>0,\ S_{m+1}=0\ \right) \\ &= \Bbb P\left(\ S_0=0,\ S_1=1,\ S_2\ge1,\ \dots,\ S_{m-1}\ge1,\ S_m=1,\ S_{m+1}=0\ \right) \\ &= \Bbb P\left(X_1=1\right) \Bbb P\left(\ U_1=1,\ U_2\ge1,\ \dots,\ U_{m-1}\ge1,\ U_m=1 \ \right) \Bbb P\left(X_{m+1}=-1\right) \\ &= \Bbb P\left(\ U_1=1,\ U_2\ge1,\ \dots,\ U_{m-1}\ge1,\ U_m=1 \ \right) \cdot pq \\ &= \Bbb P\left(\ U'_0=1,\ U'_1\ge1,\ \dots,\ U'_{m-2}\ge1,\ U'_{m-1}=1 \ \right) \cdot pq \\ &= \Bbb P\left(\ U''_0=0,\ U''_1\ge0,\ \dots,\ U''_{m-2}\ge0,\ U''_{m-1}=0 \ \right) \cdot pq \\ &\qquad\qquad\text{ and} \\ p_2' &= \Bbb P \left(\ S_0=0,\ S_1\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}=0\ \right)\cdot pq\ . \end{aligned} $$ Above, $U, U', U''$ are "similar random walks".

Now the things can be compared. For each "bridge" $U''$ as above from $0$ to $0$ never going into negatives we have the same number of up's and down's. We revert the time, and the values...

---

Later edit.

Let us compare the two probabilities $$ \begin{aligned} &\Bbb P\left(\ U''_0=0,\ U''_1\ge0,\ \dots,\ U''_{m-2}\ge0,\ U''_{m-1}=0 \ \right)\ , \\ & \Bbb P \left(\ S_0=0,\ S_1\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}=0\ \right) \end{aligned} $$ in detail. The $U''$ is given by some random walk based on a similar process $Y$, $U''_n=\sum_{k\le n} Y_k$, as it is the cases with the sum process $S$, based on $X$, i.e. $S_n=\sum_{k\le n} X_k$.

Note first that $m-1$ has to be even, else we cannot land in $0$ again after $m-1$ steps equal to $\pm 1$. I need one more letter, $m-1=2\mu$, say. Consider now all multiindices $a\in\{-1,+1\}^{\times2\mu}$ with $m-1=2\mu$ components. Among them, let $A$ be the subset of all multiindices $a$ such that: $$ \begin{aligned} &a_1&&\ge 0\ ,\\ &a_1+a_2&&\ge 0\ ,\\ &a_1+a_2+a_3&&\ge 0\ ,\\ \end{aligned} $$ and so on. We also impose the condition that the "last" inequality in the list, $a_1+a_2+\dots+a_{2\mu}\ge 0$ is in fact an equality. All these $a$ are building a set $A$. For each such $a$ consider the "word", the multiindex $a'$, obtained by reversing the order, so $a'_1=a_{2\mu}$, $a'_2=a_{2\mu-1}$, and so on. Then we have correspondingly: $$ \begin{aligned} &a'_1&&\le 0\ ,\\ &a'_1+a'_2&&\le 0\ ,\\ &a'_1+a'_2+a'_3&&\le 0\ ,\\ \end{aligned} $$ and so on. And finally: $$ \begin{aligned} &\ \Bbb P\left(\ U''_0=0,\ U''_1\ge0,\ \dots,\ U''_{m-2}\ge0,\ U''_{m-1}=0 \ \right) \\ =&\ \sum_{a\in A}\Bbb P(\ Y_1=a_1,\ Y_2=a_2,\ Y_3=a_3,\ \dots\ ) \\ =&\ \sum_{a\in A}p^\mu q^\mu \\ =&\ \sum_{a\in A}\Bbb P(\ X_1=a'_1,\ X_2=a'_2,\ X_3=a'_3,\ \dots\ ) \\ =&\ \Bbb P \left(\ S_0=0,\ S_1\leq0,\ \ldots,\ S_{m-2}\leq0,\ S_{m-1}=0\ \right)\ . \end{aligned} $$ So moreover the equality.