Let be a sequence of independent identically distributed sequence of random variables taking values and with probabilities and respectively with . Find the expected time for the first occurrence of the sequences:
a) ; ;
c) Which of the sequences and is more likely to appear first.
A monkey has a keyboard and types at every second one capital letter with probability . What is the probability that the monkey writes the sequence ABRACADABRA ( once, infinitely many times ). What is the expected time for the first occurrence of ABRACADABRA?
For a solution for the first problem see MartingaleExtras.
For the second problem consider the sequence of random variables taking values in the set of letters , representing the key pressed at time . Consider the events .
Another approach is by using Kolmogorov’s 0-1 law. The event that the monkey types ABRACADABRA infinitely often is a tail event and therefore it has probability 0 or 1.
For finding the expectation of the first occurrence of ABRACADABRA we use martingales by the model given in the .pdf file. Define the random variables
Then if we have , which means is a martingale. Denoting with the minimum of , and with the random variable which contains the time of the first appearance of ABRACADABRA. Then is again a martingale and by Doob’s optional stopping time theorem we have . By monotone convergence we have which is about times seconds.
One year has 31 536 000 seconds so it will take about 100 million years. Quite impossible for a normal monkey.