4
$\begingroup$

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:

enter image description here

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.

enter image description here

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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$? $\endgroup$ Commented Sep 23, 2022 at 6:03
  • $\begingroup$ @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. $\endgroup$
    – Galen
    Commented Sep 23, 2022 at 17:15

1 Answer 1

4
$\begingroup$

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). $$

$\endgroup$
3
  • $\begingroup$ That is the sum of $p(x)$ over all $x$ that satisfy the equality $\operatorname{bit\_count}(x) = y$? $\endgroup$
    – Galen
    Commented Sep 23, 2022 at 7:01
  • 1
    $\begingroup$ Yes, that is correct. $\endgroup$
    – frank
    Commented Sep 23, 2022 at 7:05
  • $\begingroup$ +1 I can readily see how this answer generalizes to a class of similar questions. $\endgroup$
    – Galen
    Commented Sep 23, 2022 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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