Indicators and matching

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)$.