# UMD Probability Qualifying Exams/Aug2006Probability
## Problem 1

* Consider a four state Markov chain with state space $\{1,2,3,4\}$, initial state $X_{0}=1$, and transition probability matrix
* ${\begin{pmatrix}1/4&1/4&1/4&1/4\\1/6&1/3&1/6&1/3\\0&0&1&0\\0&0&0&1\end{pmatrix}}$
* (a) Compute $\lim _{n\to \infty }P(X_{n}=3)$.
* (b) Let $\tau =\inf\{n\geq 0:X_{n}\in \{3,4\}\}$. Compute $E(\tau )$.

### Solution
## Problem 2

* If $X_{1},...,X_{n}$ are independent uniformly distributed random variables on [0,1], then let $X_{(2),n}$ be the second smallest among these numbers. Find a nonrandom sequence $a_{n}$ such that $T_{n}=a_{n}-\log X_{(2),n}$ converges in distribution, and compute the limiting distribution.

### Solution

${\begin{aligned}P(T_{n}\leq x)&=P(e^{a_{n}-\log X_{(2),n}}\leq e^{x})=P({\frac {e^{a_{n}}}{X_{(2),n}}}\leq e^{x})\\&=P(X_{(2),n}\geq e^{a_{n}-x})=n(1-e^{a_{n}-x})^{n-1}e^{a_{n}-x}+(1-e^{1_{n}-x})^{n}\end{aligned}}$
The two terms on the right hand side look like the limit definition of the exponential function. Can we choose $a_{n}$ appropriately so that it is?
Let $a_{n}=-\log n$. Then ${\begin{aligned}P(T_{n}\leq x)&=n(1-{\frac {1}{ne^{x}}})^{n-1}{\frac {1}{ne^{x}}}+(1-{\frac {1}{ne^{x}}})^{n}\\&\to e^{-e^{x}}e^{-x}+e^{-e^{x}}\end{aligned}}$
This is the distribution of $\lim _{n\to \infty }T_{n}$.

## Problem 3

* Suppose that the real-valued random variables $\xi ,\eta$ are independent, that $\xi$ has a bounded density $p(x)$ (for $x\in \mathbb {R}$, with respect to Lebesgue measure), and that $\eta$ is integer valued.
* (a) Prove that $\zeta =\xi +\eta$ has a density.
* (b) Calculate the density of $\zeta$ in the case where $\xi \sim$ Uniform[0,1] and $\eta \sim$ Poisson(1).

### Solution

(a)
${\begin{aligned}P(\zeta \leq x)&=P(\xi \leq x-\eta )=\sum _{n=-\infty }^{\infty }P(\eta =n)\int _{-\infty }^{x-n}p_{\xi }(t)\,dt\\&=\lim _{N\to \infty }\sum _{n=-N}^{N}P(\eta =n)\int _{-\infty }^{x-n}p_{\xi }(t)\,dt=\lim _{N\to \infty }\sum _{n=-N}^{N}P(\eta =n)\int _{-\infty }^{x}p_{\xi }(t-n)\,dt\\&=\lim _{N\to \infty }\int _{-\infty }^{x}\sum _{n=-N}^{N}P(\eta =n)p_{\xi }(t-n)\,dt=\int _{-\infty }^{x}\sum _{n=-\infty }^{\infty }P(\eta =n)p_{\xi }(t-n)\,dt\end{aligned}}$
where the last equality follows from Monotone Convergence Theorem.
Hence, we have shown explicitly that $\zeta$ has a density and it is given by $q_{\zeta }(t)=\sum _{n=-\infty }^{\infty }P(\eta =n)p_{\xi }(t-n)$.
(b) When $\xi \sim$ Uniform[0,1] and $\eta \sim$ Poisson(1), we have $p_{\xi }(x)=\mathrm {X} _{[0,1]}(x)$ and $p_{\eta }(k)={\frac {1}{k!e}}$ with support on $k=0,1,2,...$.
Then from part (a), the density will be
$q_{\zeta }(x)=\sum _{n=-\infty }^{\infty }p_{\eta }(n)p_{\xi }(x-n)=\sum _{n=0}^{\infty }{\frac {1}{k!e}}\mathrm {X} _{[0,1]}(x)$.

## Problem 4

* Let $(N(t),t\geq 0)$ be a Poisson process with unit rate, and let
* $W_{m,n}=\sum _{k=1}^{n}I\{N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})\geq 2\}$
* where $I(A)$ is the indicator of the event $A$.
* (a) Find a formula for $E(W_{m,n})$ in terms of $m,n$.
* (b) Show that if $m=n^{\alpha }$ with $\alpha >1/2$ a fixed constant, then $W_{m,n}\to \infty$ in probability.

### Solution
#### (a)

We know that $N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})$ is distributed as Poisson with parameter $m/n$. So
$P(N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})\geq 2)=1-P(N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})=1{\text{ or }}2)=1-e^{-m/n}-{\frac {m}{n}}e^{-m/n}$
Then ${\begin{aligned}E(W_{m,n})&=E[\sum _{k=1}^{n}I(N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})\geq 2)\\&=\sum _{k=1}^{n}E(I(N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})\geq 2)){\text{ by linearity}}\\&=\sum _{k=1}^{n}P(N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})\geq 2)=n\left(1-e^{-m/n}-{\frac {m}{n}}e^{-m/n}\right)=n-e^{-m/n}(n+m)\end{aligned}}$

#### (b)

If $\lim _{n\to \infty }W_{n,n^{\alpha }}=\infty$ then we must have $I(N({\frac {mk}{n}})-N({\frac {m(k-1)}{n}})\geq 2)=0$ only finitely often. The probability of this even (from part a) is $e^{-n^{\alpha -1}}(1+n^{\alpha -1})$.
This decays to 0 for $\alpha >1$. Then clearly, we see that the probability of $\lim _{n\to \infty }W_{n,n^{\alpha }}=\infty$ is equal to 1.
I don't know how to show the result for $1/2<\alpha <1$...

## Problem 5

* Let $X_{0}=0$ and for $n\geq 1,X_{n}=\sum _{j=1}^{n}\xi _{j}$ where the r.v.'s $\xi _{j}$ are i.i.d. with $P(\xi _{j}=-2)=1/4,P(\xi _{j}=1)=3/4$.
* (a) Prove that there exist constants $a,b$ such that $Y_{n}=X_{n}-an$ and $Z_{n}=\exp(bX_{n})$ are martingales.
* (b) If $\tau =\inf\{n\geq 1:X_{n}=3\}$, then prove that $\tau <\infty$ almost surely and find $E(\tau )$.
* (c) Prove that $\exp(bX_{n})$ is not a uniformly integrable martingale.

### Solution
#### (a)

We want $Y_{n}=E[Y_{n+1}|{\mathcal {F}}_{n}]$. We can compute both sides of this equation explicitly.
$X_{n}-an=E[X_{n+1}-a(n+1)|X_{n}]=(X_{n}-2){\frac {1}{4}}+(X_{n}+1){\frac {3}{4}}-a(n+1)=X_{n}+1/4-an-a$
Thus if we want this equality to hold we must have $a=1/4$.
Similarly, if we want $Z_{n}=E[Z_{n+1}|{\mathcal {F}}_{n}]$ then
$e^{bX_{n}}=E[e^{bX_{n+1}}|X_{n}]={\frac {1}{4}}e^{b(X_{n}-2)}+{\frac {3}{4}}e^{b(X_{n}+1)}=e^{bX_{n}}({\frac {1}{4}}e^{-2b}+{\frac {3}{4}}e^{b})$
We can easily check that $b=0$ gives a trivial solution to the equation. Using the substitution $x=e^{b}$ we can find another solution for $b$. We should get $b=\log(1+{\sqrt {13}})-\log(6)<0$.

#### (b)

We've just shown that $Y_{n}=X_{n}-{\frac {1}{4}}n$ is a martingale. Thus, $E[Y_{n}|Y_{0}]=E[Y_{0}]=0$. Then since each $\xi$ is i.i.d., we can apply the Strong Law of Large Numbers to say $1/n(X_{n}-n/4)\to 0$ almost surely. In other words, $X_{n}\to \infty$ almost surely and so certainly $\tau <\infty$ almost surely.
Now to calculate $E[\tau ]$. We introduce new notation: let $\tau _{k}(x)=\inf\{n\geq 1:X_{n}=k,X_{0}=x\}$. Then ${\begin{aligned}E[\tau _{n}(0)]&={\frac {3}{4}}(1+E[\tau _{n}(1)])+{\frac {1}{4}}(1+E[\tau _{n}(-2)])\\&={\frac {3}{4}}(1+E[\tau _{n-1}(0)])+{\frac {1}{4}}(1+E[\tau _{n+2}(0)])=1+{\frac {3}{4}}\tau _{n-1}(0)+{\frac {1}{4}}\tau _{n+2}(0)\end{aligned}}$
by a symmetry argument.
So we can write $E[\tau _{1}(0)]=1+{\frac {3}{4}}0+{\frac {1}{4}}\tau _{3}(0)$. But I don't know how to calculate $E[\tau _{1}(0)]$....

#### (c)

Recall from part (a) that the nontrivial solution for $b$ must be some negative number. Then $\lim _{n\to \infty }Z_{n}\to 1$ almost surely by part (a) as well.
However, $Z_{n}=e^{bX_{n}}\neq 1=E[Z_{\infty }|{\mathcal {F}}_{n}]$. This by the definition, means the martingale is not right closable. A martingale is right-closable iff uniformly integrable. Thus, we're done.