Bit swapping probability question

88 Views Asked by At

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

What's confusing me is that it seems as though the probability on any iteration of $X_j$ that $X_j(i) = 1$ is always $\frac{m}{n}$, which would make the problem trivial.

1

There are 1 best solutions below

0
On

It is clear that given any $1\leq i \leq n$, there exists a steady equilibrium state, with equilibrium probability $P(X_{i}=1,t)=\frac{m}{n}, P(X_{i}=0,t)=1-\frac{m}{n}$ for all time $t\in \mathbb{Z^{+}}$, t>T for some $T$.

At time $t+1$, we have

$P(X_{i}=1,t+1)=P(X_{i}=1,t)(P(\text{switch $i$ with another filled site}))+P(X_{i}=1,t)(P(\text{site $i$ is left untouched at the 't+1'th time}))+P(X_{i}=0,t)(P(\text{switch $i$ with a filled site}))$

Thus, $P(X_{i}=1,t+1)=(\frac{m}{n})\frac{m-1}{{n}\choose{2}}+(\frac{m}{n})\frac{{n-1}\choose{2}}{{n}\choose{2}}+(1-\frac{m}{n})\frac{m}{{n}\choose{2}}=\frac{m}{n}$. A similar calculation shows that $P(X_{i}=0,t+1)=(1-\frac{m}{n})$; i.e the probabilites add up to $1$, at time $t+1$.

It seems the system is such that given any initial configuration, you may be able to get to this equilibrium state; but I've not worked that out explicitly.