Proving that the mean number of times that a vector with $n$ $0$'s and $n$ $1$'s changes value is $n$.

Question

Let $n$ be a positive integer and $\Omega$ be the set of all $2n$-tuples of $n$ $0$'s and $n$ $1$'s. Clearly, $$|\Omega|=\frac{(2n)!}{(n!)^2}.$$ For each $x\in\Omega$, let $f(x)$ be the number of times $x$ changes from $0$ to $1$ or from $1$ to $0$. For example:

• $f(0,0,0,1,1,1)=1$,
• $f(0,1,0,1,1,0)=4$,
• $f(0,1,0,1,0,1)=5$,
• $f(0,0,1,1,0,1)=3$.

I want to find the mean of $f(x)$. That is, $$m(n):=\frac{1}{|\Omega|}\sum_{x\in\Omega}f(x).$$

After calculating $m(n)$ for $n=1,2,3$, I think it may be true that $m(n)=n$. However I don't know if it is true.

I had a couple of ideas which didn't solved the problem but may help someone here.

Since $x_i$ is different to $x_{i+1}$ if and only if $(x_i+x_{i+1}) \bmod{2}=1$, $$f(x)=\sum_{i=1}^{2n-1}(x_i+x_{i+1}) \bmod{2}.$$

I would apreciate any help.

Answer 1

For now, think of each $0$ and $1$ as being distinct. For each symbol $x$, there are $2n$ equally likely possibilities:

• $x$ occurs at the right end of the string.

• $x$ occurs just to the left of one of the $n-1$ other same symbols.

• $x$ occurs just to the left of one of the $n$ other opposite symbols.

This means that with probability $\frac{n}{2n}=\frac12$, $x$ will be the left symbol in a pair of opposite symbols. Since there are $2n$ symbols, and each has a probability of $\frac12$ of being the left element of an opposite pair, the expected number of opposing pairs is $2n\cdot \frac12=n$.

Answer 2

We can use the linearity of expectation. There are $2n-1$ spaces between the bits. The chance that a given space is between two different bits is $\frac n{2n-1}$ because whatever bit is to the left, there are $n$ opposite bits and $n-1$ similar bits for the right. We therefore expect $(2n-1)\cdot \frac n{2n-1}=n$ transitions.