Puzzle: binary number shrinkage on operation

Question

Given a random binary number with n digits. Define operation P: count number of ones, suppose there are k ones in this binary number, then flip k-th digit(1 to 0, 0 to 1) counting from left(or right, it does not make a difference). Repeat P until all digits are turned into 0. For example, b'101' has 2 ones, flip 2nd digit, we get b'111';follow same operation, b'110', b'100', b'000', end. 101->111->110->100->000, 4 steps.

1. Are steps finite for all binary number? Prove it.
2. For n digit random binary number, calculate expectation of steps.

I have test n=2,3,4 and they all fall into all zeros.

For any step, it will change 1->0 or 0->1. If steps are infinite, it means there will be a fixed point or loop for operation P, which does not exist except all zeros(need proof here). All zeros is a absorption state, all other state is unstable. Can anyone give a rigorous proof?

n=1, 0; 1->0. $E_1=(0+1)/2=0.5$

n=2, 00; 10->00; 01->11->10->00; 11->10->00. $E_2 = (0+1+3+2)/4=1.5$

n=3, 000; 100->000; 010->110->100->000; 011->001->101->111->110->100-> 000. $E_3 = (0+1+3+5+2+4+6+3)/8=3$

@JimmyK4542 does a simulation, the answer holds unitl 20,maybe prove by induction? $$E_n = n(n+1)/4$$

Answer 1

Take a sequence of binary digits $\mathfrak{a}=a_0a_1\ldots a_{n-1}1$ ending in $1$. Associate to it a complementary sequence (I've made up that term) $\mathfrak{a}^c=\overline{a_{n-1}}\,\overline{a_{n-2}}\ldots\overline{a_1}\,\overline{a_0}$ ($1$ at the end dropped, each digit complemented, order reversed).

Let $f$ be our transformation as described in the question. We need to note that the following is true:

Lemma: If $\mathfrak{a}$ is not all "ones", i.e. $\mathfrak{a}\ne 111\ldots 1$, i.e. $\mathfrak{a}^c\ne 000\ldots0$, then:

$$f(\mathfrak{a}^c)=f(\mathfrak{a})^c$$

Proof: If $\mathfrak{a}$ has $k<n$ ones, then $\mathfrak{a}^c$ has $k-1$ zeros, i.e. $(n-1)-(k-1)=n-k$ ones. $f$ will "flip" the bit $k$ in $\mathfrak{a}$, so $f(\mathfrak{a})=a_0\ldots\overline{a_k}\ldots a_{n-1}1$. Thus, $f(\mathfrak{a})^c=\overline{a_{n-1}}\ldots a_k\ldots\overline{a_0}$, where the bit $a_k$ is preserved, at the position $n-k$. It is easy to see that we get the same result by flipping $n-k$'th bit in $\mathfrak{a}^c$, i.e. this is equal to $f(\mathfrak{a}^c)$. $\quad\blacksquare$

Now, this means also that $f^i(\mathfrak{a}^c)=f^i(\mathfrak{a})^c$ for $i=1,2,\ldots$ - as long as $\mathfrak{a}$ does not have "all ones".

Let's also call an "order" of the sequence $\mathfrak{a}$ (and use the symbol $o(\mathfrak{a})$) the smallest number $i$ such that $f^{i}(\mathfrak{a})=000\ldots 0$. So far, we have not proven that every sequence has an order. This will be proven in the next theorem:

Theorem: Every sequence $\mathfrak{a}$ has an order. If the sequence is of length $n$, then $o(\mathfrak{a})\le \frac{n(n+1)}{2}$.

Proof: Induction on $n$. For $n=1$ the statement is trivial (the order is at most $1$). Presume the theorem is valid for sequences of length $n-1$, and let's prove it is valid for a sequence $\mathfrak{a}$ of length $n$.

• If $\mathfrak{a}=a_0a_1\ldots{a_n}$ ends with $0$, it is easy to see that the last $0$ does not "participate" in $f$. In other words, $o(\mathfrak{a})=o(a_0a_1\ldots a_{n-1})\le\frac{(n-1)n}{2}\le\frac{n(n+1)}{2}$.
• If, however, $\mathfrak{a}$ ends in $1$, let $i=o(\mathfrak{a}^c)$ - the order of the complementary sequence. Now, in $i$ iterations we have $f^i(\mathfrak{a}^c)=000\ldots 0$ and $i\le\frac{(n-1)n}{2}$ as per inductive hypothesis. This, however, means that $f^i(\mathfrak{a})^c=000\ldots 0$, i.e. $f^i(\mathfrak{a})=111\ldots 1$ - "all ones"! It is very easy to see that, at that point, we need to apply $f$ only $n$ more times to get to $000\ldots 0$, i.e. $f^{i+n}(\mathfrak{a})=000\ldots 0$. Thus, the order of $\mathfrak{a}$ exists too, and $o(\mathfrak{a})=i+n\le\frac{(n-1)n}{2}+n=\frac{n(n+1)}{2}$.$\quad\blacksquare$

We can note the following fact that we observed in the previous proof: if $\mathfrak{a}$ ends with a $1$, then:

$$o(\mathfrak{a})=o(\mathfrak{a}^c)+n$$

Finally, we can prove that:

Theorem: The average order of a sequence of length $n$ is $\frac{n(n+1)}{4}$.

Proof: Again, induction on $n$. The statement is trivial for $n=1$. Let $n>1$. There are $2^{n-1}$ of those sequences ending with $0$ and $2^{n-1}$ sequences ending with $1$. The first lot has the average $\frac{(n-1)n}{4}$. The second lot, because of $o(\mathfrak{a})=o(\mathfrak{a}^c)+n$ is by $n$ bigger than the average of all orders of the complementary sequences - which just happen to span the whole set of sequences of length $n-1$. Thus, the second lot has the average $n+\frac{(n-1)n}{4}$. Now, calculating the full average:

$$\begin{array}{rcl}\frac{1}{2^n}\left(2^{n-1}\frac{(n-1)n}{4}+2^{n-1}\left(\frac{(n-1)n}{4}+n\right)\right)&=&\frac{1}{2}\left(2\frac{(n-1)n}{4}+n\right)\\&=&\frac{n(n+1)}{4}\end{array}$$

as desired. $\quad\blacksquare$

Answer 2

Note that every string is of one of the following forms, where $x$ is a smaller string: $x0,1x,0x1$. In each of these cases, we can see that if $x$ is not all zeroes, the operation affects the substring $x$ in the same way that it would affect the string $x$ on its own. (And when $x$ is all zeroes, the process quickly reduces the whole string to zeroes. (In the last case, this takes $2n$ extra steps.)) It follows by induction on string length that the process always terminates in a string of all zeroes.

You can get a recurrence relation for the expected number of steps by considering the disjoint (and equally likely) cases $0x0,0x1,1x0,1x1$.