Problem 10.28 Easy Free 4 variations

Elevator Stops

A lift starts in the basement of a building with $10$ floors above it. Twelve people get in, and each independently chooses one of the $10$ floors uniformly at random as their destination. Find the expected number of floors at which the lift stops to let out at least one person.

Work it out, then compare with the answer.

SolutionShow the worked solution

Let $X_i$ indicate that at least one person gets out at floor $i$ , for $i=1,\dots,10$ . The number of stops is $S=X_1+\dots+X_{10}$ .

A given person avoids floor $i$ with probability $\frac{9}{10}$ . The choices are independent, so

\mathbb{P}(X_i=0)=\left(\tfrac{9}{10}\right)^{12}.

By linearity of expectation and symmetry between the floors,

\mathbb{E}[S]=\sum_{i=1}^{10}\mathbb{P}(X_i=1)=10\left(1-\left(\tfrac{9}{10}\right)^{12}\right)=10-\frac{9^{12}}{10^{11}}.

Since $9^{12}=282\,429\,536\,481$ , this gives

\boxed{\mathbb{E}[S]=10\left(1-\left(\tfrac{9}{10}\right)^{12}\right)=\frac{717\,570\,463\,519}{10^{11}}\approx 7.18}

Generalisation. With $n$ people and $k$ equally likely floors, the expected number of stops is $k\bigl(1-(1-1/k)^n\bigr)$ .

Variations

The same idea with a twist. Each solution gives only the changed step.

Variation 10.28a

A bag contains $10$ sweets: $6$ blue, $2$ red, $1$ green, and $1$ yellow. Three sweets are drawn at random without replacement. Find the expected number of distinct colours among the sweets drawn.

Work it out, then compare with the answer.

Solution

Let $C$ indicate that a particular colour appears among the three sweets, and suppose that colour has $k$ sweets in the bag. The draw misses the colour exactly when all three sweets come from the other $10-k$ . All $\binom{10}{3}=120$ draws are equally likely, so

\mathbb{E}[C]=1-\frac{\binom{10-k}{3}}{120}.

This gives $1-\frac{4}{120}=\frac{29}{30}$ for blue ( $k=6$ ), $1-\frac{56}{120}=\frac{8}{15}$ for red ( $k=2$ ), and $1-\frac{84}{120}=\frac{3}{10}$ each for green and yellow ( $k=1$ ). Summing,

\frac{29}{30}+\frac{16}{30}+\frac{9}{30}+\frac{9}{30}=\frac{63}{30}.

\boxed{\tfrac{21}{10}}

Variation 10.28b

Suppose $n$ balls are thrown independently and uniformly at random into $n$ bins. Let $P_n$ denote the (random) proportion of bins that end up empty. Determine $\lim_{n\to\infty}\ln\big(\mathbb{E}[P_n]\big)$ , or state that it does not exist.

Work it out, then compare with the answer.

Solution

Each ball misses a given bin with probability $1-\frac1n$ , and the balls are independent. So a given bin is empty with probability $(1-\frac1n)^n$ .

Let $N_n$ be the number of empty bins. By linearity, $\mathbb{E}[N_n]=n(1-\frac1n)^n$ , so

\mathbb{E}[P_n]=\frac{\mathbb{E}[N_n]}{n}=\left(1-\tfrac1n\right)^n\to e^{-1}.

For $n\ge2$ this expectation is positive, and $\ln$ is continuous at $e^{-1}$ . Hence the limit exists:

\boxed{-1}

Variation 10.28c

A factory operates every day of a $365$ -day year and runs $24$ hours on any day when none of its employees has a birthday; on any day when at least one employee has a birthday, the factory shuts down for the whole day and no one works. Employees’ birthdays are independent and uniform over the $365$ days. The factory wants to choose the number of employees to hire so as to maximise the expected total number of hours per year that employees are not working. Is any finite number of employees optimal? If so, how many should it hire?

Work it out, then compare with the answer.

Solution

Write $q=\frac{364}{365}$ . A given day contains at least one of the $n$ birthdays with probability $1-q^n$ . So the expected number of shut-down days is $365(1-q^n)$ .

On each such day all $n$ employees are off for $24$ hours. The expected number of employee-hours off is therefore

H(n)=24\cdot 365\cdot n\,(1-q^n).

Both factors $n$ and $1-q^n$ are positive and strictly increasing in $n$ . So $H$ is strictly increasing and $H(n)\to\infty$ , and no finite $n$ attains a maximum.

If one counts instead the hours during which the factory is idle, the expectation $24\cdot365(1-q^n)$ is still strictly increasing in $n$ . It never reaches its supremum $8760$ , so again no finite $n$ is optimal.

\boxed{\text{No finite number of employees is optimal}}

Variation 10.28d

Suppose $n$ people each have a birthday chosen independently and uniformly among $365$ days. Let $b(n)$ denote the expected number of days of the year on which exactly one of the $n$ people has a birthday. There are exactly two positive integers $n$ at which $b(n)$ attains its maximum value. Find them.

Work it out, then compare with the answer.

Solution

Write $q=\frac{364}{365}$ . A given day is the birthday of exactly one person with probability $n\cdot\frac{1}{365}\,q^{\,n-1}$ . Summing over the $365$ days gives

b(n)=n\,q^{\,n-1}.

Compare consecutive values:

\frac{b(n+1)}{b(n)}=\frac{(n+1)\cdot 364}{365\,n}.

This ratio is greater than $1$ for $n<364$ , equal to $1$ at $n=364$ , and less than $1$ for $n>364$ . So $b$ increases up to $n=364$ , satisfies $b(364)=b(365)$ , and decreases from $n=365$ onwards. The maximisers are therefore

\boxed{n=364\ \text{and}\ n=365}

Spotted an error? Email us