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.
 A: First observation:


*

*$X_N(i)$ only depends on $X_1(i)$


So we denote by $A_n$ the probability that $X_N(i)=1$ given that $X_1(i)=0$. and we denote the probability that $X_N(i)=1$ given that $X_1(i)=1$ by $B_n$.
The probability that a vertex is picked in the $N$'th swap is $\frac{2}{n}$
From here we have:
$A_N = (A_{N-1})(\frac{n-2}{n}+\frac{2}{n}\times \frac{m-1}{n-1})+(1-A_{N-1})(\frac{2}{n}\times \frac{m}{n-1})$
The above formula is divided into two summands, depending on whether $P(X_{n-1})$ is $1$ or $0$.
Expanding the terms and adding this is equal to:
$A_{N-1}\frac{(n-1)(n-2)+2(m-1)-2m}{n(n-1)}+\frac{2m}{n(n-1)}=A_{N-1}\frac{(n-1)(n-2)-2}{n(n-1)}+\frac{2m}{n(n-1)}=A_N\frac{n^2-3n}{n(n-1)}+\frac{2m}{n(n-1)}=A_{n-1}\frac{n-3}{n-1}+\frac{2m}{n(n-1)}$.
It is not hard to prove that if $A_1=1$ then the recursion relation implies $A_n$ goes to $\frac{m}{n}$. (Notice $\frac{m}{n}$ is an equilibrium point and etcetera).
Second observation:
$mA_n(i)+(n-m)B_n(i)=m$ which implies $(n-m)B_n(i)=m(1-A_n(i))=\frac{m}{n-m}(1-A_n(i))$
Finally note that if $A_n=\frac{m}{n}$ then $B_n=\frac{m}{n}$.
By continuity of $f(x)=\frac{m}{n-m}(1-x)$ we are done.
Note: We have found a method to calculate the probabilities explicitly
A: 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$.
