Martingales applications

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

Martingales applications

September 16, 2010 beni22sof Leave a comment Go to comments

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.