I have some problems in solving this problem:
"Two independent walkers move on a discrete ring with N state (N odd) and periodic boundary conditions, with transition probability: $$P_{n\rightarrow n\pm 1}=\frac{1}{2}$$ 1)Show that for long $t$ the two walkers cross each other with probability 1.
2)At time $t=0$ the two walkers are in the same site (for example n=1), calculate the average time they are on the same site.
3)Generalize to the case where the two walkers are independent but with different transition probability, such as the two markov chains are irreducible and aperiodic and the invariant probabilities are constant $$p_{i}^{inv(1)} = p_{i}^{inv(2)} = \frac{1}{N}$$
4)Consider the case with $K \geq 3$ independent walkers
Can anyone help me? I think that for the firs question I have to calculate the invariant probabilities but I have no idea how to do it.
Let $\left\{X^{(k)}_n:n=0,1,\ldots\right\}$ be independent Markov chains on $S=\{0,1,\ldots,N-1\}$ with transition probabilities $$ p^{(k)}_{ij} = \begin{cases} p^{(k)},& j\equiv i+1\pmod N\\ 1-p^{(k)},& j\equiv i-1\pmod N. \end{cases} $$ These are irreducible and aperiodic (since $N$ is odd) Markov chains on a finite state space, and therefore each have a unique stationary distribution $\pi^{(k)}$. Due to symmetry, $\pi^{(k)}$ is the uniform distribution on $S$. Since $X^{(k)}_n$ is ergodic, for any $i,j\in S$ the hitting time $$ \tau_{ij}^{(k)} = \inf\{n>0: X^{(k)}_n = j\mid X^{(k)}_0=i\} $$ is finite with probability one, and so for any $i_1,i_2,j\in S$ the maximum $$ \tau_{i_1j}^{(1)}\vee \tau_{i_2j}^{(2)} $$ is also finite with probability one.
To compute the expected value of $$ \inf\left\{n>0: X^{(1)}_n = X^{(2)}_n \mid X^{(1)}_0 = X^{(2)}_0\right\}, $$ it may be easier to consider the process $\left(X^{(1)}_n, X^{(2)}_n\right)$ and compute its stationary distribution.