Question

Prove that if \(m\) is not a power of \(2,\) there is no probabilistic algorithm whose running time is strictly bounded and whose output distribution is uniform on \(\\{0, \ldots, m-1\\}\).

Short answer

Question: Prove that if m is not a power of 2, then there is no probabilistic algorithm with a strictly bounded running time that can produce a uniform output distribution on the set {0, 1, ..., m-1}. Answer: There is no such probabilistic algorithm because using the pigeonhole principle, it can be shown that the output distribution can never be uniform if m is not a power of 2. For at least two different output values a and b, the number of input strings mapping to them will differ by at least 1, contradicting the requirement for a uniform output distribution.

Step-by-step solution

Understand the problem and establish some initial facts

We want to prove that if \(m\) is not a power of \(2\), there is no probabilistic algorithm with a bounded running time that can produce a uniform output distribution on the set \(\\{0, 1, \ldots, m-1\\}\). First, we need to establish that a probabilistic algorithm can consume random bits of information, in the form of 0's and 1's. If the running time is strictly bounded, then the maximum number of distinct input strings for the random bits is finite.

Prove that the distribution is not uniform

Let's assume that there is a probabilistic algorithm with a bounded running time that supposedly generates a uniform output distribution on the given set. Let's say that the running time is bounded by \(k\). Since the running time is bounded, it is guaranteed to consume at most \(k\) random bits. From these random bits, there are a total of \(2^k\) possible input strings, which will lead to the distinct output strings. Now, applying the pigeonhole principle, we can see that after dividing the \(2^k\) possible input strings among the \(m\) distinct output values (since we assume the distribution is uniform), there must exist at least one output value that receives \(\lceil\frac{2^k}{m}\rceil\) input strings, where \(\lceil x \rceil\) is the smallest integer greater than or equal to x. Since \(m\) is not a power of \(2\), we know that for some values of \(i \geq 0\): $$2^i < m < 2^{i+1}$$ Because of the pigeonhole principle, there must exist at least two different output values, \(a\) and \(b\), such that the number of input strings mapping to \(a\) and \(b\), respectively, differ by at least 1. In other words, we have: $$\left|\textrm{Number of inputs that map to }a - \textrm{Number of inputs that map to }b\right| \geq 1$$

Show the contradiction

This difference in the number of input strings mapping to two different output values contradicts the assumption that the output distribution is uniform. A uniform output distribution requires all output values to have the same probability, which is not the case here. Therefore, there is no probabilistic algorithm with a strictly bounded running time that produces a uniform output distribution on the set \(\\{0, 1, \ldots, m-1\\}\), if \(m\) is not a power of \(2\).

Key concepts

Uniform Distribution

In probability, a uniform distribution is a type of distribution where all possible outcomes are equally likely. When we talk about generating a uniform distribution through a probabilistic algorithm, we mean the algorithm should produce each number in its range with an equal chance. Understanding this, it becomes clear why generating a uniform distribution between 0 and some number less than a power of 2 using random bits is problematic. Because random bits are inherently binary (0s and 1s), they naturally favor outputs that are powers of 2. This is because every additional bit doubles the possible combinations. Therefore, if we want a uniform distribution over 0 to 7, for instance, each of these outcomes would need a 1 in 8 chance, which fits perfectly since 8 is a power of 2. However, if we wanted a uniform distribution over 0 to 5, things get tricky. Since 6 isn't a power of 2, we can't split 2's binary combinations evenly among 6 states, leading to some numbers appearing more frequently than others.

Pigeonhole Principle

The pigeonhole principle is a concept in mathematics that states if you have more items than containers, at least one container must contain more than one item. Applying this to our problem, imagine the containers are the possible outputs of our algorithm and the items are the input possibilities determined by random bits. If you have a probabilistic algorithm consuming a finite number of random bits, there are typically more possible inputs (or pigeonholes) than the number of desired output values when the range isn't a perfect power of 2. This forces at least one output to receive more inputs than others, meaning the distribution cannot be uniform. For instance, if we use bits to generate numbers between 0 and 5, and our input combinations are 8 (as derived from 3 bits, which is 2^3), at least some numbers will have more combinations leading to them than others, because 8 divided by 6 outputs doesn’t divide evenly. Thus, this imbalance speaks directly to the failure of uniform output.

Random Bits

When creating a probabilistic algorithm, random bits are a foundational element. They are bits or binary digits (0s and 1s) that are used as the building blocks of random decision-making in computers. Each bit represents a binary choice, and together, these form the basis of almost every randomized procedure in computing. Using k random bits, you can create any number in the range of 0 to 2^k - 1. This is why powers of 2 are significant; they define the limits of what can be generated with those bits in a fair or uniform way. If, however, the range of desired outputs is not a power of 2, the challenge lies in the need for these bits to map onto non-uniform ranges. Attempting to map them uniformly to a set that isn't a power of 2 will inevitably lead to some numbers being represented more than others. Thus, we see why the impracticality of using a finite set of random bits to generate a genuinely uniform distribution for non-power of 2 numbers arises.