3

Consider the situation of decoding a 6-digit password that consists of the symbols $A$ to $Z$ and $0$ to $9$, where all possible combinations are tried randomly and uniformly.

(a) What is the probability that the correct password will never be entered?

(b) What is the probability that eventually the same combination will be entered two consecutive times?

I am so bad in these combinatorial things.

Can anybody explain me how to calculate these two probabilities, please?

I know that there are $36^5$ possibilities to try.

Edit

For (a) I think I have to look at $$ \left(\frac{36^5-1}{36^5}\right)^n\to 0\text{ as }n\to\infty. $$ So the probability that the correct password will never be entered is 0.

Salamo
  • 1,094
  • 1
    Does the process stop if the correct password has been entered? If not then it is for certain that eventually the same combination will be entered two consecutive times. Positive probability of the event is enough for that. – drhab Nov 08 '14 at 16:02
  • I do not know if it stops if the correct password has been entered. But I think so! – Salamo Nov 08 '14 at 16:05

2 Answers2

6

Answering (a):

  • The probability that the correct password will be entered is $\frac{1}{36^6}$

  • The probability that the correct password will not be entered is $1-\frac{1}{36^6}$

  • The probability that the correct password will not be entered after $n$ attempts is $(1-\frac{1}{36^6})^n$

  • Hence the probability that the correct password will never be entered is $\lim\limits_{n\to\infty}(1-\frac{1}{36^6})^n=0$

Answering (b):

Having entered a password:

  • The probability to enter the same password is $\frac{1}{36^6}$

  • The probability to enter a different password is $1-\frac{1}{36^6}$

  • The probability to enter a different password over $n$ attempts is $(1-\frac{1}{36^6})^n$

  • Hence the probability to always enter a different password is $\lim\limits_{n\to\infty}(1-\frac{1}{36^6})^n=0$

  • Hence the probability to eventually enter the same password is $1-\lim\limits_{n\to\infty}(1-\frac{1}{36^6})^n=1$

barak manos
  • 43,109
  • Does the "two consecutive times" play no role? – Salamo Nov 08 '14 at 16:15
  • @Salamo: I was referring to "two consecutive times" in my answer. I avoided adding the word "consecutive" only in order to keep the answer clear, with one line per bullet. Afer every occurrence of "password", you can implicitly add "immediately after" (which means it refers to entering two passwords one after the other). – barak manos Nov 08 '14 at 16:20
3

If there are $6$ digits with $36$ possible values each, I think there are $36^6$ possible combinations altogether.

Regardless of the exact number of combinations, your reasoning for part (a) is sound.

For part (b), if you keep on making guesses indefinitely (not stopping after you guess the correct password), then eventually you will guess the same value twice in a row with probability $1$ (for reasons similar to part (a)).

If the question is which will happen first, guessing the correct password or making the same guess twice consecutively, consider that after the first guess, each time you guess another sequence of six digits you have an equal chance to guess the correct password or to guess the same sequence as the previous guess. There is a possibility that you will guess the correct password on the very first attempt, however.

Addendum: Calculations for part (b).

If you interpret the problem to mean that guessing will stop when a correct password is guessed, then one way to work the answer is as follows.

Let $p$ be the probability of each possible outcome of each guess. In this particular problem, $p = \frac1{36^6}.$ Consider the first pair of consecutive guesses that are the same. For this to occur on guesses number $n+1$ and $n+2$ requires the following sequence of events:

  1. The first guess is not the correct password. This occurs with probability $1-p.$
  2. Each of the next $n$ guesses is neither the correct password nor the same as the previous guess. Each of these events has probability $1-2p$ given that all the previously required events occurred (that is, given that no previous guess was the correct password).
  3. The guess after that sequence (that is, guess number $n+2$) is the same as the guess before it. This occurs with probability $p.$

This is the story for any non-negative integer $n$, and there is no other way to guess the same password twice. Moreover, the cases for $n = 0, 1, 2, \ldots$ are all disjoint outcomes, since you can only have one "first pair of equal guesses" in any given experiment. The probability that we will have at least one pair of consecutive equal guesses is therefore the sum of probabilities over all these cases: $$\sum_{n=0}^\infty p(1-p) (1-2p)^n.$$ This is the sum of a geometric series, so it is not hard to evaluate.

A simpler method is to consider that to guess the same password twice, our first guess must differ from the correct password (which happens with probability $1-p$), and on each guess after that we have an equal chance either to guess correctly (in which case we stop guessing) or to guess the same password as the previous guess. By symmetry, neither of these events is more likely than the other to occur first. But if a correct guess occurs first, then we never have a duplicate, whereas if a duplicate guess occurs first then of course we do have a duplicate. That gives us a $\frac12$ chance of a duplicate if the first guess is not correct, which gives us an overall probability of $\frac12(1-p).$

David K
  • 98,388
  • Here is my suggestion: I consider the event that any two consecutive tries are different: To choose the first password the probability is $1/36^6$. The next shall be different, so $1-(1/36^6)$, the next again different from the last, i.e. again probability $1-(1/36^6)$ and so on. So that the event that all two consecutive passwords are different after n tries is is $\frac{1}{36}\cdot(1-\frac{1}{36^6})^{n-2}$. When $n\to\infty$ this is $1/36^6\cdot 0 =0$. So the contrary event (that eventually two consecutive tries are the same, is 1-0=1. – Salamo Nov 08 '14 at 16:32
  • Sorry, I meant that the event that after $n$ tries all two consecutive tries were different has probability $\frac{1}{36^6}\cdot (1-\frac{1}{36^6})^{n-1}$. And so, when $n\to\infty$, the probability that all two consecutive tries are different, is $\frac{1}{36^6}\cdot 0=0$, which means, that the contrary event (that eventually two consecutive tries are the same) is 1. Is that right? – Salamo Nov 08 '14 at 16:41
  • If indeed you continue to guess passwords forever, even after guessing the correct one, then you will have two equal consecutive guesses with probability $1.$ I wonder whether that is the intended interpretation of the problem, however, since when we consider a procedure to "decode a password," the procedure usually stops once the correct password is found. Therefore I offer an alternative answer for the interpretation where we stop guessing after guessing the correct password. – David K Nov 08 '14 at 16:46
  • I see what you mean. But I am not able to calculate this. Can you help me? – Salamo Nov 08 '14 at 16:56
  • I have expanded the answer for part (b) to be a little clearer. – David K Nov 08 '14 at 18:58
  • So great, thank you. One question: You understood the Situation in (b) as the Situation that at least two consecutive Passwords are the same. Is it possible to understand it as "two consecutive equal Passwords exactly one time"? - I think YOU are right, because it is only asked for the probabilit that eventually two consecutive tries are the same and this means (I agree) at least one time. – Salamo Nov 08 '14 at 22:47
  • Maybe you can have a look at http://math.stackexchange.com/questions/1012620/6-digit-password-a-special-decoding-method. – Salamo Nov 09 '14 at 12:03