I am trying to figure out how to approach this probability problem. Let f be a function defined as $f: (0,1)^n \rightarrow (0,1)^n$. That is to say, it accepts and outputs n-bit strings. The output is a random uniform distribution. I am attempting to reason about how likely it is that for all possible inputs if there is ever an output that equals the input.

The output does not depend on any previous output since the same value can be assigned to multiple inputs, so there are $2^n$ outputs possible at any time.

If there are $2^n$ possible inputs and $2^n$ outputs you can make $2^n$ attempts, all with $1/2^n$ probability. This line of reasons is clearly flawed because $2^n * 1/2^n = 1$ and obviously the probability of this event is not 1.

Can anyone provide some insight on or ideas on this?


Each attempt succeeds with probability $p=1/2^n$ hence each attempt fails with probability $1-p$. There are $k=2^n$ attempts and they are independent hence they all fail with probability $(1-p)^k$.

The probability $s_n$ that at least one attempt succeeds is $s_n=1-(1-p)^k$, that is, $s_n=1-(1-1/2^n)^{2^n}$. Note that $s_n\to1-1/\mathrm e\approx0.632$ when $n\to\infty$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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