Exams

Exams

Final Exam

Problem 0 (Random Walk)

Let $S_n$ be a nearest neighbor simple random walk in $d$ dimensions. It has equal probabilities of going in each direction.

1. In $d=1$, identify the state space of the process, and write down the equation that the stationary probability solves (if it exists).
2. Can you find the stationary probability distribution? Hint. Use the general solution for a difference equation.
3. In $d \leq 2$, is $S_n$ transient, positive recurrent or null recurrent? Hint. It’s the same answer for both $d=1$ and $d=2$. If it’s recurrent, find the expected time to return to the origin.
4. In $d \geq 3$, is $S_n$ transient, positive recurrent or null recurrent? If it’s recurrent, find the expected time to return to the origin.

<div class=pagebreak-before> </div>

Problem 1 (Continuous Time Markov)

Consider a two state continuous time Markov process $X_t$. The rate of going from state $1$ to state $2$ is $1$ and the rate of going from state $2$ to $1$ is 3.

1. Write down a differential equation for the matrix with entries $p_t(i,j)$.

2. Solve the differential equation.

3. If $\Prob(X_0 = 1) = 1/2$ and $\Prob(X_0 = 2) = 1/2$, find $\Prob(X_3 = 2)$.

4. Suppose you’re in state $2$. Let $T$ be the amount of time you have to wait until you jump to state $1$. What is the probability distribution/density/cdf of $T$?

<div class=pagebreak-before> </div>

Problem 2

Let $\pi(x)$ be the stationary probability of a finite irreducible Markov chain. It solves the equation

where $S$ is the state space of your process. Show that if a stationary distribution exists, then $\pi(x) > 0$ for all $x \in S$.

Consider the following population model in continuous time. We have a tribe on some island where the people can eat only after feeding their god, and so when there are $n$ people, the death rate is $n + 1$ because of the fact that they always have to feed one extra person. The rate of birth is proportional to the number of people. In return for the food, if the tribe dies out, the omnipotent being introduces a new person at rate $1$ ($\lambda_0 = 1$).

1. What is the state space for the process?

2. Is this process transient or null recurrent or positive recurrent? Prove your answer.

<div class=pagebreak-before> </div>

Problem 3 (Brownian Motion)

Let $B_t$ be a one dimensional Brownian motion. Let $B_0 = x$.

Let $E$ be the event that the Brownian motion at time $1$ is in the interval $[3,5]$, AND at time $3$ it is at $[5,8]$.

1. Draw a picture of a path of Brownian motion that is in the event $E$.

2. Find the probability of the event $E$. Hint: the probability density function of $B_t$ is given by

   $$p_t(x,y) = \frac{1}{\sqrt{2\pi t}} e^{-(x-y)^2/2t}$$

3. Show that $B_t$ is a martingale.

4. Suppose the starting point $x \in [3,8]$. Let $T_a$ be the stopping time $\inf{ a \colon B_t = a }$. Let $T = \min(T_3,T_8)$. Define

   $$b(x) = \Prob_x( T_3 < T_8 ).$$

   We know that $b(x)$ satisfies a differential equation. Write this down for me. What are $b(0)$ and $b(1)$?

5. Apply the stopping theorem at $T$ to find $b(x)$.

   Hint: This is the probability that $B_t$ hits $3$ before $8$. You should think of this as a Gambler’s ruin problem. You may also solve the differential equation instead.

<div class=pagebreak-before> </div>

Problem 4

A Professor selects a person from a class of 10 students (numbered $1$ through $10$) each time by rolling a 10-sided die. Suppose the students ${1,3,5}$ have already been selected and the number $3$ shows up on the die. Then that roll is discarded, and the Professor rolls again and again until a number that is not $1,3 \OR 5$ shows up.

In general, suppose $k$ students have already been selected. Label them ${a_1,\ldots,a_k}$. Let $T_{k+1}$ be the number of attempts until the first number that is not in ${a_1,\ldots,a_k}$ shows up. Clearly $T_1 = 1$.

Next, let $X_n$ be the number of people selected by the $n$^th roll. Clearly $X_0 = 0, X_1 = 1$. $X_2 = 2$ if the second roll shows a number that didn’t show up on the first roll. Otherwise, $X_2 = 1$.

This was the process I used to select students to do problems on the board on Thursdays.

1. Is $X_n$ a Markov process? If it is a Markov process, find the transition probability $p(i,j)$ for the appropriate values of $i,j$ and if not, prove that it is not a Markov process.

2. What is the probability distribution of $T_k$? In other words give me a density function, probability mass function OR cumulative distribution function for $T_k$.

3. Are ${T_1,\ldots,T_{10}}$ are independent random variables? Explain your answer.

4. Find the expected time until all $10$ have been selected.

5. If I have $n$ students instead of $10$, give me a reasonable estimate for the expected amount of time until all the students have been selected. Hint: You should get some sort of harmonic series at this stage.

<div class=pagebreak-before> </div>

Final exam practice problems

Try redoing all the homework problems and the midterm problems. If you’re having trouble with something, shoot me an email, request a solution or drop by my office.

Problem 1

Let $X_t$ and $Y_t$ be two independent Poisson processes with rate parameters $\lambda_1$ and $\lambda_2$, measuring the number of customers coming into stores $1$ and $2$ respectively.

1. (4 pts) What is the probability that a customer arrives in store 1 before any customer arrives in store 2?
2. (4 pts) What is the probability that in the first hour, a total of exactly four customers have arrived at the two stores?
3. (4 pts) Given that exactly four customers have arrived at the two stores, what is the probability that all four went to store 1?
4. (8 pts) Let $T$ denote the time of arrival of the first customer at store $2$. Then $X_T$ is the number of customers in store $1$ at the time of the first customer arrival at store $2$. Find the probability distribution of $X_T$ (i.e., for each $k$, find $\Prob(X_T = k)$).

Problem 2

Consider a birth and death process with $\lambda_n = 1/(n+1)$ and $\mu_n = 1$.

1. (4 pts) Use the condition for transience to show that it is not transient. $\sum_{n=1}^{\infty} \frac{\mu_1 \cdots \mu_n}{\lambda_1 \cdots \lambda_{n}} < \infty$
2. (4 pts) Use the condition for positive recurrence to show that it is positive recurrent. $\sum_{n=1}^{\infty} \frac{\lambda_0 \cdots \lambda_{n-1}}{\mu_1 \cdots \mu_n} < \infty$
3. (4 pts) What is the stationary probability distribution?
4. (4 pts) What is the time it takes for the chain to return to $0$, given that it started at $0$?
5. (4 pts) Could this be a good population model, say, perhaps for the growth of some alien bacteria competing from some scarce resource? Why or why not? Explain in words.

<div class=pagebreak-before> </div>

Problem 3

Consider the population model with immigration, with parameters $\lambda, \mu \AND \nu$. That is,

1. Use the criterion for transience $\sum_{n=1}^{\infty} \frac{\mu_1 \cdots \mu_n}{\lambda_1 \cdots \lambda_{n}} < \infty$ to show that the chain is transient if $\mu < \lambda$.
2. Interpret the meaning of transience for the population model in words. Does the rate of immigration affect transience or not? Why or why not?
3. Use the criterion for recurrence to show that the process is positive recurrent for $\mu > \lambda$. $\sum_{n=1}^{\infty} \frac{\lambda_0 \cdots \lambda_{n-1}}{\mu_1 \cdots \mu_n} < \infty$ Use the bound $\prod_{i=0}^n (i \lambda + \nu) \leq n! \lambda^n \sum_{i=0}^n \frac{1}{i!} \left( \log n \frac{\nu}{\lambda} \right)^i$
4. What properties of the model could the rate of immigration possibly affect?

Problem 4a (Ethier)

Show that any stationary distribution $\pi$ of an irreducible Markov chain must be strictly positive. Hint: Show that if $\pi(i) = 0$ then $\pi(j) = 0$ whenever $p(j,i) > 0$.

Problem 4b (Ethier)

Give a direct proof that the stationary distribution of an irreducible finite Markov chain is unique. Given stationary distributions $\pi_1$ and $\pi_2$, consider the state $i$ that minimizes $\pi_1(i)/\pi_2(i)$ and show for all $j$ such that $p(j,i) > 0$ have

Then, do the same for all $j$ with $p^2(j,i) > 0$ and so on.

Problem 5

Textbook problems:

1. 8.4
2. 8.9

Midterm 1 (45 pts)

Problem 1 (22 pts)

Suppose an individual can have either $0$ or $2$ children. Suppose the probability of $0$ children is $p$. Let $X$ be the number of children a person can have. Let $X_n$ be the total number of children in the branching process at the $n$ generation. Let $X_0 = 1$.

1. (5 pts) What is the state space of this Markov chain? What are the different communication classes?
2. (2 pts) What is the cumulative distribution function of $X$? What is the mean $\mu$ of $X$?
3. (2 pts) Determine the generating function $\phi(s) = \E[ s^X]$.
4. (2 pts) For what values of $p$ do you expect the branching process to die out?
5. (5 pts) Determine the extinction probability.
6. (2 pts) Classify the communication classes of the chain as recurrent or transient. Does it depend on the value of $p$?
7. (4 pts) Given that $X_{18} = 4$, what is the conditional probability of extinction?

<div class=pagebreak-before> </div>

Problem 2 (13 pts)

A professor continually gives exams to her students. She can give three possible types of exams, and her class is graded as either having done well or badly. Let $p_i$ denote the probability that the class does well on a type $i$ exam, and suppose that $p_1 = 0.3, p_2 = 0.6 \AND p_3 = 0.9$. If the class does well on an exam, then the next exam is equally likely to be any of the three types. If the class does badly, then the next exam is always type $1$.

1. (5 pts) Draw a graph, with arrows and probabilities of the Markov chain. Alternatively, you may also just write down the transition matrix.
2. (8 pts) Suppose the teacher gives a type 1 exam first. What is the average number of exams she has to give before giving an exam of type 2? Hint: Can you make one of the states absorbing?

<div class=pagebreak-before> </div>

Problem 3 (10 pts)

Let $X_n$ and $Y_n$ be two independent copies of a Markov chain with transition probability $p(x,y)$. Let the state space $S$ be infinite, but countable. Let $Z_n = (X_n,Y_n)$.

1. (2 pts) Write down the transition probability function of chain $Z_n$ in terms of $p(x,y)$. That is, find

   $$p((x,y),(a,b)) = \Prob(Z_n = (a,b) | Z_{n-1} = (x,y) )$$

   Hint: use the fact that the chains “step independently”

2. (3 pts) Suppose $\pi(x)$ is the stationary probability of the original chain with transition probability $p(x,y)$. Show that the stationary probability of the $Z_n$ chain is $\pi(x,y) = \pi(x) \pi(y)$ by verifying the equation

   $$\sum_{x,y} \pi(x,y) p((x,y),(a,b)) = \pi(a,b)$$

   Hint: You will need to use part 1 for this.

3. (5 pts) Consider the chain

   $P = \begin{matrix} 1/2 & 1/4 & 1/4 \\ 1/4 & 1/4 & 1/2 \\ 0 & 1/2 & 1/2 \end{matrix}$ Consider $Z_n$ as above with two independent copies of the chain. In the long run, what percentage of the time are both chains in the same state?