5
$\begingroup$

Knuth's TAOCP chapter 7.2.1 discusses generating all the $n$-bit binary strings. I am interested in the total number of bits that change during this process.

During generation we store an $n$-bit string and can change some of the bits of the string in each round, with the string output at the end of each round. Call the sequence of integers represented by the output strings the generating sequence. Every $n$-bit string must be generated precisely once in a generating sequence. We are interested in the sum of the Hamming distances between successive elements in the sequence, with the initial value assigned to the string regarded as an $n$ bit change.

For the ascending generating sequence $0,1,\dots,2^n-1$ the number of bits changed during the enumeration is then $2^{n+1} - 2$. The generating sequence $0,2^n-1,1,2^n-2,2,2^n-3,\dots,2^{n-1}-1,2^{n-1}$ yields a larger number of bit changes, at least $(n+1)2^{n-1} = 2^{n-1+\log n}$, and $2^{n-1+\log n} \ge 2^{n+1} > 2^{n+1} - 2$ as long as $n\ge 4$. A Gray code (which changes one bit at each step) yields $n+2^n-1$ bit changes. We can normalise these by dividing by $2^n$ to obtain the mean number of bits changed per step.

What is the distribution of the mean number of bit changes per step, for a generating sequence chosen uniformly at random?

Even the expected value would be useful, or its behaviour as $n$ grows. The mean number of bit changes per step tends to 2 for the ascending sequence and tends to 1 for Gray codes (which achieve the minimum), as $n$ increases. However, I'm not even sure what the maximum is, other than being no larger than $n$ bits per step.

$\endgroup$
  • 2
    $\begingroup$ Can you define what you mean by uniformly at random? Do you mean uniformly over the set of all permutations $\{1,2,\dots,2^n\}$? If so, what have you tried? Shouldn't the expected value follow immediately by linearity of expectation? Am I missing something? $\endgroup$ – D.W. Sep 14 '15 at 6:01
  • $\begingroup$ I am interested in the distribution of the random variable "mean number of changes per step", assuming that each permutation is equally likely. $\endgroup$ – András Salamon Sep 14 '15 at 10:47
  • $\begingroup$ The title suggests a question that you answer in your post; in fact, you ask a totally different question. Please adjust for clarity. $\endgroup$ – Raphael Sep 14 '15 at 13:14
  • 1
    $\begingroup$ You can use linearity of expectation to compute the exact expected number of changes per step. $\endgroup$ – Yuval Filmus Sep 14 '15 at 14:09
  • $\begingroup$ I confess I'm confused by your comment. In your response to my comment you write "I am interested in the distribution" (as if the expected value were not what you wanted), but in the body of the question you say "Even the expected value would be useful", and I thought that's what my comment was explaining how to compute. Anyway: given Yuval's answer, I guess this is now moot. $\endgroup$ – D.W. Sep 14 '15 at 18:21
3
$\begingroup$

It is somewhat more natural to normalize the number of bit changes per step by the number of steps, namely $2^n-1$. We can then rephrase your question as follows. Let $\pi$ be a random permutation of $\{0,1\}^n$. You are interested in the distribution of $$ X = \frac{1}{2^n-1} \sum_{i=0}^{2^n-2} d(\pi(i),\pi(i+1)), $$ where $d$ is Hamming distance. We can compute the moments of $X$ using linearity of expectation. The expected value of $X$ is $$ \mathbb{E}[X] = \mathbb{E} d(\pi(0),\pi(1)) = \mathbb{E}_{x \neq 0} d(0^n,x) = \frac{\frac{n}{2} 2^n}{2^n-1} \approx \frac{n}{2}. $$ The second moment of $X$ is $$ \mathbb{E}[X^2] = \frac{1}{2^n-1} \mathbb{E} d(\pi(0),\pi(1))^2 + \frac{2(2^n-2)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(1),\pi(2)) + \frac{(2^n-2)(2^n-3)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx \mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx \left(\frac{n}{2}\right)^2. $$ More generally, for every fixed $t$ we have $$ \mathbb{E}[X^t] \approx \left(\frac{n}{2}\right)^t. $$ This suggests that $X$ is tightly concentrated around $n/2$.

Going further, one is tempted to conjecture that the distribution is roughly normal, since the dependence between non-adjacent summands is very slight. This can be verified or refuted by repeating the calculation above with $d(\pi(i),\pi(i+1))$ replaced by $d'(\pi(i),\pi(i+1)) = d(\pi(i),\pi(i+1)) - n/2$. Since $d(\pi(i),\pi(i+1))$ is distributed almost like $\mathrm{Bin}(n,1/2)$, this suggests that $X$ is distributed almost like $N(n/2,n/4)$, a normal random variable with mean $n/2$ and variance $n/4$.

$\endgroup$
  • $\begingroup$ Thanks. Counting the first step and dividing by $2^n$ leads to the expectation being precisely $n/2$, so this is perhaps preferable. Any ideas about what the maximum is? $\endgroup$ – András Salamon Sep 14 '15 at 17:55
  • $\begingroup$ You can get more than $n-1/2$ by taking a Gray code $x_0,\ldots,x_{2^{n-1}-1}$ of width $n-1$ and then taking $0x_0,1\overline{x_0},0x_1,1\overline{x_1},\ldots,0x_{2^{n-1}-1},1\overline{x_{2^{n-1}-1}}$. For example, from $00,01,11,10$ we get $000,111,001,110,011,100,010,101$ of average distance $\approx 2.57$. $\endgroup$ – Yuval Filmus Sep 14 '15 at 18:12
  • 1
    $\begingroup$ It seems that my example from the previous comment is actually optimal. It has the maximum number of pairs at distance $n$, and the rest are at distance $n-1$. $\endgroup$ – Yuval Filmus Sep 14 '15 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.