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

The distribution of the number of hits follows the binomial distribution. The probability of no hits can be calculated using the binomial distribution formula as (1 - p)^(n), where p = 10,000/36^6 and n = 1 billion. . The mean of the number of hits is given by n * p, and the variance is given by n * p * (1 - p).

Step-by-step explanation:

To solve this problem, we need to use combinations. Each password consists of 6 characters chosen from a set of 26 letters and 10 integers, so we have a total of 36 possible characters. The number of unique passwords that can be created is therefore 36^6 (since we have 36 choices for each position in the password).

(a) The distribution of the number of hits follows the binomial distribution, with the probability of success (a hit) being the ratio of the number of unique passwords to the total number of possible passwords. In this case, the probability of success is 10,000/36^6, and the distribution is binomial with parameters n = 1 billion (the number of trials) and p = 10,000/36^6 (the probability of success).

(b) The probability of no hits is the probability of failure in the binomial distribution, which is given by (1 - p)^(n), where p = 10,000/36^6 and n = 1 billion.

(c) The mean of the number of hits is given by n * p, and the variance is given by n * p * (1 - p).

Answer 2

The number of hits would follow a binomial distribution with
`n =10,\!000` and
`p \approx 4.59 * 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 * 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 (10,\!000)/(2.18 * 10^(9))` chance of matching one of the users' password.

Denote that probability as
`p`:

`p := \displaystyle (10,\!000)/(2.18 * 10^(9)) \approx 4.59 * 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 * 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 * 10^(-6)` as the chance of success on any given trial.

The probability of getting no hit would be:

`(1 - p)^(n) \approx 7 * 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)) * (4.59 * 10^(-6)) \approx 0.0459`.

The variance of this binomial distribution would be:

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