Coupling argument

Let $f, g: \mathbb {R} \rightarrow \mathbb {R}$ be monotone nondecreasing. Show that for any random variable $X$

provided all the expectations exist.

Let $m$ be the renewal function of an ordinary renewal process $N$ whose interarrival times have finite mean.

Let $\beta , \gamma \in [0,1]$. Bertha and Harold play a game of rackets. Bertha wins the point with probability $\beta$ when she serves, and Harold wins with probability $\gamma$ when he serves. The first player to win $n$ points wins the game, and Bertha serves first. Consider the following rules for changing server.

Show that $X$ is stochastically larger than $Y$ if and only if $\mathbb {E}\left[u(X)\right] \geq \mathbb {E}\left[u(Y)\right]$ for any nondecreasing function $u$ for which the expectations exist.

Let $X$ and $Y$ be Poisson distributed with respective parameters $\lambda$ and $\mu$. Show that $X$ is stochastically larger than $Y$ if $\lambda \geq \mu$.

Show for discrete random variables $X, Y$ that $\mathbb {P}\left(X = Y\right) \leq 1-\frac{1}{2} d_{\mathrm{TV}}(X, Y)$, where $d_{\mathrm{TV}}$ denotes total variation distance.

Show that equality is possible in the inequality of Exercise (4.12.4) in the following sense. For any pair $X, Y$ of discrete random variables, there exists a pair $X^{\prime }$, $Y^{\prime }$ having the same marginal distributions as $X, Y$ such that $\mathbb {P}\left(X^{\prime } = Y^{\prime }\right) = 1-\frac{1}{2} d_{\mathrm{TV}}(X, Y)$.

Let $X$ and $Y$ be indicator variables with $\mathbb {E}\left[X\right]= p, \mathbb {E}\left[Y\right] = q$. What is the maximum possible value of $\mathbb {P}\left(X = Y\right)$, as a function of $p, q$? Explain how $X, Y$ need to be distributed in order that $\mathbb {P}\left(X = Y\right)$ be:

Let $\mathbf{\pi }$ be a positive mass function on the finite set $\Theta$, and let $\mathbf{P}$ be the transition matrix of an irreducible, aperiodic Markov chain with stationary distribution $\mathbf{\pi }$. Let $W = (W(i): i \in \Theta )$ be a vector of random variables such that $\mathbb {P}\left(W(i) = j\right) = p_{i j}$ for $i, j \in \Theta$, and use $W$ as an update rule in the coupling-from-the-past algorithm for sampling from $\pi$.

Let $X$ and $Y$ be independent recurrent birth-death processes with the same parameters (and no explosions). It is not assumed that $X_{0} = Y_{0}$. Show that:

For nonnegative random variables $Z_{1}, \cdots , Z_{m}$, show that $\mathbb {E}\left[Z_{1} Z_{2} \cdots Z_{m}\right]$ is no greater than $\int_{0}^{1} Q_{Z_{1}}(u) Q_{Z_{2}}(u) \cdots Q_{Z_{m}}(u) d u$, with $Q_{Z_{i}}$ the quantile function for $Z_{i}$.

In the notation of Example $\langle 32 \rangle$, show that $\mathbb {E}\left[\Psi (\left|X-Y\right|)\right] \geq \widetilde{\mathbb {P}}\left(\Psi (\left|\tilde{X}-\tilde{Y}\right|)\right)$, for every convex, increasing function $\Psi$ on $\mathbb {R}^{+}$.

Example 32: For a random variable $X$ with distribution function $F_{X}(x): = \mathbb {P}\left(X \leq x\right)$, define its quantile function $q_{X}(u): = \inf \left\{ t : F_{X}(t) \geq u\right\}$ for $0 < u < 1$. Regarded as a random variable on $(0,1)$, equipped with its Borel sigma-field and Lebesgue measure $\widetilde{\mathbb {P}}$, the function $\tilde{X}: = q_{X}(u)$ has the same distribution as $X$. Similarly, if $Y$ has distribution function $F_{Y}$ and quantile function $q_{Y}$, the random variable $\tilde{Y}: = q_{Y}(u)$ has the same distribution as $Y$. Both $\tilde{X}$ and $\tilde{Y}$ are defined on the same $(0,1)$, even though $X$ and $Y$ need not be defined on the same space, giving a coupling of $X$ and $Y$.

Let $P$ and $Q$ be two probability measures defined on the same sigma-field $\mathcal{A}$ of a set $X$. The total variation distance $v = v(P, Q)$ is defined as $\sup_{A \in \mathcal{A}}\left|P A-Q A\right|$.

Prove Lemma $\langle 9 \rangle$ by carrying out on the following steps. Write $R_{A}$ for $\cup_{\alpha \in A} R_{\alpha }$. Argue by induction on the size of $S$.

Lemma 9: Let $\nu$ be a finite measure on a finite set $S$ and $\mu$ be a finite measure on a sigma-field $\mathcal{B}$ on a set $T$. Suppose $\left\{ R_{\alpha }: \alpha \in S\right\}$ is a collection of measurable sets with the domination property that $\nu (A) \leq \mu \left(\cup_{\alpha \in A} R_{\alpha }\right)$ for all $A \subseteq S$. Then there exists a probability kernel $K$ from $S$ to $T$ with $K_{\alpha }$ concentrated on $R_{\alpha }$ for each $\alpha$ and $\sum_{\alpha \in S} \nu \left\{ \alpha \right\} K_{\alpha } \leq \mu$. With no loss of generality, suppose $S = \left\{ 1,2, \ldots , m\right\}$. Check the case $m = 1$. Work from the inductive hypothesis that the result is true for S $< m$.

(Continuation) Let $F(x)$ and $G(x)$ be two distribution functions, with $F(x) < G(x)$ for all $x$. Prove that there exists a probability space and two random variables $\xi$ and $\eta$, defined on this probability space, such that $F(x) = \mathbb {P}\left(\xi \leqslant x\right), G(x) = \mathbb {P}\left(\eta \leqslant x\right)$ and $\xi > \eta$.

Let $\xi$ and $\eta$ be random variables with distribution functions $F(x)$ and $G(x)$ respectively. Prove that

Let $\xi$ and $\eta$ be random variables with distribution functions $F(x)$ and $G(x)$ respectively. Prove that if

for some positive $\varepsilon > 0$, then

Let $\xi$ and $\eta$ be random variables with probability distributions $\mathbf{F}$ and $\mathbf{G}$ respectively. Prove that