0

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 think it is very difficult to compute these probabilities by pure combinatorical thoughts, isn't it? As you can see here: 6-digit password - a special decoding method

So I asked myself if it is possible and smart to see this decoding strategy as a kind of Markov chain maybe? Maybe it is easier then to solve?

This task is asked in the context of a lecture concerning Markov chains, so it is at least not devious to have this assumption.

Hope you can help me.

Community
  • 1
Salamo
  • 1,094

1 Answers1

1

Kolmogorov's 0-1 law immediately gives (b) $1$.

(a) must be $0$ too, but the law doesn't immediately apply because a priori the probabilities are not independent.

We can instead use the law to prove that with probability $1$ we will eventually reach the correct combination in the particular way that starting with attempt number $6n$ for some $n$ we will randomly select the right digits for positions 1, 2, 3, 4, 5, 6, in that order. The probability of this happening for different $n$s is independent, so the law applies. And since there's a probability of $1$ to find the right code in a special way, the probability of finding it at all must also be $1$.

hmakholm left over Monica
  • 286,031
  • Can you explain me how I can model the decoding method as a markov chain? – Salamo Nov 10 '14 at 10:48
  • @Salamo: Um .. expressing it as a Markov chain is completely straightforward. There's a state for each of the possible "current" combinations, and it can turn into a different state in $6\cdot 36$ equally probably ways (except that 6 of those actually don't change the combination and so combine into a single transition with probablity $1/36$). – hmakholm left over Monica Nov 10 '14 at 10:52