Lesson 7

Problem. Consider a distribution on binary strings of length \(n\): \(U=\{0,1\}^{n}\). Suppose we do not know the probabilities of elementary outcomes, but we know the probabilities of the following \(n\) events: for any \(i \in [n]\), it holds that \(\Pr[u_{i}=0] = 1/2\), where \(u \in U\) is a random string (that is, a zero appears at each position with probability \(1/2\)). Is it true that the distribution is uniform on \(U\)? (In other words, is it true that \(\Pr[u]=2^{-n}\) for any \(u \in U\)?)