Discrete random variables

For what values of the constant $C$ do the following define mass functions on the positive integers $1,2, \ldots$?

For a random variable $X$ having each of the four mass functions of Exercise (3.1.1), find $\mathbb {P}\left(X > 1\right)$, the most probable value of $X$, and the probability that $X$ is even, when the mass function is:

We toss $n$ coins, and each one shows heads with probability $p$, independently of each of the others. Each coin which shows heads is tossed again. What is the mass function of the number of heads resulting from the second round of tosses?

Let $S_{k}$ be the set of positive integers whose base-10 expansion contains exactly $k$ elements (so that, for example, $1024 \in S_{4}$). A fair coin is tossed until the first head appears, and we write $T$ for the number of tosses required. We pick a random element, $N$ say, from $S_{T}$, each such element having equal probability. What is the mass function of $N$?

Let $X$ and $Y$ be independent random variables, each taking the values $-1$ or $1$ with probability $\frac{1}{2}$, and let $Z = X Y$. Show that $X, Y$, and $Z$ are pairwise independent. Are they independent?

Let $X$ and $Y$ be independent random variables taking values in the positive integers and having the same mass function $f(x) = 2^{-x}$ for $x = 1,2, \ldots$. Find:

Let $X_{1}, X_{2}, X_{3}$ be independent random variables taking values in the positive integers and having mass functions given by $\mathbb {P}\left(X_{i} = x\right) = \left(1-p_{i}\right) p_{i}^{x-1}$ for $x = 1,2, \ldots$, and $i = 1,2,3$.

Three players, $\mathrm{A}, \mathrm{B}$, and C, take turns to roll a die; they do this in the order ABCABCA....

Let $X_{r}, 1 \leq r \leq n$, be independent random variables which are symmetric about 0 ; that is, $X_{r}$ and $-X_{r}$ have the same distributions. Show that, for all $x, \mathbb {P}\left(S_{n} \geq x\right) = \mathbb {P}\left(S_{n} \leq -x\right)$ where $S_{n} = \sum_{r = 1}^{n} X_{r}$.

Is the conclusion necessarily true without the assumption of independence?

Every package of some intrinsically dull commodity includes a small and exciting plastic object. There are $c$ different types of object, and each package is equally likely to contain any given type. You buy one package each day.

Each member of a group of $n$ players rolls a die.

A fair coin is tossed repeatedly. Let $T$ be the number of tosses until the first head. You are offered the following prospect, which you may accept on payment of a fee. If $T = k$, say, then you will receive $£ 2^{k}$. What would be a 'fair' fee to ask of you?

Let $X$ have mass function

and let $\alpha \in \mathbb {R}$. For what values of $\alpha$ is it the case that $\mathbb {E}\left[X^{\alpha }\right] < \infty$?

Show that $\operatorname {Var}\left[a+X\right] = \operatorname {Var}\left[X\right]$ for any random variable $X$ and constant $a$.

Suppose you find a warm-hearted bookmaker offering payoff odds of $\pi (k)$ against the $k$th horse in an $n$-horse race where $\sum_{k = 1}^{n}\left(\pi (k)+1\right)^{-1} < 1$. Show that you can distribute your bets in such a way as to ensure you win.

You roll a conventional fair die repeatedly. If it shows $1$, you must stop, but you may choose to stop at any prior time. Your score is the number shown by the die on the final roll.

Continuing with Exercise (3.3.8), suppose now that you lose $c$ points from your score each time you roll the die. What strategy maximizes the expected final score if $c = \frac{1}{3}$? What is the best strategy if $c = 1$?

Let $G = (V, E)$ be a random graph with $m = \left|V\right|$ vertices and edge-set $E$. Write $d_{v}$ for the degree of vertex $v$, that is, the number of edges meeting at $v$. Let $Y$ be a uniformly chosen vertex, and $Z$ a uniformly chosen neighbour of $Y$.

The gambler Lester Savage makes up to three successive bets that a fair coin flip will show heads. He places a stake on each bet, which, if a head is shown, pays him back twice the stake. If a tail is shown, he loses his stake.

His stakes are determined as follows. Let $x > y > z > 0$. He bets $x$ on the first flip; if it shows heads he quits, otherwise he continues. If he continues, he bets $y$ on the second flip; if it shows heads he quits, otherwise he continues. If he continues, he bets $z$ on the third flip.

Let $G$ be his accumulated gain (positive or negative). List the possible values of $G$ and their probabilities. Show that $\mathbb {E}\left[G\right] = 0$, and find $\operatorname {Var}\left[G\right]$ and $\mathbb {P}\left(G < 0\right)$.

Lester decides to stick with the three numbers $x, y, z$ but to vary their order. How should he place his bets in order to simultaneously minimize both $\mathbb {P}\left(G < 0\right)$ and $\operatorname {Var}\left[G\right]$? Explain.

A set of $n$ different words is equally likely to be in any of the $n$ ! possible orders. It is decided to place them in lexicographic order using the following algorithm.

(i) Compare the first word $w$ with the others, and find the set of earlier words and the set of later words.

(ii) Iterate the procedure on each of the two sets thus obtained.

(iii) Continue until the final ordering is achieved.

An urn contains $n$ balls numbered $1,2, \ldots , n$. We remove $k$ balls at random (without replacement) and add up their numbers. Find the mean and variance of the total.

Of the $2 n$ people in a given collection of $n$ couples, exactly $m$ die. Assuming that the $m$ have been picked at random, find the mean number of surviving couples. This problem was formulated by Daniel Bernoulli in 1768.

Urn R contains $n$ red balls and urn B contains $n$ blue balls. At each stage, a ball is selected at random from each urn, and they are swapped. Show that the mean number of red balls in urn $R$ after stage $k$ is $\frac{1}{2} n\left\{ 1+(1-2 / n)^{k}\right\}$. This 'diffusion model' was described by Daniel Bernoulli in 1769.

Consider a square with diagonals, with distinct source and sink. Each edge represents a component which is working correctly with probability $p$, independently of all other components. Write down an expression for the Boolean function which equals 1 if and only if there is a working path from source to sink, in terms of the indicator functions $X_{i}$ of the events $\left\{ \text{edge }i\text{ is working}\right\}$ as $i$ runs over the set of edges. Hence calculate the reliability of the network.

A system is called a ' $k$ out of $n$ ' system if it contains $n$ components and it works whenever $k$ or more of these components are working. Suppose that each component is working with probability $p$, independently of the other components, and let $X_{c}$ be the indicator function of the event that component $c$ is working. Find, in terms of the $X_{c}$, the indicator function of the event that the system works, and deduce the reliability of the system.

Let $G = (V, E)$ be a finite graph. For any set $W$ of vertices and any edge $e \in E$, define the indicator function

Set $N_{W} = \sum_{e \in E} I_{W}(e)$. Show that there exists $W \subseteq V$ such that $N_{W} \geq \frac{1}{2}\left|E\right|$.

A total of $n$ bar magnets are placed end to end in a line with random independent orientations. Adjacent like poles repel, ends with opposite polarities join to form blocks. Let $X$ be the number of blocks of joined magnets. Find $\mathbb {E}\left[X\right]$ and $\operatorname {Var}\left[X\right]$.

In a lecture audience, there are $n$ students born in 2011, and they were born on independent, uniformly distributed days. Calculate the mean of the number $B$ of pairs of students sharing a birthday, and show that $\mathbb {E}\left[B\right] > 1$ if and only if $n \geq 28$. Compare this with the result of Problem (1.8.30). Find the variance of $B$.

Show that any set of 10 points in the plane $\mathbb {R}^{2}$ can be covered by a suitable placement of disjoint open unit disks. [Hint: Consider an infinite array of unit disks whose centres form a triangular lattice.]

Days are either wet or dry, and, given today's weather, tomorrow's is the same as today's with probability $p$, and different otherwise. Let $w_{n}$ be the probability that the weather $n$ days into the future from today will be wet. Show that $w_{n+1} = 1-p+(2 p-1) w_{n-1}$, and find $w_{n}$. What is the mean number of wet days in the next week?

An urn contains $b$ balls of which $g$ are green. Balls are sampled from the urn at random, one by one. After a ball is sampled, its colour is noted, and it is discarded. Find the mean and variance of the number of green balls in a sample of size $n( \leq b)$.

Let $n( \geq 2)$ heterosexual couples be seated randomly at a circular table, subject only to the rule that the sexes alternate. There is no requirement that couples sit together. Let $X$ be the number of couples seated adjacently. Show that $\mathbb {E}\left[X\right] = 2$ and $\operatorname {Var}\left[X\right] = 2-2 /(n-1)$.

Each trial may result in any of $t$ given outcomes, the $i$ th outcome having probability $p_{i}$. Let $N_{i}$ be the number of occurrences of the $i$ th outcome in $n$ independent trials. Show that

for any collection $n_{1}, n_{2}, \ldots , n_{t}$ of non-negative integers with sum $n$. The vector $N$ is said to have the multinomial distribution.

In your pocket is a random number $N$ of coins, where $N$ has the Poisson distribution with parameter $\lambda$. You toss each coin once, with heads showing with probability $p$ each time. Show that the total number of heads has the Poisson distribution with parameter $\lambda p$.

Let $X$ be Poisson distributed where $\mathbb {P}\left(X = n\right) = p_{n}(\lambda ) = \lambda^{n} e^{-\lambda } / n$ ! for $n \geq 0$. Show that $\mathbb {P}\left(X \leq k\right) = 1-\int_{0}^{\lambda } p_{k}(x) d x$.

A population of $b$ animals has had a number $a$ of its members captured, marked, and released. Let $X$ be the number of animals it is necessary to recapture (without re-release) in order to obtain $m$ marked animals. Show that

and find $\mathbb {E}\left[X\right]$. This distribution has been called negative hypergeometric.

Let $\Lambda$ be a positive random variable with density function $f$ and distribution function $F$, and let $Y$ have the Poisson distribution with parameter $\Lambda$. Show for $n = 0,1,2, \ldots$ that

where $p_{n}(\lambda ) = e^{-\lambda } \lambda^{n} / n!$.

Show that the collection of random variables on a given probability space and having finite variance forms a vector space over the reals.

Find the marginal mass functions of the multinomial distribution of Exercise (3.5.1).

Let $X$ and $Y$ be discrete random variables with joint mass function

Find the marginal mass functions of $X$ and $Y$, calculate $C$, and also the covariance of $X$ and $Y$.

Let $X$ and $Y$ be discrete random variables with mean $0$, variance $1$, and covariance $\rho$. Show that $\mathbb {E}\left[\max \left\{ X^{2}, Y^{2}\right\} \right] \leq 1+\sqrt{1-\rho^{2}}$.

Let $X$ and $Y$ be discrete random variables with joint mass function $f$.

Let $X, Y, Z$ be discrete random variables with the property that their values are distinct with probability 1. Let $a = \mathbb {P}\left(X > Y\right), b = \mathbb {P}\left(Y > Z\right), c = \mathbb {P}\left(Z > X\right)$.

If one picks a numerical entry at random from an almanac, or the annual accounts of a corporation, the first two significant digits, $X$, $Y$, are found to have approximately the joint mass function

Find the mass function of $X$ and an approximation to its mean.

Let $X$ and $Y$ have joint mass function

where $a$ is a constant. Find $c, \mathbb {P}\left(X = j\right), \mathbb {P}\left(X+Y = r\right)$, and $\mathbb {E}\left[X\right]$.

Let $X, Y, Z$ be non-degenerate and independent random variables. By considering $U = X+Y, V = Y+Z, W = Z-X$, or otherwise, show that having positive correlation is not a transitive relation.

Use the identity $a^{2} d^{2}+b^{2} c^{2}-2 a b c d = (a d-b c)^{2}$ to prove the Cauchy-Schwarz inequality.

Show that

Show the following:

Suppose that $X$ and $Y$ are discrete random variables, and that $\phi (X)$ and $\psi (X)$ are two functions of $X$ satisfying

for any function $g$ for which all the expectations exist. Show that $\phi (X)$ and $\psi (X)$ are almost surely equal, in that $\mathbb {P}\left(\phi (X) = \psi (X)\right) = 1$.

Suppose that the conditional expectation of $Y$ given $X$ is defined as the (almost surely) unique function $\psi (X)$ such that $\mathbb {E}\left[\psi (X) g(X)\right] = \mathbb {E}\left[Y g(X)\right]$ for all functions $g$ for which the expectations exist. Show (a)-(f) of Exercise (3.7.1) above (with the occasional addition of the expression 'with probability $1$').

How should we define $\operatorname {Var}\left[Y \mid X\right]$, the conditional variance of $Y$ given $X$? Show that $\operatorname {Var}\left[Y\right] = \mathbb {E}\left[\operatorname {Var}\left[Y \mid X\right]\right]+\operatorname {Var}\left[\mathbb {E}\left[Y \mid X\right]\right]$.

The lifetime of a machine (in days) is a random variable $T$ with mass function $f$. Given that the machine is working after $t$ days, what is the mean subsequent lifetime of the machine when:

Let $X_{1}, X_{2}, \ldots$ be identically distributed random variables with mean $\mu$ and variance $\sigma^{2}$, and let $N$ be a random variable taking values in the non-negative integers and independent of the $X_{i}$. Let $S = X_{1}+X_{2}+\cdots +X_{N}$. Show that $\mathbb {E}\left[S \mid N\right] = \mu N$, and deduce that $\mathbb {E}\left[S\right] = \mu \mathbb {E}\left[N\right]$. Find $\operatorname {Var}\left[S\right]$ in terms of the first two moments of $N$, using the conditional variance formula of Exercise (3.7.4).

A factory has produced $n$ robots, each of which is faulty with probability $\phi$. To each robot a test is applied which detects the fault (if present) with probability $\delta$. Let $X$ be the number of faulty robots, and $Y$ the number detected as faulty. Assuming the usual independence, show that

Each child is equally likely to be male or female, independently of all other children.

Let $X$ and $Y$ be independent with mean $\mu$. Explain the error in the following equation:

A coin shows heads with probability $p$. Let $X_{n}$ be the number of flips required to obtain a run of $n$ consecutive heads. Show that $\mathbb {E}\left[X_{n}\right] = \sum_{k = 1}^{n} p^{-k}$.

Give a definition of the conditional covariance $\operatorname {Cov}\left[X, Y \mid Z\right]$. Show that

An urn contains initially $b$ blue balls and $r$ red balls, where $b, r \geq 2$. Balls are drawn one by one without replacement. Show that the mean number of draws until the first colour drawn is first repeated equals 3.

Let $X, Y$ be discrete integer-valued random variables with the joint mass function

Show that $X$ and $Y$ are each Poisson-distributed, and that the conditional distribution of $X$ given $Y$ is binomial.

Let $X$ and $Y$ be independent variables, $X$ being equally likely to take any value in $\left\{ 0,1, \ldots , m\right\}$, and $Y$ similarly in $\left\{ 0,1, \ldots , n\right\}$. Find the mass function of $Z = X+Y$. The random variable $Z$ is said to have the trapezoidal distribution.

Let $X$ and $Y$ have the joint mass function

Find the mass functions of $U = X+Y$ and $V = X-Y$.

Let $X$ and $Y$ be independent geometric random variables with respective parameters $\alpha$ and $\beta$. Show that

Let $\left\{ X_{r}: 1 \leq r \leq n\right\}$ be independent geometric random variables with parameter $p$. Show that $Z = \sum_{r = 1}^{n} X_{r}$ has a negative binomial distribution.

Sam rolls $6 n$ dice once; he needs at least $n$ sixes. Isaac rolls $6(n+1)$ dice; he needs at least $n+1$ sixes. Who is more likely to obtain the number of sixes he needs?

Let $N$ be Poisson distributed with parameter $\lambda$. Show that, for any function $g$ such that the expectations exist, $\mathbb {E}\left[N g(N)\right] = \lambda \mathbb {E}\left[g(N+1)\right]$. More generally, if $S = \sum_{r = 1}^{N} X_{r}$, where $\left\{ X_{r}: r \geq 0\right\}$ are independent identically distributed non-negative integer-valued random variables, show that

Let $S = \sum_{i = 1}^{N} X_{i}$, where the $X_{i}, i \geq 1$, are independent, identically distributed random variables with mean $\mu$ and variance $\sigma^{2}$, and $N$ is positive, integer-valued, and independent of the $X_{i}$. Show that $\mathbb {E}\left[S\right] = \mu \mathbb {E}\left[N\right]$, and

Let $X$ and $Y$ be independent random variables with the geometric distributions $f_{X}(k) = p q^{k-1}$, $f_{Y}(k) = \lambda \mu^{k-1}$, for $k \geq 1$, where $p+q = \lambda +\mu = 1$ and $q \neq \mu$. Write down $\mathbb {P}\left(X+Y = n+1, X = k\right)$, and hence find the distribution of $X+Y$, and the conditional distribution of $X$ given that $X+Y = n+1$. Does anything special occur when $q = \mu$?

Let $T$ be the time which elapses before a simple random walk is absorbed at either of the absorbing barriers at 0 and $N$, having started at $k$ where $0 \leq k \leq N$. Show that $\mathbb {P}\left(T < \infty \right) = 1$ and $\mathbb {E}\left[T^{k}\right] < \infty$ for all $k \geq 1$.

For simple random walk $S$ with absorbing barriers at 0 and $N$, let $W$ be the event that the particle is absorbed at 0 rather than at $N$, and let $p_{k} = \mathbb {P}\left(W \mid S_{0} = k\right)$. Show that, if the particle starts at $k$ where $0 < k < N$, the conditional probability that the first step is rightwards, given $W$, equals $p p_{k+1} / p_{k}$. Deduce that the mean duration $J_{k}$ of the walk, conditional on $W$, satisfies the equation

subject to the convention that $p_{N} J_{N} = 0$. Show that we may take as boundary condition $J_{0} = 0$. Find $J_{k}$ in the symmetric case, when $p = \frac{1}{2}$.

With the notation of Exercise (3.9.2), suppose further that at any step the particle may remain where it is with probability $r$ where $p+q+r = 1$. Show that $J_{k}$ satisfies

and that, when $\rho = q / p \neq 1$,

A coin is tossed repeatedly, heads turning up with probability $p$ on each toss. Player A wins the game if $m$ heads appear before $n$ tails have appeared, and player B wins otherwise. Let $p_{m n}$ be the probability that A wins the game. Set up a difference equation for the $p_{m n}$. What are the boundary conditions?

Consider a simple random walk on the set $\left\{ 0,1,2, \ldots , N\right\}$ in which each step is to the right with probability $p$ or to the left with probability $q = 1-p$. Absorbing barriers are placed at 0 and $N$. Show that the number $X$ of positive steps of the walk before absorption satisfies