1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$
0
$\begingroup$

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$.

$\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.