\documentclass[a4paper,12pt]{article}
\newcommand{\ds}{\displaystyle}
\newcommand{\pl}{\partial}
\parindent=0pt
\begin{document}


{\bf Question}

A signalling lamp has three possible modes. off, red, and green. A
secret agent has two such lamps. He operates them at one minute
intervals according to the following scheme. He selects a lamp at
random. If it is off he switches it to red or green with equal
probabilities. If it is already on, he changes the colour being
shown. The two lamps are indistinguishable. Write down the six
possible states of the system and explain briefly why it forms a
Markov chain. Classify the states according to transience or
recurrence, giving reasons in each case. Determine the period of
any recurrent states. Calculate the mean recurrence time of any
positive recurrent states.

${}$

What proportions of a long interval of time would you expect the
system to spend in each state?

${}$

The system starts with both lamps off, and the agent commences one
minute later. What is the probability that one lamp is off after
$\left(k+\ds \frac{1}{2}\right)$ minutes have elapsed?



\vspace{.25in}

{\bf Answer}

The six possible states are as follows:

1. Both lamps off\ \ 2. 1 off 1 red\ \ 3. 1 off 1 green

4. Both red\ \ 5. Both green\ \ 6. 1 red 1 green

When the agent arrives to change the lamps, the probabilities of
change depend only on the state the lamps are in, and not on how
that state was reached. This is the characteristic property of a
Markov chain. The transition matrix is as follows, the
rows/columns corresponding to states 1-6 above.

$$\left(\begin{array}{cccccc} 0 & \frac{1}{2} & \frac{1}{2} & 0 &
0 & 0 \\ 0 & 0 & \frac{1}{2} & \frac{1}{4} & 0 & \frac{1}{4}\\ 0 &
\frac{1}{2} & 0 & 0 & \frac{1}{4} & \frac{1}{4} \\0 & 0 & 0 & 0 &
0 & 1\\ 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & \frac{1}{2} &
\frac{1}{2} & 0 \end{array}\right)$$

The transition diagram can be drawn as follows

PICTURE \vspace{2in}

State 1 is transient. Indeed the system leaves state 1 after 1
step, never to return. $p_{11}=0$.

${}$

States 2 and 3 are transient. $p_{22}=p_{33}=\ds \frac{1}{4}$.
Also from states 2 and 3 there is a probability $\ds \frac{1}{2}$
if entering the closed set of states $\{4,\ 5,\ 6\}$.

${}$

The closed set $\{4\, 5,\ 6\}$ forms a sub-chain. It is finite and
irreducible - i.e. all states intercommunicate. Thus they are all
positive recurrent. Clearly they all have period 2.

${}$

Now $p_{66}^(2)=1$ and clearly $\mu_6=2$.

For state 4, paths of return are as follows:

$4-6-4\ \left(\rm{prob}\ \ds \frac{1}{2}\right)\ \ 4-6-5-6-4\
\left(\rm{prob}\ \ds \frac{1}{4}\right)\ \ 4-6-5-6-5-6-4
\left(\rm{prob}\ \ds \frac{1}{8}\right)$ etc.

so

$\begin{array}{rcl} \mu_4 & = & 2 \times \ds \frac{1}{2}+4\times
\ds \frac{1}{4}+6\times \ds \frac{1}{8}+8\times \ds
\frac{1}{16}+\cdots+2n\times \ds \frac{1}{2}n+\cdots\\ 2\mu_4 & =
& 2+4\times \ds \frac{1}{2}+6\times \ds \frac{1}{4}+8\times \ds
\frac{1}{8}+10\times \ds \frac{1}{16}+\cdots\\ & & +(2n+2)\times
\ds \frac{1}{2}n+\cdots\\ \mu_4 & = & 2+2\times \ds
\frac{1}{2}+2\times \ds \frac{1}{4}+2\times \ds
\frac{1}{8}+2\times \ds \frac{1}{16}+\cdots = 4\end{array}$

Also $\mu_5=4$ by symmetry.

${}$

Occupancy proportions are the reciprocal of mean recurrence times
so for state 6 $\ds \frac{1}{2}$ the time and for states 4 and 5
$\ds \frac{1}{4}$ each.

After one minute (i.e. one operation) 1 lamp is off. If it is to
remain off then the other lamp must be chosen on each of the $k-1$
subsequent occasions i.e. probability $\ds \frac{1}{2^{k-1}}$.


\end{document}