# Creating a probability density function from a word problem

I am taking a course related to probabilities and as a primer we are given some word problems, I have somehow slipped by in my earlier classes and never have taken a classes on such subjects. I was hoping for some direction on how I might go about solving this problem. The problem is stated as such

A mischievous student wants to break into a computer file, which is password-protected. Assume that there are $n$ equally likely passwords, and that the student chooses passwords independently at at random and tries them. Let $N_n$ be the number of trials required to break into the file. Determine the probability density function of $N_n$

(a) If unsuccessful passwords are not eliminated from further selections.

(b) If unsuccessful passwords are eliminated from further selections.

So just talking it through, for the student to crack the password after $x$ tries he would have the chance of $x / n$ meaning the more times he tries the better chance he has to crack the password, because once $x = n$ then the password has to be cracked.

So as a function, the probability that the password is cracked after $x$ tries would be

$$P( N_n = x) \ = \ x / n$$

I think that this would be the solution to part b of the problem above because this takes into account that the student can assume past unsuccessful attempts will never work again?

But I am lost for insight on part a, as to how unsuccessful attempts would affect his future attempts?

Can anyone offer some guidance on this problem?

## 2 Answers

Let's try the first question (no elimination):

• For $k=0$ the probability that the password has already been guessed after $k$ tries is zero. ($F(0) = 0$). The probability that the password hasn't yet been guessed is $1-0 = 1$.
• For any given $k>0$, the probability that the password has not yet been guessed after $k$ tries is $1-F(k) = \left( 1-F(k-1) \right) \left( 1-\frac{1}{n}\right)$ since you have to have not-guessed it on the first $k-1$ tries and again miss on the $k$-th.
• So for all $k \geq 0$, $$1-F(k) = \left( 1-\frac{1}{n}\right)^k \\F(k) = 1-\left( 1-\frac{1}{n}\right)^k$$

$F(k)$ is, of course, the cumulative distribution function. To get $f(k)$, the probability that the first correct guess happens on try $k$, we can use the probability that no correct guesses happened on the first $k-1$ tries times the probability that the $k$-th try is a hit: $$f(k|k>0) = \left( 1-\frac{1}{n}\right)^{k-1} \frac{1}{n}$$ As a correctness check, $f(1) = 1/n$ and that makes sense -- there is a $1/n$ chance of hitting it on the first guess.

Now let's see how you would handle the second question (with elimination):

• Again $F(0)=0$.
• For any given $k>0$, the probability that the password has not yet been guessed after $k$ tries is $1-F(k) = \left( 1-F(k-1) \right) \left( 1-\frac{1}{n-k+1}\right)$ since you have to have not-guessed it on the first $k-1$ tries and again miss on the $k$-th $-$ but this time, the chance of a hit on the $k$-th guess is $\frac{1}{n-k+1}$ because you have already shrunk the "field" by eliminating $k-1$ earlier guesses.
• So for all $k\geq 0$, $$1-F(k) = \left( 1-\frac{1}{n}\right) \left( 1-\frac{1}{n-1}\right) \cdots \left( 1-\frac{1}{n-k+1}\right) \\F(k) = 1-\left( \frac{n-1}{n}\right) \left(\frac{n-2}{n-1}\right) \cdots \left( \frac{n-k}{n-k+1}\right) = 1 - \frac{n-k}{n} = \frac{k}{n}$$

Note that for $k \geq n$, $F(k) = 1$ since that big product has a zero in it.

To get $f(k)$ use the fact that $F(k) = \sum f(k)$; this says that $$f(k|0<k\leq n) = \frac{1}{n}$$

We give a very condensed solution, leaving you to fill in details.

For (a) we need $x-1$ wrong guesses followed by a right guess. Thus the probability distribution function of $N_n$ is given by $\Pr(N_n=x)=\left(\frac{n-1}{n}\right)^{x-1}\cdot\frac{1}{n}$, where $x$ ranges over the positive integers.

For (b) the password is equally likely to be the first thing tried, the second, and so on, so in that case $\Pr(N_n=x)=\frac{1}{n}$ for $x=1,2,\dots,n$.