UMD Probability Qualifying Exams/Aug2010Probability

Problem 1

Two persons, A and B, are playing a game. If A winsa a round, he gets $4 from B and wins the next round with probability 0.7. If A loses the round, he pays $5 to B and wins the next round with probability 0.5.

(i) Write downt he transition matrix of the Markov chain with two states, {A won the current round, B won the current round} and find the stationary probabilities of the states

(ii) Find $\lim _{n\to \infty }P(A{\text{ has more money after }}n{\text{ rounds than before the game}})$ .

Solution

(i) The Markov transition matrix will be the 2x2 matrix $Q=(q_{ij})$ where $i,j=1$ corresponds to a win for Player A and $i,j=0$ corresponds to a loss for Player A. For example, $q_{11}$ is the probability that Player A wins after winning in the previous hand; $q_{01}$ is the probability that Player A wins after losing in the previous hand; etc. This will give

$Q=\left({\begin{array}{cc}0.7&0.3\\0.5&0.5\end{array}}\right)$

The stationary distribution will be the tuple $\pi =(a,b)$ such that $\pi Q=\pi$ . We can calculate this explicitly:

$(a,b)\left({\begin{array}{cc}0.7&0.3\\0.5&0.5\end{array}}\right)=(a,b)$ yields the following system of equations: $.7a+.5b=a;.3a+.5b=b$ Using the fact that $\pi$ must be a probability (i.e. $a+b=1$ ) we get $a={\frac {5}{8}},b={\frac {3}{8}}$ .

(ii) Since $Q$ is positive, and hence ergodic, then any initial probability distribution will converge to the stationary distribution just calculated, $\pi$ . Thus as $n\to \infty$ Player A will win with probability $5/8$ . Can Player A expect to have more money though? For sufficiently large $n$ we can compute Player A's expected winnings in one round:

$E[{\text{winnings}}]=5/8*4+3/8*(-5)=5/8>0$

Thus Player A should expect to have more money than before the game with probability 1.

Problem 2

(i) Let $X$ be a random variable with zero mean and finite variance $\sigma ^{2}$ . Show that for any $c>0$

$P(X>c)\leq {\frac {\sigma ^{2}}{\sigma ^{2}+c^{2}}}$ .

(ii) Let $\{X_{n},n\geq 1\}$ be a square-integrable martingale with $E(X_{1})=0$ . Show that for any $c>0$

$P(\max _{1\leq i\leq n}X_{i}\geq c)\leq {\frac {var(X_{n})}{var(X_{n})+c^{2}}}$ .

Solution

(i) $P(X\geq c)\leq P(|X|\geq c)=P(|X-E[x]|\geq c)\leq P(|X-E[X]|\geq c+\sigma )\leq {\frac {\sigma ^{2}}{c^{2}+2c\sigma +\sigma ^{2}}}\leq {\frac {\sigma ^{2}}{c^{2}+\sigma ^{2}}}$ were the second-to-last inequality is the standard Chebyshev's inequality.