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