Suppose a particle starts at position 0 and at each time period particle $i$ moves one position to the right with probability $p_{i, j}$ or moves to the left with with probability $1-p_{i, j}$, where $j$ is the position of the particle before it moves. Let $X_{n, i}$ be the position of particle $i$ after $n$ moves. If $p_{2, j}\geq p_{1, j}$ for all $j$, show that $X_{n, 2}\geq_{st} X_{n, 1}$ for all $n$. Is this also always true under the same conditions, but allowing the second particle to initially start to the right of the first particle?
The goal is to find a coupling such that $(X_{n, 1}, X_{n, 2}) =_d (\hat{X}, \hat{Y})$ such that $\hat{X} \leq_{st} \hat{Y}$. If such a coupling exists then it would immediately follow that $X_{n, 1} \leq_{st} X_{n, 2}$. The difficulty for me comes from the fact that the probability of moving left/right is dependent on the position of the particle.
I have tried creating a coupling of the form $(X_{n, 1}, X_{n, 1} + \sum_{i=1}^n I_i)$ where \begin{equation*} I_i = \begin{cases} 2 & \text{ if } X_{i, 1} = X_{i-1,1}-1 \text{ and } X_{i, 2} = X_{i-1, 2} + 1\\ 0 & \text{ otherwise } \end{cases} \end{equation*} However, I believe this fails because I am not accounting for the case where particle 1 moves to the right while particle 2 moves to left. I think this also fails because I could do the same thing, but having the coupling depend on $X_{n, 2}$ rather than $X_{n, 1}$.
I have also tried some multiplicative indicators to find something similar in distribution, but I cannot seem to get the coupling. Is it possible to construct the coupling? If so, what is that coupling?
In words, I'll define the following coupling: at each time step, we find which of the two particles is more likely to move right. Then we first decide if it moves right or left. If the more likely particle moves left, the other is forced to move left. Otherwise, the less likely particle may move right, with the appropriate probability.
In notation, let $\hat{X}_0 = \hat{Y}_0 = 0$. At each $n$, let $\pi_n = \max(p_{1, \hat{X}_n}, p_{2, \hat{Y}_n}), \sigma_n = \min(p_{1, \hat{X}_n}, p_{2, \hat{Y}_n}) $, and let $U_n = \mathbf{1}\{p_{1,\hat{X}_n} \le p_{2, \hat{Y}_n}\}.$ Then draw two correlated bits $$ B_n \sim \mathrm{Bern}(\pi_n), C_n = \begin{cases} 0 & B_n = 0\\ \sim \mathrm{Bern}(\sigma_n/\pi_n) & B_n = 1\end{cases},$$ and set $$\hat{X}_{n+1} = \hat{X}_n + (1-U_n) (2B_n -1) + U_n(2C_n - 1) \\ \hat{Y}_{n+1} = \hat{Y}_n + U_n (2B_n -1) + (1-U_n)(2C_n - 1).$$
The key property we will need is that $$ \forall n, P(\hat{Y}_{n+1} \ge \hat{X}_{n+1}|\hat{Y}_n = \hat{X}_n) = 1.$$ To see this, note that if $\hat{Y}_n = \hat{X}_n,$ then $U_n = 1,$ i.e., the $Y$ particle is more likely to move right. Then by the dynamics we defined, if it moves left, the $X$ particle is forced to move left, meaning that $\hat{Y}_{n+1} < \hat{X}_{n+1}$ cannot occur.
Now, the first thing you need to check is that the marginal probabilities of the two processses match $X_{1,n}$ and $X_{2,n}$ from the question. I'll leave this to you.
To show the stochastic dominance, we will just prove that $P(\exists n : \hat{Y}_n < \hat{X}_n) = 0$. To see this, assume for the sake of contradiction that for some sample path, at some $n$, $\hat{X}_n > \hat{Y}_n$. Since steps are of length $1$, and since $\hat{X}_0 = \hat{Y}_0 = 0$, this means that there exists some $t < n$ such that $\hat{X}_t = \hat{Y}_t,$ and $\hat{X}_{t+1} > \hat{Y}_{t+1}$. But we already saw that $\hat{X}_t = \hat{Y}_t \implies \hat{Y}_{t+1} \ge \hat{X}_{t+1}$, yielding a contradiction.
The same reasoning works if $\hat{Y}_0 > \hat{X}_0$: again, since $\hat{X}$ starts behind $\hat{Y}$, if there is some time $n$ such that $\hat{X}_n > \hat{Y}_n,$ there is some time $t < n : \hat{X}_t = \hat{Y}_t$ and $\hat{X}_{t+1} > \hat{Y}_{t+1}$, which fails due to the same contradiction.