Show $S_N = \sum\limits_{n=1}^{N} \text{sign}(Y-X_n)$ is Markov, $(X_n),Y $ iid Uniform(0,1)

Question

Let $(X_n)$ and Y be i.i.d. Uniform$(0,1)$ random variables and let $$S_N = \sum\limits_{n=1}^{N} \text{sign}(Y-X_n)$$

Show that $S_n$ is a Markov Chain and find its transition probabilities.

Any help with this one?

Its clear that $\mathbb{P}(S_N = x\,\,\vert\,\, S_{n-1},...S_0) = \mathbb{P}([(S_N = x)\cap S_{N-1} = x-1]\cup[(S_N = x)\cap S_{N-1} = x+1]\,\,\vert\,\, S_{n-1},...S_0) = \mathbb{P}([(S_N = x)\cap S_{N-1} = x-1]\cup[(S_N = x)\cap S_{N-1} = x+1]\,\,\vert\,\, S_{N-1})$

How would you find the transitional probabilities?

Answer 1

Notice that $u=(S_n+n)/2$ is $Beta-Binomial(n,1,1)=U[0,n]$. Hence $$Y|S_n\sim Beta(1+\frac{n+S_n}2,1+\frac{n-S_n}2)=Beta(1+u,1+d)$$ with average $\hat y_n=\frac {1+u}{2+u+d}=\frac{1+u}{n+2}$ and hence $$S_{n+1}-S_n|S_n\sim B(P((Y|S_n)>X_{n+1}))= B(\hat y_n)$$ where $B(p)$ is Bernoulli on $\{-1,1\}$ with $P(B(p)=1)=p$.