Coupling and random walks Let $(\xi_j)_{j\geq1}$ be independent variables with $P(\xi=1)=1-P(\xi=-1)=p_x$ and $(\mu_j)_{j\geq1}$ be independent variables with $P(\mu=1)=1-P(\mu=-1)=p_y$.
Define simple random walks $(X_n)_{n\geq 0}$ and $(Y_n)_{n\geq 0}$ on $\mathbb{Z}$ via $X_n=x+\sum_{j=1}^n \xi_j$ and $Y_n=x+\sum_{j=1}^n \mu_j$
I need to show that:
a) The random walk $(X_n)_{n\geq1}$ on $\mathbb{Z}$ forgets its initial state; so that $p_x=p_y$ and $y-x=2k$. Construct a coupling of $(X_n)_{n\geq 0}$ and $(Y_n)_{n\geq 0}$ for that matter.
b) The random walk $(X_n)_{n\geq1}$ monotonously depends on $p_x$; that is for $x\leq y$ and $p_x\leq p_y$ construct a monotone coupling of $(X_n)_{n\geq 0}$ and $(Y_n)_{n\geq 0}$, i.e. such that $P'(X'_n\leq Y'_n)=1$ for all $n\geq 0$.
Now I know that a) independent coupling and in b) monotone coupling is somehow meant... But I do not get how to get the coupling and find the solution to both.
 A: For part (a), you just want a standard coupling.  Run the processes independently until the first time $T$ where $X_T=Y_T$ and thereafter run them together.
You should be able to formalize this by defining a new process $\tilde Y_n$ in terms of increments $(\tilde\mu_j)$ which are in turn defined in terms of $(\mu_j)$, $(\xi_j)$, and $T$, and establishing that $(\tilde\mu_j)$ has the same distribution as $(\mu_j)$.  I assume this is a class assignment, so see examples from your class for a template showing how "formal" this coupling should look to make your professor happy.
Then, you need to establish that $T<\infty$ almost surely, and you're done.  If it helps, consider the process $Z_n=X_n-Y_n$.  This is random walk, too.  Think about its transition probabilities and why it might be recurrent, and how that recurrence might relate to $T$.
For part (b), think about defining a single step $\xi$ and $\mu$ for each process.  If these are defined as independent random variables, obviously any combination of values is possible.  However, can you think of way of defining $\xi$ and $\mu$ dependently (i.e., by means of a joint distribution) so that you always have $\xi \leq \mu$, while still maintaining the same marginal distributions?  If you had sequences of such dependent single steps, what would that mean for processes $X$ and $Y$ defined as sums of those steps?
