Probability a bit in a bit string is 1 after swapping

Question

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.

Answer 1

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$.

Answer 2

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