MATH 5040 exams

Back

Exam IV

Problem 1 (20 pts)

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.

a. (4 pts) What is the probability that a customer arrives in store 1 before any customer arrives in store 2? a. (4 pts) What is the probability that in the first hour, a total of exactly four customers have arrived at the two stores? a. (4 pts) Given that exactly four customers have arrived at the two stores, what is the probability that all four went to store 1? a. (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 (20 pts)

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

a. (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$ a. (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$ a. (4 pts) What is the stationary probability distribution? a. (4 pts) What is the time it takes for the chain to return to $0$, given that it started at $0$? a. (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.

Problem 3 (10 pts, bonus)

You will only get points for this if you get all the questions correct. So attempt only if you’re confident.

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

$\begin{align} \lambda_n & = n \lambda + \nu\\ \mu_n & = n \mu \\ \end{align}$

a. 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$. a. Interpret the meaning of transience for the population model in words. Does the rate of immigration affect transience or not? Why or why not? a. 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$ a. What properties of the model could the rate of immigration possibly affect?

Exam III

Problem 1 (Homework revisited, 18 pts)

Suppose you have a Markov chain on ${0,1,\ldots}$ with the following transition probabilities $p(x,x+1) = \frac{1}{x+2} \AND p(x,0) = \frac{x+1}{x+2}$

(4 pts) What is the probability that you run off to infinity, given that you started at some arbitrary $x$?
(4 pts) Before doing any serious calculations, explain in words whether you expect this chain to be positive recurrent, null recurrent, or transient.
(10 pts) Determine whether the chain positive recurrent, null recurrent, or transient. Show your work.

Problem 2 (Branching process, 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 after $n$ generations.

(5 pts) What is the state space of this Markov chain? How many communication classes are there?
(2 pts) What is the cumulative distribution function of $X$? What is the mean $\mu$ of $X$?
(2 pts) Determine the generating function $\phi(s) = \E[ s^X]$.
(2 pts) For what values of $p$ do you expect the branching process to die out?
(5 pts) Determine the extinction probability.
(2 pts) Classify the communication classes of the chain depending on the value of $p$.
(4 pts) Given that $X_{18} = 5$, what is the conditional probability of extinction?

Exam II

No calculators, textbooks, don’t look into your neighbor’s work, justify your answers, blah blah blah.

Suppose we flip a fair coin repeatedly until we have flipped two consecutive heads. Consider the Markov chain with state space ${0,1,2}$ that keeps track of the length of the current “heads streak”. If $X_0 = 0$, then $X_1 = 1$ with probability a half. Then, $X_2 = 0$ if a tails shows up. If a heads shows up instead, then $X_2 = 2$ and the chain terminates.
- Draw the transition matrix of the Markov chain in the standard form.
- What are the recurrent and transient states of your chain?
- Find the average number of flips until we’ve flipped two consecutive heads.
Consider a gamma random variable $X \sim \textrm{Gamma}(n)$ that has density

$f(x) = \frac{1}{\Gamma(x)} x^{n-1} e^{-x} \quad x \geq 0$ The gamma function is defined as $\Gamma(x) = \int_0^{\infty} x^{n-1} e^{-x} dx$ When $x$ is an integer $n$, the gamma function is the factorial function: $\Gamma(n+1) = n!$

We wish to simulate a gamma random variable using the rejection method, and an exponential random variable $Y \sim \operatorname{Exp}{1/n}$. $Y$ has density $g(x) = \frac{1}{n} \exp( -x/n)$
- Describe the rejection method to simulate $X$, step-by-step.
- Estimate $c$, the best constant that satisfies $\frac{f(x)}{g(x)} \leq c$ Hint: Write the ratio $f(x)/g(x)$ as $\exp(\textrm{something})$. Then find the maximum value of that something using ideas from Calculus I. The value of $c$ you get should be $n^n e^{-(n-1)}/(n-1)!$. You only get points if you show me your work.
- Use Stirling’s formula to simplify this. Stirling’s formula for the factorial says that $n! \approx n^{n+1/2} e^{-n} \sqrt{2\pi}$
- What is the probability of rejection? If $U$ is the uniform random variable in the algorithm, then compute $\Prob\left( U \leq \frac{f(Y)}{c g(Y)} \right)$ where $Y \sim \operatorname{Exp}(1/n)$.
- Let $H$ be the random variable that represents the number of rejections before acceptance happens. What kind of random variable is $H$? How many rejections do you see on average?
- If $n = 100000$, very crudely, (without using a calculator), approximately compute how many rejections will you see on average. I’m only looking for an order of magnitude estimate.

Exam I

No calculators, textbooks, justify your answers, blah blah blah.

Consider the following transition matrix. $\begin{equation} \begin{array}{c|cccccc|} & 0 & 1 & 2 & 3 & 4 & 5\\ \hline \\ 0 & 0.5 & 0 & 0.5 & 0 & 0 & 0\\ 1 & 0 & 0 & 0.25 & 0 & 0 & 0.75\\ 2 & 1 & 0 & 0 & 0 & 0 & 0\\ 3 & 0.25 & 0 & 0 & 0 & 0.75 & 0\\ 4 & 0.25 & 0.25 & 0 & 0.5 & 0 & 0\\ 5 & 0.25 & 0.75 & 0 & 0 & 0 & 0 \end{array} \end{equation}$

a. Draw a graph with arrows along the edges showing the possible transitions between the $6$ states ${0,1,2,3,4,5}$.

a. Identity the different communication classes in the Markov chain. Label them as recurrent or transient. Justify your answer.

a. Draw the transition matrix in the canonical form
```
$$
\begin{equation}
    P= 
    \left(
    \begin{array}{c|c}
        R   &   0   \\
        \hline
        S   &   Q
    \end{array}
    \right)
\end{equation}
$$
where $R$ is the transition matrix of the recurrent states, and $S$ and $T$ correspond to the transition matrix of the transient states.
```
a. Suppose the initial probability vector is given by
```
$$
\begin{align*}
    \phi 
    & = ( \Prob(X_0 = 0), \Prob(X_0 = 1), \Prob(X_0 = 2), \Prob(X_0 = 3), \Prob(X_0 = 4), \Prob(X_0 = 5)) \\
    & = (0.1,0.2, 0.3, 0, 0.2, 0.2)
\end{align*}
$$
What is the probability of being in state $0$ after a long long time?
```
a. What happens to the matrix $Q^n$ as $n \to \infty$? Justify your answer.

a. What is the period of state $0$? Justify your answer by verifying the definition of period. What is the period of state $2$?

a. Suppose you start in state $2$, what is the average amount of time spent in state $2$?

a. Suppose you start in state $2$, what is average number of steps between visits to state $2$?
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$.

Draw a graph, with arrows and probabilities of the Markov chain. Alternatively, you may also just write down the transition matrix.

Arjun Krishnan