# What is the distribution of bit counts of a binomial random variable?

Suppose I have a binomial random variable $$X \sim B(n,p)$$ and I apply the following bit counting operation $$Y = \operatorname{bit\_count}(X)$$

where $$\operatorname{bit\_count}$$ is defined in the following Python code.

def bit_count(x:int) -> int:
bits = 0
while x:
bits += x & 1
x >>= 1
return bits


Here is a table of values computing this function on $$x \in [0, 19]$$ (for your copy-pasting convenience).

X bit_count(X)
0 0
1 1
2 1
3 2
4 1
5 2
6 2
7 3
8 1
9 2
10 2
11 3
12 2
13 3
14 3
15 4
16 1
17 2
18 2
19 3

Similarly, we can plot such data for $$x \in [0, 49]$$ to reveal a serrated pattern:

We can also consider a simulated example that gives us a sense of what the resulting distribution can look like. This was $$10^4$$ samples from $$B(100, 0.5)$$, then transformed with the $$\operatorname{bit\_count}$$ transform.

Because the smoothness does not apply here, we cannot consider the derivative or Jacobian for the change in variable.

How can we derive such a distribution?

• Surely you need to define a functional form of the mapping from $X$ to $Y$ and not just an algorithm for getting $Y$ from $X$ for certain $x$? Commented Sep 23, 2022 at 6:03
• @statsplease Having an algebraic expression is nice, but not necessary in general. As frank's answer shows, it is sometimes sufficient to be able to compute over a finite collection of outcomes. Commented Sep 23, 2022 at 17:15

We have a well-known distribution $$X \sim B(n,p)$$, i.e. we know $$p(x)$$, and a well-defined function bit_count: $$x\to y$$ for the domain $$x\in [0:n]$$. Then, the distribution over the image of bit_count is simply obtained as $$p(y) = \sum_{x,\; bit\_count(x) = y} p(x).$$
• That is the sum of $p(x)$ over all $x$ that satisfy the equality $\operatorname{bit\_count}(x) = y$? Commented Sep 23, 2022 at 7:01