Home > Measure Theory, Probability, Problem Solving > Martingales applications

Martingales applications


Let (X_n)_n be a sequence of independent identically distributed sequence of random variables taking values 0 and 1 with probabilities p and q respectively with p+q=1. Find the expected time for the first occurrence of the sequences:
a) 0; 1;
b) 01; \underbrace{11...1}_{k}
c) Which of the sequences 01 and 11 is more likely to appear first.

A monkey has a keyboard and types at every second one capital letter with probability 1/26. 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 (X_n)_n taking values in the set of letters \{A,B,C,...,Z\}, representing the key pressed at time n. Consider the events A_k=\{\text{ABRACADABRA is typed between times } 11k+1 \text{ and } 11(k+1)\}.

Then the events A_k are independent with probability P(A_k)=(1/26)^{11} and therefore \displaystyle \sum_n P(A_n)=\infty. Then, by the Borel-Cantelli Lemma the event A_k 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

Y_n=26^{11}\chi_{\{X_1=A,X_2=B,X_3=R...X_11=A\}}+...+26^{11}\chi_{\{X_{n-10}=A,...X_n=A\}}+

+26^{10}\chi_{\{X_{n-9}=A,X_{n-8}=B,...,X_n=R\}}+..+26^2\chi_{\{X_{n-1}=A,X_n=B\}}+26\chi_{\{X_n=A\}}.

Then if \mathcal{F}_n=\sigma(X_1,...,X_n) we have E(Y_{n+1} | \mathcal{F}_n)=Y_n+1, which means \{Y_n-n\}_n is a martingale. Denoting with a \wedge b the minimum of a,b, and with N the random variable which contains the time of the first appearance of ABRACADABRA. Then \{Y_{n \wedge N}- (n\wedge N)\}_n is again a martingale and by Doob’s optional stopping time theorem we have E(Y_{n\wedge N})=E(n\wedge N). By monotone convergence we have E(N)=E(Y_N)=26^{11}+26^4+26 which is about 3.67034449 times 10^{15} seconds.

One year has 31 536 000 seconds so it will take about 100 million years. Quite impossible for a normal monkey.

About these ads
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 333 other followers

%d bloggers like this: