1 (of 6).

(All numbers in this question are purely fictional.)

A particular type of tumour cell divides according to the rules of a branching pro- cess: with probability 0.35 the cell dies, and with probability 0.65 the cell divides into two. Let Xn denote the number of cells in generation n, where X0  = 1.

(a)    Calculate the extinction probability of this branching process. [5]

Radiotherapy can reduce the chance of a cell dividing to 0.65 - 0.15β, where the value of β e [0, 1] depends upon the strength of the treatment.

(b)    Calculate the extinction probability, as a function of β, for a tumour branching

process which is being treated with radiotherapy. [4]

(c)    Sketch a graph, as a function of β, of the ratio

P (X never hits zero I radiotherapy)

P (X never hits zero I no radiotherapy) . [5]

(d)    Doctor A suggests using radiotherapy strong enough to reduce

P (X never hits zero I radiotherapy) to 70% of the corresponding value with no treatment. Doctor B suggests using a strength which reduces the expected number of cells in generation 3 to 90% of the corresponding value with no treatment. Which of these two suggestions would give the greater probability of the branching process going extinct? [10]

2 (of 6).      Two people play a game using a coin satisfying P (Head) = 0.2 = 1 - P (Tail). On

a player’s turn they toss the coin three times, with the following possible outcomes:

•    if they score three Heads, they win and the game stops;

•    if they score exactly one Head, they get another turn;

•    if they score zero Heads or two Heads, play passes to the other player.

(a)    Find the probability that the player who starts the game is the winner. [10]

(b)    Calculate the expected number of coin tosses before the game ends. [5]

3 (of 6).      Let P be a transition matrix for a Markov chain on a state space S with ISI = n.

Let A be an n × n matrix, each of whose entries equals 1/n. For q e [0, 1] let Mq denote the matrix given by

Mq  = qP + (1 - q)A .

Carefully explain:

(a)    for which values of q  e  [0, 1] we can be sure that there exists at least one

non-negative vector π satisfying (i πi  = 1 and πMq  = π; [5]

(b)    for which values of q  e  [0, 1] we can be sure that there exists a unique π

satisfying these properties. [5]

4 (of 6).      A Markov chain X has state space S = {1, 2, 3, 4} and transition matrix

1     2      3         4

P =  2(1) 、．

3．． 0     0    2/10    8/10．． .

(a)    List the communicating classes, and identify which states are recurrent and

which are transient.

[3]

(b)    Explain why limn二3 Pn exists.

(c)    Calculate limn二3 Pn .

[2]

[11]

5 (of 6).

Consider the following algorithm for generating a finite sequence of random num- bers from the set A = {1, 3, 6, 8}.

E.g. if (X1 , X2 , X3 , . . . ) = (1, 6, 8, 1, 6, 6, . . . ) and N = 4, then V = (1, 6, 8, 1).

(a)    What is the mean length of the output sequence V? [3]

(b)    Let SV denote the sum of the entries in V (so in the example above, SV  = 16).

Calculate E [SV ], making sure to explain your reasoning carefully. [5]

(c)    What is the probability that V contains no 1s? [7]

(Hint: you might find it helpful to condition on the value of N.)

6 (of 6).

Consider an alternative algorithm (different to that in Question 5) for generating a finite sequence of random numbers from the set A = {1, 3, 6, 8}.

E.g. if (X1 , X2 , X3 , . . . ) = (1, 6, 8, 1, 6, 6, . . . ) then, since X6  = X5 , T = 5 and so the output sequence is W = (1, 6, 8, 1, 6).

(a)    Explain how the sequence of random variables in the output sequence W may

be described by a Markov chain with state space {0, 1, 3, 6, 8}, where 0 is an

absorbing state, and write out the transition matrix.

(b)    What is the probability that W contains no 1s?

[4]

[5]

(c)    Let SW denote the sum of the entries in W. Calculate E [SW ]. [7] (Hint: write mk  = E [SW  I X1  = k]; use a first-step decomposition argument to express mk as a linear combination of mj  for j k.)

(d)    Describe some of the differences and similarities between the distributions of the output sequences of Algorithms 1 and 2.  (You are not expected to write more than a few sentences.) [4]

SOLUTIONS: MAT00035I

The offspring distribution is given by P (V = 0) = (1 - ε) = 1 - P (V = 2), where we write ε = 3/10.

(a)    Using the standard notation from the course, the PGF of the offspring distri-

bution is given by GV (z) = (1 - ε)+ (1+ε)z2 . The extinction probability

is the smallest non-negative root to the equation GV (η) = η .           、(')2 Marks

Solving this quadratic (in the knowledge that one of the two roots is always 1) gives the extinction probability to be

1 - ε

1 + ε

(b)    We repeat the calculation from part (a) with the new offspring distribution,

writing ηβ for the extinction probability:

ηβ  =

1 - (1 - β)ε

1 + (1 - β)ε .

'            e

4 Marks 、 /

(c)    The ratio reduces to the following:

P (X never hits zero I radiotherapy) 1 - ηβ (1 + ε)(1 - β) P (X never hits zero I no radiotherapy) =  1 - η  =   1 + (1 - β)ε  .

When β = 0 there is no effect of radiotherapy, and so the ratio equals 1; when β = 1 the process becomes critical, and the numerator hits zero. The graph should show a continuous, decreasing function, lying above the line y = -x. E.g. when ε = 0.2 the graph looks like this:

1.0

0.8

0.6

0.4

0.2

0.2                    0.4                    0.6                    0.8                    1.0

' e 5 Marks 、 /

(d)    We calculate the corresponding β values for each suggestion.

Doctor A: write x = 70/100 and solve (1 - ηβ )/(1 - η) = x to obtain

A  =

(1 + ε)(1 - x) 1 + ε(1 - x)

= 0.357 .

'            e

3 Marks 、 /

Doctor B: The mean of the offspring distribution is µ  :=  1 + ε with no radiotherapy, and µβ   :=  1 + (1 - β)ε with treatment.  The mean number of cells in generation n is µn  and µβ(n), respectively.  Writing n = 3 and y = 90/100, we therefore need to solve

(1 + (1 - β)ε)n  = y(1 + ε)n

for β, which gives

(1 + ε)(1 - y1/n)

ε

'            e

5 Marks

、 /

tion which yields the largest choice of β .                                           、(')2 Marks

'                         e

2.                 (a)    Model the game as a four-state Markov chain with state space S = {A, B, WA , WB },

where A and B indicate that it is player A or B’s turn, and WA  (WB ) indi- cates that player A (B) has won. Write p = 0.2 for P (Head). The chain has transition matrix

A

B(A)   ╱

WB ． 0

B

3p2 (1 - p) + (1 - p)3 3p(1 - p)2

0

0

WA

p3

0

1

0

WB

p3(0) 、．

1(0) ．． .

'            e 5 Marks 、 /

The game is symmetric, so we just need to calculate fA(*),WA , the probability that the chain ever reaches WA  if started from A.  We could do this via a first-step decomposition, or by calculating the matrix GQ : we do both here.

First-step: By symmetry, fB(*),WA   = fA(*),WB   = 1 - fA(*),WA . Thus

fA(*),WA   = p3 + 3p(1 - p)2 fA(*),WA  + (1 - 3p + 6p2 - 4p3 )(1 - fA(*),WA ) . Solving for fA(*),WA  we obtain

fA(*) 3p(1 - p)2         = 0.503 .