4

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.

Consider the following decoding method: At first a combination is chosen randomly and uniformly. At the next trial a digit from this combination is chosen uniformly at random and its entry is substituted by a uniformly randomly chosen element from $\left\{A,...,Z,0,...,9\right\}$. This procedure is repeated until the password is found.

(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 already asked how to get the anwers to (a) and (b) without using the here mentioned special decoding method and I got great help, see Probability concerning a 6-digit password.

Now I have to answer (a) and (b) using the decoding method and again I have enormous problems! Combinatorical thoughts are not my favourite business. Nevertheless I tried to find the probabilities in an analog way as it was shown to me in the linked thread.

Additionally, I wonder if this task now maybe has something to do with Markov chains because the lecture this task is from is about Markov chains.

I think there are (at least) the two following ways to understand the described decoding strategy, which sense is meant?

Sense 1 We choose (randomly and uniformly) one of the $36^6$ possible combinations. If it is the right, we stop. Otherwise we then choose (randomly and uniformly) one of the 6 digits and substitute it (randomly and uniformly) by a symbol out of the alphabet. Then we choose (randomly and uniformly) one of the remaining 5 digits and subtitute it and so on until we substituted all the 6 digits. If this was the right password, we stop. If not, we again start substituting the 6 digits (the digits of the combination that we chosed at the beginning, that is, we stick to this combination).

Sense 2 Same as above with the difference that after we substituted all 6 digits and saw that it is the wrong password, we choose (randomly and uniformly) another combination out of the $36^6$ possibilities (it can be the same as before) and then substitute the digits of this new combination.

I think that sense 1 is meant and thus I considered the task in this sense.

(a) Anyway, my result here is $0$, because as far as I see the probability not to have reached the right password after n passages is $$ \left(1-\frac{1}{36^6}\right)\cdot\left(1-\prod_{k=1}^6\frac{1}{k\cdot 36}\right)^n $$ and this tends to $0$ as $n\to\infty$.

Remark: If we decode without this special method (see the linked thread) then the probability of (a) is 0, too.

(b) The probability that we have eventually one pair of consecutive equal guesses is - to my results - $$ \sum_{n=0}^{\infty}\left(1-\frac{1}{36^6}\right)\cdot\left(\prod_{k=1}^6\frac{35}{k\cdot 36}\right)\cdot\left(\prod_{k=1}^6\frac{34}{k\cdot 36}\right)^n\left(\prod_{k=1}^6\frac{1}{k\cdot 36}\right) $$

Edit

I think my last result for (b) was not correct, I think instead it has to be $$ \sum_{n=0}^{\infty}\left(1-\frac{1}{36^6}\right)\cdot\left(1-\prod_{k=1}^k\frac{1}{k\cdot 36}\right)\cdot\left(1-\prod_{k=1}^{6}\frac{2}{k\cdot 36}\right)^n\cdot\left(\prod_{k=1}^{6}\frac{1}{k\cdot 36}\right). $$

If I know compute the geometrical series and use that $1-\prod_{k=1}^{6}\frac{1}{k\cdot 36}\approx 1$, then I get that (with $p:=\frac{1}{36^6}$) the probability of (b) is $$ \approx \left(\frac{1}{2}\right)^6\cdot (1-p) $$

Remark: When decoding without this method (see the linked thread) then the probability of (b) is $\frac{1}{2}\cdot (1-p)$. That is, using the method, if my result is correct, we have a much smaller probability for (b). So this decoding method is more efficient.

Would be great to get a feedback from you to know if I am right. And, as mentioned, I am interested to know if the task has something to do with the context of Markov chains.

Ciao & greetings

Salamo

Community
  • 1
Salamo
  • 1,094
  • With random substitution of just one digit for each new guess, if you allow the digit to be replaced by any of the $36$ digits from ${0,1,...,Z},$ including the value that digit already has, then each guess has a $\frac 1{36}$ chance to repeat the guess before. You will repeat much more than when all digits are randomized every time. If the replacement digit can only be taken from the set of $35$ digits that differ from the value that digit already has, then there is zero probability for any consecutive guesses to be the same. – David K Nov 09 '14 at 21:08
  • This has some relevance also to genetic algorithms. In particular, there is an algorithm I work with that is allowed to "mutate" one symbol in one member of its population (which is essentially a string of symbols), with the restriction that a mutation must substitute a different value for that symbol. Therefore a string can never mutate to itself in one step. However, the string can still (and sometimes does!) mutate back to itself in two steps. – David K Nov 09 '14 at 21:17
  • I did not understand your first comment. You are trying to say me that my calculations are false, right? Maybe you can write in an answer how it is computed correctly? (As in your last answer in the linked thread, that was very helpful to me)? – Salamo Nov 09 '14 at 21:20
  • I understood the decoding method in a wrong way? – Salamo Nov 09 '14 at 21:21
  • I think for your analysis of part (b), after testing one sequence to see if it is the password, you substitute multiple digits in the sequence before testing to see if the new sequence is the password. I interpreted the problem statement to mean you substitute just one digit and then test. The problem statement seems ambiguous, however, so I am not sure which interpretation was intended. – David K Nov 09 '14 at 21:48
  • I think you are right! Because this fits better to the description of the method! Puh, its hard to calculate it then, isn't it? – Salamo Nov 09 '14 at 21:54
  • @DavidK Do you have an idea how one can compute the searched probabilities? I did not find a way, unfortunately. – Salamo Nov 10 '14 at 09:38

0 Answers0