Problems

Show that if $\operatorname {Var}\left[X\right] = 0$ then $X$ is almost surely constant; that is, there exists $a \in \mathbb {R}$ such that $\mathbb {P}\left(X = a\right) = 1$. (First show that if $\mathbb {E}\left[X^{2}\right] = 0$ then $\mathbb {P}\left(X = 0\right) = 1$.)

Let $\Omega = \left\{ \omega_{1}, \omega_{2}, \omega_{3}\right\}$, with $\mathbb {P}\left(\omega_{1}\right) = \mathbb {P}\left(\omega_{2}\right) = \mathbb {P}\left(\omega_{3}\right) = \frac{1}{3}$. Define $X, Y, Z: \Omega \rightarrow \mathbb {R}$ by

Show that $X$ and $Y$ have the same mass functions. Find the mass functions of $X+Y, X Y$, and $X / Y$. Find the conditional mass functions $f_{Y \mid Z}$ and $f_{Z \mid Y}$.

For what values of $k$ and $\alpha$ is $f$ a mass function, where:

Let $X$ and $Y$ be independent Poisson variables with respective parameters $\lambda$ and $\mu$. Show that:

If $X$ is geometric, show that $\mathbb {P}\left(X = n+k \mid X > n\right) = \mathbb {P}\left(X = k\right)$ for $k, n \geq 1$. Why do you think that this is called the 'lack of memory' property? Does any other distribution on the positive integers have this property?

Show that the sum of two independent binomial variables, $\operatorname {bin}(m, p)$ and $\operatorname {bin}(n, p)$ respectively, is $\operatorname {bin}(m+n, p)$.

Let $N$ be the number of heads occurring in $n$ tosses of a biased coin. Write down the mass function of $N$ in terms of the probability $p$ of heads turning up on each toss. Prove and utilize the identity

in order to calculate the probability $p_{n}$ that $N$ is even. Compare with Problem (1.8.20).

An urn contains $N$ balls, $b$ of which are blue and $r( = N-b)$ of which are red. A random sample of $n$ balls is withdrawn without replacement from the urn. Show that the number $B$ of blue balls in this sample has the mass function

This is called the hypergeometric distribution with parameters $N, b$, and $n$. Show further that if $N, b$, and $r$ approach $\infty$ in such a way that $b / N \rightarrow p$ and $r / N \rightarrow 1-p$, then

You have shown that, for small $n$ and large $N$, the distribution of $B$ barely depends on whether or not the balls are replaced in the urn immediately after their withdrawal.

Let $X$ and $Y$ be independent $\operatorname {bin}(n, p)$ variables, and let $Z = X+Y$. Show that the conditional distribution of $X$ given $Z = N$ is the hypergeometric distribution of Problem (3.11.10).

Suppose $X$ and $Y$ take values in $\left\{ 0,1\right\}$, with joint mass function $f(x, y)$. Write $f(0,0) = a$, $f(0,1) = b, f(1,0) = c, f(1,1) = d$, and find necessary and sufficient conditions for $X$ and $Y$ to be:

Let $X_{1}, X_{2}, \ldots , X_{n}$ be independent random variables, and suppose that $X_{k}$ is Bernoulli with parameter $p_{k}$. Show that $Y = X_{1}+X_{2}+\cdots +X_{n}$ has mean and variance given by

Show that, for $\mathbb {E}\left[Y\right]$ fixed, $\operatorname {Var}\left[Y\right]$ is a maximum when $p_{1} = p_{2} = \cdots = p_{n}$. That is to say, the variation in the sum is greatest when individuals are most alike. Is this contrary to intuition?

Let $\mathbf{X} = \left(X_{1}, X_{2}, \ldots , X_{n}\right)$ be a vector of random variables. The covariance matrix $\mathbf{V}(\mathbf{X})$ of $\mathbf{X}$ is defined to be the symmetric $n$ by $n$ matrix with entries $\left(v_{i j}: 1 \leq i, j \leq n\right)$ given by $v_{i j} = \operatorname {Cov}\left[X_{i}, X_{j}\right]$. Show that $\left|\mathbf{V}(\mathbf{X})\right| = 0$ if and only if the $X_{i}$ are linearly dependent with probability one, in that $\mathbb {P}\left(a_{1} X_{1}+a_{2} X_{2}+\cdots +a_{n} X_{n} = b\right) = 1$ for some $\mathbf{a}$ and $b$. $(\left|\mathbf{V}\right|$ denotes the determinant of $\mathbf{V}$.)

Let $X$ and $Y$ be independent Bernoulli random variables with parameter $\frac{1}{2}$. Show that $X+Y$ and $\left|X-Y\right|$ are dependent though uncorrelated.

A secretary drops $n$ matching pairs of letters and envelopes down the stairs, and then places the letters into the envelopes in a random order. Use indicators to show that the number $X$ of correctly matched pairs has mean and variance 1 for all $n \geq 2$. Show that the mass function of $X$ converges to a Poisson mass function as $n \rightarrow \infty$.

Let $\mathbf{X} = \left(X_{1}, X_{2}, \ldots , X_{n}\right)$ be a vector of independent random variables each having the Bernoulli distribution with parameter $p$. Let $f:\left\{ 0,1\right\}^{n} \rightarrow \mathbb {R}$ be increasing, which is to say that $f(\mathbf{x}) \leq f(\mathbf{y})$ whenever $x_{i} \leq y_{i}$ for each $i$.

Let $R(p)$ be the reliability function of a network $G$ with a given source and sink, each edge of which is working with probability $p$, and let $A$ be the event that there exists a working connection from source to sink. Show that

where $\omega$ is a typical realization (i.e. outcome) of the network, $N(\omega )$ is the number of working edges of $\omega$, and $m$ is the total number of edges of $G$.

Deduce that $R^{\prime }(p) = \operatorname {Cov}\left[I_{A}, N\right] /\left\{ p(1-p)\right\}$, and hence that

Let $R(p)$ be the reliability function of a network $G$, each edge of which is working with probability $p$.

In a certain style of detective fiction, the sleuth is required to declare "the criminal has the unusual characteristics...; find this person and you have your man". Assume that any given individual has these unusual characteristics with probability $10^{-7}$ independently of all other individuals, and that the city in question contains $10^{7}$ inhabitants. Calculate the expected number of such people in the city.

In 1710, J. Arbuthnot observed that male births had exceeded female births in London for 82 successive years. Arguing that this showed the two sexes cannot be equally likely, since $2^{-82}$ is very small, he attributed this run of masculinity to Divine Providence. Let us assume that each birth results in a girl with probability $p = 0.485$, and that the outcomes of different confinements are independent of each other. Ignoring the possibility of twins (and so on), show that the probability that girls outnumber boys in $2 n$ live births is no greater than $\binom {2 n}{n} p^{n} q^{n}\left\{ q /(q-p)\right\}$, where $q = 1-p$. Suppose that 20,000 children are born in each of 82 successive years. Show that the probability that boys outnumber girls every year is at least 0.99. You may need Stirling's formula.

Consider a symmetric random walk with an absorbing barrier at $N$ and a reflecting barrier at 0 (so that, when the particle is at $0$, it moves to 1 at the next step). Let $\alpha_{k}(j)$ be the probability that the particle, having started at $k$, visits 0 exactly $j$ times before being absorbed at $N$. We make the convention that, if $k = 0$, then the starting point counts as one visit. Show that

Problem of the points (3.9.4). A coin is tossed repeatedly, heads turning up with probability $p$ on each toss. Player A wins the game if heads appears at least $m$ times before tails has appeared $n$ times; otherwise player B wins the game. Find the probability that A wins the game.

A coin is tossed repeatedly, heads appearing on each toss with probability $p$. A gambler starts with initial fortune $k$ (where $0 < k < N$); he wins one point for each head and loses one point for each tail. If his fortune is ever 0 he is bankrupted, whilst if it ever reaches $N$ he stops gambling to buy a Jaguar. Suppose that $p < \frac{1}{2}$. Show that the gambler can increase his chance of winning by doubling the stakes. You may assume that $k$ and $N$ are even.

What is the corresponding strategy if $p \geq \frac{1}{2}$?

A compulsive gambler is never satisfied. At each stage he wins $£ 1$ with probability $p$ and loses $£ 1$ otherwise. Find the probability that he is ultimately bankrupted, having started with an initial fortune of $£ k$.

Let $\left\{ X_{n}: n \geq 1\right\}$ be independent, identically distributed random variables taking integer values. Let $S_{0} = 0, S_{n} = \sum_{i = 1}^{n} X_{i}$. The range $R_{n}$ of $S_{0}, S_{1}, \ldots , S_{n}$ is the number of distinct values taken by the sequence. Show that $\mathbb {P}\left(R_{n} = R_{n-1}+1\right) = \mathbb {P}\left(S_{1} S_{2} \cdots S_{n} \neq 0\right)$, and deduce that, as $n \rightarrow \infty$,

Hence show that, for the simple random walk, $n^{-1} \mathbb {E}\left[R_{n}\right] \rightarrow \left|p-q\right|$ as $n \rightarrow \infty$.

Arc sine law for maxima. Consider a symmetric random walk $S$ starting from the origin, and let $M_{n} = \max \left\{ S_{i}: 0 \leq i \leq n\right\}$. Show that, for $i = 2 k, 2 k+1$, the probability that the walk reaches $M_{2 n}$ for the first time at time $i$ equals $\frac{1}{2} \mathbb {P}\left(S_{2 k} = 0\right) \mathbb {P}\left(S_{2 n-2 k} = 0\right)$.

Let $S$ be a symmetric random walk with $S_{0} = 0$, and let $N_{n}$ be the number of points that have been visited by $S$ exactly once up to time $n$. Show that $\mathbb {E}\left[N_{n}\right] = 2$.

Consider the following fragment of verse entitled 'Note for the scientist'.

People who have three daughters try for more, And then its fifty-fifty they'll have four, Those with a son or sons will let things be, Hence all these surplus women, QED.

Let $\beta > 1$, let $p_{1}, p_{2}, \ldots$ denote the prime numbers, and let $N_1, N_2, \ldots$ be independent random variables, $N_i$ having mass function $\mathbb {P}\left(N_i = k\right) = \left(1-\gamma_{i}\right) \gamma_{i}^{k}$ for $k \geq 0$, where $\gamma_{i} = p_{i}^{-\beta }$ for all $i$. Show that $M = \prod_{i = 1}^{\infty } p_{i}^{N_i}$ is a random integer with mass function $\mathbb {P}\left(M = m\right) = C m^{-\beta }$ for $m \geq 1$ (this may be called the Dirichlet distribution), where $C$ is a constant satisfying

$N+1$ plates are laid out around a circular dining table, and a hot cake is passed between them in the manner of a symmetric random walk: each time it arrives on a plate, it is tossed to one of the two neighbouring plates, each possibility having probability $\frac{1}{2}$. The game stops at the moment when the cake has visited every plate at least once. Show that, with the exception of the plate where the cake began, each plate has probability $1 / N$ of being the last plate visited by the cake.

There are $\binom {n}{m}$ points ranked in order of merit with no matches. You seek to reach the best, $B$. If you are at the $j$ th best, you step to any one of the $j-1$ better points, with equal probability of stepping to each. Let $r_{j}$ be the expected number of steps to reach $B$ from the $j$ th best vertex. Show that $r_{j} = \sum_{k = 1}^{j-1} k^{-1}$. Give an asymptotic expression for the expected time to reach $B$ from the worst vertex, for large $m, n$.

There are $n$ unstable molecules in a row, $m_{1}, m_{2}, \ldots , m_{n}$. One of the $n-1$ pairs of neighbours, chosen at random, combines to form a stable dimer; this process continues until there remain $U_{n}$ isolated molecules no two of which are adjacent. Show that the probability that $m_{1}$ remains isolated is $\sum_{r = 0}^{n-1}(-1)^{r} / r! \rightarrow e^{-1}$ as $n \rightarrow \infty$. Deduce that $\lim_{n \rightarrow \infty } n^{-1} \mathbb {E}\left[U_{n}\right] = e^{-2}$.

Let $\left\{ I_{r}: 1 \leq r \leq n\right\}$ be independent Bernoulli random variables with respective parameters $\left\{ p_{r}: 1 \leq r \leq n\right\}$ satisfying $p_{r} \leq c < 1$ for all $r$ and some $c$. Let $\lambda = \sum_{r = 1}^{n} p_{r}$ and $X = \sum_{r = 1}^{n} X_{r}$. Show that

The length of the tail of the $r$ th member of a troop of $N$ chimeras is $x_{r}$. A random sample of $n$ chimeras is taken (without replacement) and their tails measured. Let $I_{r}$ be the indicator of the event that the $r$ th chimera is in the sample. Set

Show that $\mathbb {E}\left[\bar{Y}\right] = \mu$, and $\operatorname {Var}\left[\bar{Y}\right] = (N-n) \sigma^{2} /\left\{ n(N-1)\right\}$.

Any individual in a group $G$ contracts a certain disease $C$ with probability $\gamma$; such individuals are hospitalized with probability $c$. Independently of this, anyone in $G$ may be in hospital with probability $a$, for some other reason. Let $X$ be the number in hospital, and $Y$ the number in hospital who have $C$ (including those with $C$ admitted for any other reason). Show that the correlation between $X$ and $Y$ is

where $p = a+c-a c$. It has been stated erroneously that, when $\rho (X, Y)$ is near unity, this is evidence for a causal relation between being in $G$ and contracting $C$.

A telephone sales company attempts repeatedly to sell new kitchens to each of the $N$ families in a village. Family $i$ agrees to buy a new kitchen after it has been solicited $K_{i}$ times, where the $K_{i}$ are independent identically distributed random variables with mass function $f(n) = \mathbb {P}\left(K_{i} = n\right)$. The value $\infty$ is allowed, so that $f(\infty ) \geq 0$. Let $X_{n}$ be the number of kitchens sold at the $n$th round of solicitations, so that $X_{n} = \sum_{i = 1}^{N} I_{\left\{ K_{i} = n\right\} }$. Suppose that $N$ is a random variable with the Poisson distribution with parameter $v$.

A particle performs a random walk on the non-negative integers as follows. When at the point $n$ $( > 0)$ its next position is uniformly distributed on the set $\left\{ 0,1,2, \ldots , n+1\right\}$. When it hits 0 for the first time, it is absorbed. Suppose it starts at the point $a$.

Let $G$ be a finite graph with neither loops nor multiple edges, and write $d_{v}$ for the degree of the vertex $v$. An independent set is a set of vertices no pair of which is joined by an edge. Let $\alpha (G)$ be the size of the largest independent set of $G$. Use the probabilistic method to show that $\alpha (G) \geq \sum_{v} 1 /\left(d_{v}+1\right)$.

Kelly betting, or proportional investment. A gambler (or 'investor') makes a sequence of bets of the following type: on each bet, for a given stake $S$, the return is either the loss of the stake with probability $q( = 1-p)$ or a win totalling $(1+r) S$ with probability $p$. (Assume the usual independence.) The entry fee is $c S$ where $c < r$. Show that the mean gain per play for stake $S$ is $g S$, where $g = p r-q-c$ (with a negative value indicating a loss).

The gambler decides to bet a fixed fraction $f$ of her current fortune at each stage. That is, given a current fortune $F$, she bets $f F$ for some fixed $f$. Show that her resulting fortune is

where $I$ is the indicator function of a win. Suppose $p > (1+c) /(1+r)$. The gambler considers two policies for choosing $f$ : for given $F$,

Let $x_{1}, x_{2}, \ldots , x_{r}$ be given reals with $r \geq 2$, and let the sequence $\left\{ X_{n}: n \geq 1\right\}$ of random variables be given as follows. First, $X_{n} = x_{n}$ for $n \leq r$. For $n \geq r$, we set $X_{n+1} = X_{U_{n}}+X_{V_{n}}$ where $U_{n}, V_{n}$ are uniformly distributed on $\left\{ 1,2, \ldots , n\right\}$, and the family $\left\{ U_{n}, V_{n}: n \geq r\right\}$ are independent. Show that

Enthusiasts may care to show that, when $r = 1 = x_{1}$ and $n \rightarrow \infty$,

Let $X_{1} = 1$. For $n \geq 1$, let $X_{n+1} = X_{U_{n}}-X_{V_{n}}$ where $U_{n}, V_{n}$ are uniformly distributed on $\left\{ 1,2, \ldots , n\right\}$, and the family $\left\{ U_{n}, V_{n}: n \geq 1\right\}$ are independent. Show that

You may find it useful to recall Euler's sine formula:

Gollum has concealed the ring of power in a box chosen randomly from a row of $n \geq 1$ such boxes. Bilbo opens a box at random. If the ring is not there, his occult powers are sufficient for him to learn whether the ring lies to the right or the left, and he opens further boxes accordingly. Find an expression for the mean number $b_{n}$ of boxes opened before finding the ring, and deduce that $b_{n} \sim 2 \log n$ as $n \rightarrow \infty$.

In a variant of the previous problem, we have $n = 2^{r}-1$, and Bilbo invariably chooses the middle box. Find the mean number $m_{r}$ of boxes inspected, and the asymptotics of $m_{r}$ as $r \rightarrow \infty$.

A bad fairy has cursed you. A good fairy has concealed the magic word that cancels the curse in one of $n$ numbered boxes, and she has told you that it is in box $i$ with probability $p_{i}$, for $i = 1,2, \ldots , n$. Each day you are permitted to look in one box.

Gwen and John play 'best of $2 n+1$ games', and play stops as soon as either has won $n+1$ games. Gwen wins each game with probability $\gamma \in (0,1)$ and John otherwise (with probability $\delta = 1-\gamma$). Different games have independent winners. Write down an expression for the probability $f_{r}$ that Gwen wins $r$ games altogether, given that John has won the match, and deduce that $r f_{r} = (n+r) \gamma f_{r-1}$ for $0 < r \leq n$.

Hence or otherwise, prove that the mean total number $T_{n}$ of games in the match is

where $P_{n}$ is the probability that Gwen wins the match. When $p = \frac{1}{2}$, show that

Let $S(n, k)$ be the number of ways to partition $N = \left\{ 1,2, \ldots , n\right\}$ into $k$ non-empty parts. Suppose each element of $N$ is coloured with one of $c$ distinct colours. Prove that

Deduce that the $n$th moment of the Poisson distribution with parameter 1 equals the number $b_{n}$ of ways to partition $N$, that is, $b_{n} = \sum_{k = 1}^{n} S(n, k)$.

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.

Let $X, Y$ be discrete random variables with respective mass functions $f_{X}, f_{Y}$, and joint mass function $f_{X, Y}$. Define the:

Let $\beta > 1$, and let $M, L$ be independent random variables with the Dirichlet distribution with parameter $\beta$ of Problem (3.11.31).

A strict Oxford secret is a secret which you may tell to no more than one other person. Of a group of $n+1$ Oxonians, one learns a strict secret. In accordance with the rules, she tells it to one other person selected uniformly at random from the rest of the group. Each confidante tells the secret to exactly one person picked at random from the rest of the group, excluding the person from whom they heard the secret. When someone who already knows the secret hears it repeated, the entire process ceases.

Let $S$ be the total number of people who eventually know the secret. Find the distribution of $S$, and show that

With $n^{\underline{r}}$ denoting $n!/(n-r)$ !, you may find it useful that

From a pack of $n$ cards, two different cards are selected randomly, and they are transposed. Let $p_{r}$ be the probability that any given card (say, the top card) is in its original position after $r > 0$ such independent transpositions.