# Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution

Let $$X$$ be an integer sampled uniformly from the (integer) range $$\{ 0...2^k - 1 \}$$ .

Now, consider the distribution of

$$\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_2(X) \rfloor & \text{otherwise} \end{cases}$$

and

$$\#\text{bytes}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_{256}(X) \rfloor & \text{otherwise} \end{cases}$$

which are the numbers of bits and of bytes respectively necessary to hold $$X$$.

My question: Is there some commonly-used term for the one of the distributions of $$\#\text{bits}(X)$$ or $$\#\text{bytes}(X)$$ ? Or for a distribution which is very similar to them?

• Geometric distribution. – Yuval Filmus Dec 23 '18 at 21:41
• @YuvalFilmus: Not exactly, but that's super-close. Thanks and see my answer. – einpoklum Dec 23 '18 at 23:36

## 1 Answer

As @YuvalFilmus suggests, these distributions are very close to being geometric. They aren't geometric, since they're bounded, which is what threw me off, but think about it this way:

A geometric distribution corresponds to the number of Bernouli trials up to and including a first success (in some formulations: not including the first success). The distribution parameter p is the probability of succeeding in each individual experiment. Now,

• Our first "experiment" involves sampling the most significant bit (or byte): Will it be 0, or something else? A 0 is a success, something else is a failure.
• Our second "experiment" is the same, but for the second-most-significant bit (or byte).
• and so on.

In a geometric distribution proper, experiments never cease until the first success. In our case, $$k$$ experiments are conducted, and if you've failed them all then you're simply at 0, with probability $$2^{-k}$$.