Question

A computer system uses passwords that are exactly six characters and each character is one of the 26 letters (a–z) or 10 integers (0–9). Suppose that 10,000 users of the system have unique passwords. A hacker randomly selects (with replace- ment) one billion passwords from the potential set, and a match to a user’s password is called a hit. (a) What is the distribution of the number of hits? (b) What is the probability of no hits? (c) What are the mean and variance of the number of hits?

Answer 1

Answer:

The number of hits would follow a binomial distribution with $n =10,\!000$ and $p \approx 4.59 \times 10^{-6}$.

The probability of finding $0$ hits is approximately $0.955$ (or equivalently, approximately $95.5\%$.)

The mean of the number of hits is approximately $0.0459$. The variance of the number of hits is approximately $0.0459\!$ (not the same number as the mean.)

Step-by-step explanation:

There are $(26 + 10)^{6} \approx 2.18 \times 10^{9}$ possible passwords in this set. (Approximately two billion possible passwords.)

Each one of the $10^{9}$ randomly-selected passwords would have an approximately $\displaystyle \frac{10,\!000}{2.18 \times 10^{9}}$ chance of matching one of the users' password.

Denote that probability as $p$:

$p := \displaystyle \frac{10,\!000}{2.18 \times 10^{9}} \approx 4.59 \times 10^{-6}$.

For any one of the $10^{9}$ randomly-selected passwords, let $1$ denote a hit and $0$ denote no hits. Using that notation, whether a selected password hits would follow a bernoulli distribution with $p \approx 4.59 \times 10^{-6}$ as the likelihood of success.

Sum these $0$'s and $1$'s over the set of the $10^{9}$ randomly-selected passwords, and the result would represent the total number of hits.

Assume that these $10^{9}$ randomly-selected passwords are sampled independently with repetition. Whether each selected password hits would be independent from one another.

Hence, the total number of hits would follow a binomial distribution with $n = 10^{9}$ trials (a billion trials) and $p \approx 4.59 \times 10^{-6}$ as the chance of success on any given trial.

The probability of getting no hit would be:

$(1 - p)^{n} \approx 7 \times 10^{-1996} \approx 0$.

(Since $(1 - p)$ is between $0$ and $1$, the value of $(1 - p)^{n}$ would approach $0\!$ as the value of $n$ approaches infinity.)

The mean of this binomial distribution would be:$n\cdot p \approx (10^{9}) \times (4.59 \times 10^{-6}) \approx 0.0459$.

The variance of this binomial distribution would be:

$\begin{aligned}& n \cdot p \cdot (1 - p)\\ & \approx(10^{9}) \times (4.59 \times 10^{-6}) \times (1- 4.59 \times 10^{-6})\\ &\approx 4.59 \times 10^{-6}\end{aligned}$.