## Martingales applications

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) ; ;

b) ;

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 .

Then the events are independent with probability and therefore . Then, by the Borel-Cantelli Lemma the event occurs infinitely often.

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.

## Leave a Reply