0
$\begingroup$

The Hamming weight (or population count) of an integer $n$, which we denote by $w_H(n)$, is the number of $1$'s in the binary expansion of $n$. For example, let $n = 25_{10} = 11001_2$; counting the number of ones, we obtain $w_H(25) = 3$.

We can easily convert to binary (or represent $n_{10}$ as $n_2$) by summing powers of $2$, as follows

$$\cdots + 1(2^4) + 1(2^3) + 0(2^3) + 0(2^1) + 1(2^0) = 2^4 + 2^3 + 2^0 = 16 + 8 + 1 = 25$$

Let's say that $n \to \infty$, and we want to find out if the Hamming weight of $n$ converges or diverges. I.e., when $n \to \infty$, does $w_H(n)$ converge or diverge? If it converges, to what real number does it converge to?

My initial guess is that $n$ does diverge though, but I dont know how to prove it. I did a simple computer experiment and found out that when $n \to 59999$ it does seem to diverge, but very slowly. The average hamming weight at that end-point is $9.428114$. The more the binary length is increasing the more one bits are available. However, in a binary string there are equal amounts of zeros. But that is not enough proof. One last question, is it possible to find out by Cauchy that it converges, or what tools are available?

Thanks.

$\endgroup$
1
$\begingroup$

Obviously it diverges. Because there are arbitrarily large integers with weight $1$ (for example $2^k$) and arbitrarily large integers with weight $2$ (for example $3\cdot 2^k$.)

Edit: Now it seems the OP is really more interested in the average weight. That diverges as well.

Say $0\le n<2^k$. The binary expansion of $n$, if we pad on the left with zeroes, which don't affect the weight, is a sequence of $k$ zeroes and ones. And every sequence of $k$ zeroes and ones appears on the list. Half of the values on $n$ have a one in the first place, half have a one in the second place, etc. So $$2^{-k}\sum_{n=0}^{2^k-1}w_H(n)=k/2.$$(Because there are $2^{k-1}$ ones in each column and there are $k$ columns. For example with $k=3$:

000
001
010
011
100
101
110
111

Sure enough, four ones in each column.)

Note it follows that $\frac 1N\sum_{n=0}^{N-1}w_H(n)\to\infty$. Say $2^k\le N<2^{k+1}$. Then $$\frac 1N\sum_{n=0}^{N-1}w_h(n) \ge\frac 1N\sum_{n=0}^{2^k-1}w_H(n)=\frac {2^k}N(k/2)\ge k/4.$$

$\endgroup$
  • $\begingroup$ Yeah ok. Does that imply that the average of $w_H(n)$ when $n\rightarrow\infty$ also diverges? $\endgroup$ – Natural Number Guy Jun 29 '18 at 17:53
  • 1
    $\begingroup$ @NaturalNumberGuy Not as far as I can see. But it seems pretty clear to me that the average weight for $0\le n\le 2^k$ is something like $k/2$. $\endgroup$ – David C. Ullrich Jun 29 '18 at 18:01
  • $\begingroup$ Thanks for the comprehensible answer. $\endgroup$ – Natural Number Guy Jun 29 '18 at 18:14

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.