<s>[INST] Probability a bit in a bit string is 1 after swapping Stuck on a homework question, so I could use all the help I could get.
Let $x = x(1), \dots , x(n)$ be a bit string containing exactly $m$ occurrences of 1. Consider the following operation on $x$: we choose a random pair of indices $(i,j),$ and we swap $x(i)$ and $x(j)$ so that $x'(i) = x(j),$ $x'(j) = x(i),$ while $x'(k) = x(k)$ if $k \neq i$ and $k \neq j.$ (If $i = j,$ therefore, then we change nothing.) Let $X_1 = x,$ and let $X_2, \dots, X_N$ be obtained by such a sequence of operations (always swapping a new random pair) that so $X_{r+1} = X_r$. The number of 1s remains $m$ in each iteration. Show for each $i$, we have $P(X_N (i) = 1) \rightarrow \frac{m}{n}$ as $N \rightarrow \infty$.
We're given this hint: Consider the last time $i$ was swapped. 
I've gathered that the probability that $i$ is swapped on any given iteration is $1-(1- \frac{1}{n})^2$. I've also figured out that the probability $i$ is 1 after a swap is $\frac{m}{n}$, as there are m choices for i to change to (including itself) after being selected for a swap, but I'm not sure how to apply this.
 [/INST] Let's start with this:
\begin{align*}
P(X_N(i)=1|X_{N-1}(i)=0) &= \frac{2m}{n^2}
\end{align*}
Because if $X_{N-1}(i)=0$, then we get $X_N(i)=1$ if the first index chosen is $i$ and the second index is one of the $m$ out of $n$ spots that have a $1$, or if the first index is one of the $m$ out of $n$ spots that have a $1$ and the second index chosen is $i$.
Then similarly, we can reason out $P(X_N(i)=1|X_{N-1}(i)=1)$ by saying that it is what happens when we do not {choose $i$ and one of the $n-m$ indexes that have $0$s, in either order}. That is:
\begin{align*}
P(X_N(i)=1|X_{N-1}(i)=1) &= 1 - \left( \frac{2(n-m)}{n^2} \right) \\
 &= \frac{n^2 - 2n + 2m}{n^2}
\end{align*}
Therefore:
\begin{align*}
P(X_N(i)=1) = \big(P(X_{N-1}(i)=1) \cdot (n^2 - 2n + 2m) + P(X_{N-1}(i)=0) \cdot 2m \big)/n^2
\end{align*}
But since $X_{N-1}$ can be only $0$ or $1$, $P(X_{N-1}(i)=0) + P(X_{N-1}(i)=1) = 1$, and:
\begin{align*}
P(X_N(i)=1) = \big(P(X_{N-1}(i)=1) \cdot (n^2 - 2n + 2m) + (1-P(X_{N-1}(i)=1)) \cdot 2m \big)/n^2
\end{align*}
Let's define $t_N$ as $P(X_N(i)=1)$, making this:
\begin{align*}
t_N &= \big(t_{N-1} \cdot (n^2 - 2n) + 2m \big)/n^2 \\
    &= t_{N-1} \left(1 - \frac{2}{n}\right) + \frac{2m}{n^2}
\end{align*}
It's now straightforward to show that $t_N$ converges to $\frac{m}{n}$:
Start by defining $s_N$ as $t_N - \frac{m}{n}$, so that $t_N = s_N + \frac{m}{n}$. Then we have:
\begin{align*}
s_N + \frac{m}{n} &= \left(s_{N-1} + \frac{m}{n}\right) \left(1 - \frac{2}{n}\right) + \frac{2m}{n^2} \\
s_N + \frac{m}{n} &= s_{N-1} \left(1 - \frac{2}{n}\right) + \frac{m}{n} - \frac{2m}{n^2} + \frac{2m}{n^2} \\
s_N &= s_{N-1} \left(1 - \frac{2}{n}\right)
\end{align*}
So obviously
$$
s_N = s_1 \left(1 - \frac{2}{n}\right)^{N-1}
$$
and
$$
\lim_{N \to \infty} s_N = 0
$$
which gives us what we want about $t_N$.
</s>