0
$\begingroup$

You are given a parameter $ x\in\{0, 1, 2,\ldots,256\} $, where $x$ is the required number of zeros in the output bit string.

What is the probability that the output from a function that produces a randomly chosen bitstring from the set $ \{0, 1\}^{256}$ contains the $x$ amount of leading zeros. Assume that the output is uniformly randomly chosen, but if the same input is again given, it will produce the same output. Give your answer in terms of $x$. For example, if $x$ is $0$, the probability is $1$, because there is no requirement for leading $0$'s.

My answer: I know that this is a bernoulli distribution. I think the answer is
Pr(the output has the required number of leading zeros) = ${(\tfrac{1}{256})}^{p}$ , because the probability of mapping the $0$ to the correct leading position is $ \frac{1}{256} $ for each required $p$.

Any help or advice is appreciated! Thanks.

$\endgroup$
2
  • $\begingroup$ Instead of a function producing random results, it is better to speak of random variables (which happen to be functions with s suitably chosen domain). It would be more important to state that the bitstring is uniformly randomly chosen ... $\endgroup$ Apr 1 '17 at 2:24
  • $\begingroup$ @HagenvonEitzen Ok! I have updated that. $\endgroup$ Apr 1 '17 at 2:30
2
$\begingroup$

The first $x$ bits follow the same distribution as a sequence of $x$ tosses of a fair coin.The probability of tossing "heads" $x$ times in a row is $2^{-x}$.

$\endgroup$

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.