MATH 303 2016WT2

Back

Question 1

Consider the Markov chain with state space \(\{0, 1, 2\}\) and transition matrix

\[\mathbf{P}=\begin{array}{c|ccc} & 0 & 1 & 2 \\ \hline 0 & \frac{1}{2} & \frac{1}{2} & 0 \\ 1 & \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 2 & \frac{1}{6} & \frac{1}{2} & \frac{1}{3} \end{array}\]

  1. Suppose \(X_0 = 0\). Find the probability that \(X_2 = 2\).

  2. Find the stationary distribution of the Markov chain.

  3. What proportion of time does the Markov Chain spend in state 2, in the long run?

  4. Suppose \(X_5 = 1\). What is the expected additional number of steps (after time 5) until the first time the Markov chain will return to state \(1\)?

Solution

  1. The only walk from 0 to 2 of length 2 is \(0\to 1\to 2\), so \[\begin{align} p_{02}^{(2)} = p_{01}p_{12} = \frac{1}{2}\cdot \frac{1}{2} = \frac{1}{4} \end{align}\]

  2. We can observe that the detailed balance equations does not hold for this transition matrix since \(p_{02} = 0\) and \(p_{20} > 0\) implies that the only solution to detailed balance is the zero-vector, which is not a distribution. Thus, we solve \(\pi p = \pi\), \(\sum_k \pi_k = 1\). \[\begin{align} \pi_0 &= \frac{1}{2}\pi_0 + \frac{1}{3}\pi_1 + \frac{1}{6}\pi_2 \\ \pi_1 &= \frac{1}{2}\pi_0 + \frac{1}{3}\pi_1 + \frac{1}{2}\pi_2 \\ \pi_2 &= \frac{1}{3}\pi_1 + \frac{1}{3}\pi_2 \\ \pi_0 + \pi_1 + \pi_2 = 1 \end{align}\] the unique solution is \(\pi = (\frac{5}{7}, \frac{3}{7}, \frac{3}{14})\)

  3. The chain is irreducible and finite. by the big theorem, the proportion of time spent in state 2 is \(\pi_2 = \frac{3}{14}\)

  4. Once again, by the big theorem, the expected time of returning to 1 is \(1/\pi_1 = \frac{7}{3}\).

Question 2

Four black balls and four white balls are divided between urn 1 and urn 2, with four balls in each urn. At each time step, a ball is chosen from each of the two urns, then the ball from urn 1 is placed in urn 2, and the ball from urn 2 is placed in urn 1. Let \(X_n\) denote the number of white balls in urn 1 after the nth step. This defines a Markov chain.

  1. Determine the one-step transition matrix for this Markov chain.

  2. Using any method, determine the stationary distribution for the chain. (If you guess the distribution, be sure to verify that your guess is correct.)

Solution

  1. \[P = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ \frac{1}{16} & \frac{3}{8} & \frac{9}{16} & 0 & 0 \\ 0 & \frac{1}{4} & \frac{1}{2} & \frac{1}{4} & 0 \\ 0 & 0 & \frac{9}{16} & \frac{3}{8} & \frac{1}{16} \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix}\]

  2. We use the detailed balance equations. \[\begin{align} \pi_0 &= \frac{1}{16}\pi_1 & \frac{9}{16}\pi_1 &= \frac{1}{4}\pi_2 & \frac{1}{4}\pi_2 &= \frac{9}{16}\pi_3 & \frac{1}{16}\pi_3 &= \pi_4 \end{align}\] \[\begin{align} \sum_{k=0}^{4} \pi_k = \left( 1 + 16 + 36 + 16 + 1 \right)\pi_0 = 70\pi_0 = 1 \end{align}\] \[\begin{align} \pi_0 &= \pi_4 = \frac{1}{70} & \pi_1 &= \pi_3 = \frac{8}{35} & \pi_2 &= \frac{18}{35} \end{align}\]

Question 3

Each day an individual is in an active or inactive state. An active day is followed by an inactive day with probability \(\alpha\), and an inactive day is followed by an active day with probability \(\beta\). This defines a Markov Chain with states “active” and “inactive.”

  1. Draw the transition diagram for the Markov Chain.

  2. Determine the stationary distribution of the Markov Chain.

  3. Now suppose there are 10 such individuals, whose states change independently. What is the long run proportion of time that there are \(j\) active individuals, for \(j = 0,1,\ldots,10\). (Explain or prove your answer.)

Solution
  1. Denote \(0 :=\) inactive and \(1 :=\) active.
MATH 303 2016WT2 Q3a

  1. We use the detailed balance equations. \[\begin{align} \beta\pi_0 &= \alpha\pi_1 \\ \beta\pi_0 &= \alpha (1 - \pi_0) \\ \pi_0 &= \frac{\alpha}{\alpha + \beta},\quad \pi_1 = \frac{\beta}{\alpha + \beta} \end{align}\]

  2. In the long run, the fraction of time an individual is active is \(\pi_1\), so the proportion of time that \(j\) individuals are active out of 10 is \[\begin{align} P(\mbox{Bin}(10, \pi_1) = j) = \binom{10}{j}\left( \frac{\alpha}{\alpha + \beta} \right)^{j}\left( \frac{\beta}{\alpha + \beta} \right)^{10 - j} \end{align}\]

Question 4

Suppose that \(X, Y\) are independent exponential random variables with parameter \(\lambda\).

  1. Find \(P(X < 2Y)\).

  2. Find \(P(X > a \mid X < 2Y)\).

  3. Which of the following is a correct formula for \(E(X^2\mid X > 1)\)? \(E[(X + 1)^2], (EX + 1)^2, EX^2 + 1\). Give a brief reason for your answer

Solution
  1. We compute \(P(X < 2Y)\) directly.

\[\begin{align} P(X < 2Y) &= \int_{0}^{\infty}\int_{0}^{2y} \lambda^2 e^{-\lambda x}e^{-\lambda y} dxdy \\ &= \int_{0}^{\infty} \lambda (1 - e^{-2\lambda y})e^{-\lambda y} dy \\ &= 1 - \frac{1}{3} \\ &= \frac{2}{3} \end{align}\]

  1. We compute \(P(X > a \mid X < 2Y)\) directly.

\[\begin{align} P(X > a \mid X < 2Y) &= \frac{P(a < X < 2Y)}{P(X < 2Y)} \\ P(a < X < 2Y) &= \int_{a}^{\infty}\int_{a}^{2y} \lambda^2 e^{-\lambda x}e^{-\lambda y} dxdy \\ &= \int_{a}^{\infty} \lambda (e^{-\lambda a} - e^{-2\lambda y})e^{-\lambda y} dy \\ &= e^{-2\lambda a} - \frac{1}{3}e^{-2\lambda a} \\ &= \frac{2}{3}e^{-2\lambda a} \\ P(X > a\mid X < 2Y) &= e^{-2\lambda a} = P(\mbox{Exp}(2\lambda) > a) \end{align}\]

This implies that \((X\mid X < 2Y)\sim \mbox{Exp}(2\lambda)\).

  1. \(E[X^2 \mid X > 1] = E[(1 + (X - 1))^2 \mid X > 1]\). By memorylessness, \(((X - 1)^2\mid X > 1) \sim \mbox{Exp}(\lambda)\). Thus, \(E[X^2 \mid X > 1] = E[(X + 1)^2]\).

Question 5

Each customer who enters a certain business must be served first by server 1, then by server 2, and finally by server 3. The amount of time it takes to be served by server i is an exponential random variable with rate \(\mu_i\) (\(i = 1,2,3\)). Suppose you enter the system at a time when it contains a single customer who is being served by server 3.

  1. What is the probability that server 3 will still be busy when you move over to server 2?

  2. What is the probability that server 3 will still be busy when you move over to server 3?

  3. Suppose that \(\mu_1 = \mu_3 = 1\) and \(\mu_2 = 2\). Find the expected time that you spend in the system.

Solution

  1. \(P(T_1 < T_3) = \frac{\mu_1}{\mu_1 + \mu_3}\)

  2. \(P(T_1 + T_2 < T_3) = \frac{\mu_1}{\mu_1 + \mu_3}\cdot \frac{\mu_2}{\mu_2 + \mu_3}\)

  3. We condition on the event that server 3 is still busy when you move over to server 3:

\[\begin{align} P(T_1 + T_2 < T_3') &= \frac{1}{2}\cdot \frac{2}{3} = \frac{1}{3} \\ E[T] &= E[T\mid T_1 + T_2 > T_3']P(T_1 + T_2 \geq T_3') + E[T\mid T_1 + T_2 < T_3']P(T_1 + T_2 < T_3') \\ &= (1 + 1/2 + 1)\frac{2}{3} + (1 + 1/2 + 2)\frac{1}{3} \\ &= 17/6 \end{align}\]

Question 6

A system receives shocks according to a Poisson process with rate \(\lambda\). Each shock independently causes the system to fail with probability \(p\). Let \(T\) denote the failure time of the system, and let \(N\) be the number of shocks received up to and including time \(T\).

  1. Suppose that \(N = n\). What is the conditional distribution (name and parameter(s)) of \(T\)?

  2. Suppose that a failed system is always immediately replaced by a new system. What is the distribution (name and parameter(s)) of the number of replacements that occur during a fixed time interval \([0, t]\)?

  3. Suppose that 5 shocks occur during \([0, t]\). What is the distribution (name and parameter(s)) of the number of replacements during \([0, t]\)?

  4. Given that \(T = t\), what is the conditional distribution (name and parameter(s)) of \(N\)?

Solution

  1. Given the number of shocks \(n\), the failure time is simply the time it takes to receive \(n\) shocks, which is \(T_1 + T_2 + \cdots + T_n \sim \mbox{Gamma}(n, \lambda)\).

  2. The number of replacements is the number of fatal shocks received by time \(t\) is \(N_1(t) \sim \mbox{Poisson}(\lambda p t)\).

  3. \(\mbox{Bin}(5, p)\)

  4. There is only 1 fatal shock at time \(t\) and all shocks before \(t\) are nonfatal, so \((N\mid T = t) \sim \mbox{Poisson}(\lambda (1-p)t) + 1\).

Question 7

A service centre consists of two servers, each working at an exponential rate of two services per hour. Customers require service by one server (not both), and are served in order of arrival. Customers arrive at rate three per hour, and the system has total capacity of at most three customers. This defines a birth and death chain.

  1. What are the birth and death rates?

  2. Determine the limiting probabilities.

  3. What fraction of potential customers are lost?

Solution

  1. The birth rate is \(\lambda_i = 3\) for \(i = 0,1,2\) and the death rate is \(\mu_1 = 2\) and \(\mu_i = 4\) for \(i = 2, 3\).

  2. We can use the results from a previous note to find

\[\begin{align} P_1 &= \frac{3}{2}P_0 \\ P_2 &= \frac{3}{4}\frac{3}{2}P_0 \\ P_3 &= \frac{3}{4}\frac{3}{4}\frac{3}{2}P_0 \end{align}\]

\[\begin{align} P_0 &= \frac{4}{61} & P_1 &= \frac{12}{61} & P_2 &= \frac{18}{61} & P_3 &= \frac{27}{61} \end{align}\]

  1. The fraction of potential customers lost is \(P_3\cdot \frac{3}{3 + 2} = \frac{81}{305}\).

Question 8

A factory has four machines and a single repair technician. For each machine, the operating time until failure is an exponential random variable with rate \(\frac{1}{4}\) per hour. The repair time of a failed machine is an exponential random variable with rate \(\frac{1}{2}\) per hour. Up to four machines can be operating at any given time, but at most one machine can be in repair at any time. This defines a birth and death process, where the state is the number of machines that are operating.

  1. Write down the birth and death rates.

  2. Write down the balance equations for the limiting probabilities.

  3. Solve the balance equations to obtain the limiting probabilities.

  4. What proportion of time is the repair technician idle?

Solution

  1. The birth rate is \(\lambda_i = \frac{1}{2}\) for \(i = 0,1,2,3\) and the death rate is \(\mu_i = \frac{1}{4}i\) for \(i = 1,2,3,4\).

  2. The balance equations are

\[\begin{align} \frac{1}{2}P_0 &= \frac{1}{4}P_1 \\ \frac{3}{4}P_1 &= \frac{1}{2}P_0 + \frac{1}{2}P_2 \\ P_2 &= \frac{1}{2}P_1 + \frac{3}{4}P_3 \\ \frac{5}{4}P_3 &= \frac{1}{2}P_2 + P_4 \\ \frac{3}{2}P_4 &= \frac{1}{2}P_3 \end{align}\]

  1. We can solve the equations to obtain

\[\begin{align} P_0 &= \frac{3}{19} & P_1 &= \frac{6}{19} & P_2 &= \frac{6}{19} \\ P_3 &= \frac{4}{19} & P_4 &= \frac{4}{19}. && \end{align}\]

  1. \(\displaystyle P_0 = \frac{3}{19}\).