Q1 A random symbol generator produces each of 10 digits and each of 26 letters

of the latin alphabet with positive probability.  Assuming that the individual out- comes are independent, let M be event that an infinite sequence of such symbols contains the word MATH2647 infinitely often.

1.1  Find the probability of M using a suitable monotone approximation.

1.2  Find the probability of M using the Borel-Cantelli lemma.

In your answer you should clearly state and carefully apply every result you use.

Q2 An XOR gate adds bits according to the following rules:

0 + 0 = 1 + 1 = 0 ,        1 + 0 = 0 + 1 = 1 .

Suppose that random bits (Bk )k(n)=1  are independent and have a common distribu- tion P(Bk  = 1) = p = 1     P(Bk  = 0), where 0 ❁ p ❁ 1. Write Sn  for the result of the sum of these bits using XOR gates, and let pn  be the probability of the event ❢Sn  = 1❣, equivalently,

pn  = P ✏the sequence (Bk )k(n)=1  contains an odd number of ‘ones’ ✑ .

2.1  Compute p1  and p2 .

2.2  Show that, with properly defined p0 , we have pn  = p + (1     2p) pn   1  for all n ✕ 1.

2.3  Use generating functions to derive a closed formula for pn , and check that it gives correct values for n = 0, 1, 2.

2.4  Find nlim✦✶pn  and explain your result.

Q3  Consider a Markov chain with state space ❢1, 2, 3, 4❣ and the transition matrix

✵ 0     1❂2     0     1❂2✶

P =  ❇(❇)1❂2      0      1❂2      0    ❈(❈)

 ❈❆ .

3.1  Describe the class structure of this Markov chain and determine the period of each state.

3.2  Find all stationary distributions for this Markov chain.

3.3  Find a closed expression in terms of powers of the eigenvalues of P for the n-step transition probabilities p1(n))  and p .

3.4  Deduce closed expressions in terms of powers of the eigenvalues of P for the n-step transition probabilities p  and p, where n ❃ 0.

3.5  Classify all states of this Markov chain into transient and recurrent.

In your answer you should clearly state and carefully apply every result you use.

Q4  For real an  ❃ 0 and pn  ✷ (0, 1), let (Xn )n✕1  be random variables such that P(Xn  = an ) = pn  = 1    P(Xn  = 0).

For each of the following claims, prove the result if it is correct, or find a coun- terexample otherwise:

4.1  If an  ✦ 0, then Xn  ✦ 0 in Lr , for some r ❃ 0, as n ✦ ✶ .

4.2  If an  ✦ 0, then Xn  ✦ 0 in probability as n ✦ ✶ .

4.3  If an  ✦ 0, then Xn  ✦ 0 almost surely as n ✦ ✶ .

4.4  If pn  ✦ 0, then Xn  ✦ 0 in Lr , for some r ❃ 0, as n ✦ ✶ .

4.5  If pn  ✦ 0, then Xn  ✦ 0 in probability as n ✦ ✶ .

4.6  If pn  ✦ 0, then Xn  ✦ 0 almost surely as n ✦ ✶ .

4.7  If pn  ✦ 0 and the variables Xn  are independent, then Xn  ✦ 0 in Lr , for some r ❃ 0, as n ✦ ✶ .

4.8  If pn  ✦ 0 and the variables Xn  are independent, then Xn  ✦ 0 in probability as n ✦ ✶ .

4.9  If pn  ✦ 0 and the variables Xn  are independent, then Xn  ✦ 0 almost surely as n ✦ ✶ .

In your answer you should clearly state and carefully apply any result you use.