A Prisoner Problem Variation

Jerry Metzger and Thomas Richards University of North Dakota Department of Mathematics Witmer Hall Room 313 101 Cornell Street Stop 8376 Grand Forks, ND 58202-8376 USA

                     jerry.metzger@und.edu
                    thomas.richards@und.edu

Abstract Consider a fair n-sided die with faces numbered 1 to n. Several different methods are used to compute the probability that every face has come up at least once when face n appears for the k^{th} time. The results lead to a number of summation identities. The probabilities are related to several sequences in Sloane’s On-Line Encyclopedia of Integer Sequences.

1 Introduction

1.1 The puzzle

The warden meets with 23 new prisoners when they arrive. He tells them, “You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

“In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the on or the off position. I am not telling you their present positions. The switches are not connected to anything.

“After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can’t move both but he can’t move none either. Then he’ll be led back to his cell.

“No one else will enter the switch room until I lead the next prisoner there, and he’ll be instructed to do the same thing. I’m going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

“But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time any one of you may declare to me, ‘We have all visited the switch room.

“If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators.”

Here’s the question: What is the strategy the prisoners devise?

That is the puzzle as presented by Tom and Ray Magliozzi on their National Public Radio show Car Talk [6].

1.2 A solution

One prisoner is selected as the monitor. The other 22 prisoners are given the following instructions: the first two times you enter the switch room with switch A in the off position, flip it to the on position; otherwise flip switch B. The monitor’s first visit to the switch room is used to set switch A in the off position if it is not already there or flip switch B otherwise. The monitor now begins to count visits: whenever the monitor enters the switch room after that first time, and finds switch A on, it is flipped off, and 1 is added to the visits total; otherwise switch B is flipped. When the visits total reaches 43, the monitor announces that all 22 other prisoners have each been to the switch room at least once. This is so since 21 prisoners can account for at most 42 cases of the monitor finding switch A in the on position.

1.3 A variation

In this note, the switches are removed from the puzzle and the number of prisoners is some n ≥ 1. A monitor is elected whose duty is to declare, when escorted to the interview room, that all the other prisoners have been to the interview room at least once. In this situation, the puzzle now becomes a probability problem. On visit k by the monitor, what is the probability that all n − 1 other prisoners have been to the interview room at least once?

This version of the puzzle is similar to the occupancy problems of the type discussed by David and Barton [2]. In the terminology of that text, the problem would be presented as: If balls are distributed one at a time randomly into boxes numbered 1, 2, 3, …, n, what is the probability that there are no empty boxes when the k^{th} ball is added to box n? Or, the version used here, if an n-sided fair die is rolled repeatedly, what is the probability that every face has come up at least once when face n comes up for the k^{th} time?

2 The natural solution

Let n, k be positive integers. Roll an n-sided fair die repeatedly. We compute the probability that every face has occurred at least once when face n comes up for the k^{th} time.

When face n comes up for the k^{th} time, and every other face has occurred at least once, the preceding tosses will consist of j_{i} ≥ 1 occurrence of faces i = 1, 2, …, n − 1 and k − 1 occurrences of face n. The probability of any one such pattern is given by

(\frac{1}{n})^{j_{1}+j_{2}+···+j_{n−1}+k−1} .

The number of such patterns is given by the multinomial coefficient

\binom{j_{1} + j_{2} + ⋯ + j_{n−1} + k − 1}{j_{1}, j_{2}, …, j_{n−1}, k − 1}.

So the probability of faces 1 through n − 1 each occurring at least once and face n occurring k − 1 times is

∑_{j_{1}=1}^{∞} ∑_{j_{2}=1}^{∞} ⋯ ∑_{j_{n−1}=1}^{∞} (\frac{1}{n})^{j_{1}+j_{2}+···+j_{n−1}+k−1} \binom{j_{1} + j_{2} + ⋯ + j_{n−1} + k − 1}{j_{1}, j_{2}, …, j_{n−1}, k − 1}.

It follows that the probability every face has occurred at least once when face n comes up for the k^{th} time is

\frac{1}{n} ∑_{j_{1}=1}^{∞} ∑_{j_{2}=1}^{∞} ⋯ ∑_{j_{n−1}=1}^{∞} (\frac{1}{n})^{j_{1}+j_{2}+···+j_{n−1}+k−1} \binom{j_{1} + j_{2} + ⋯ + j_{n−1} + k − 1}{j_{1}, j_{2}, …, j_{n−1}, k − 1}

= ∑_{j_{1}=1}^{∞} ∑_{j_{2}=1}^{∞} ⋯ ∑_{j_{n−1}=1}^{∞} (\frac{1}{n})^{j_{1}+j_{2}+···+j_{n−1}+k} \binom{j_{1} + j_{2} + ⋯ + j_{n−1} + k − 1}{j_{1}, j_{2}, …, j_{n−1}, k − 1}.

3 The inclusion-exclusion solution

The probability is computed again, this time by inclusion-exclusion. For j = 1, 2, …, n − 1, let A_{j} be the event that face j has not come up when face n appears for the k^{th} time. Then the probability that every face has come up at least once when face n is tossed for the k^{th} time is

p(n, k) = 1 − Pr(A_{1} or A_{2} or ⋯ or A_{n−1}).

Using the summation formula

∑_{m=k}^{∞} \binom{m − 1}{k − 1}x^{m} = (\frac{x}{1 − x})^{k} ,

it follows that for each of the \binom{n−1}{j} possible choices of j of the events, and for any m ≥ k, the probability that face n appears k − 1 times in the first m − 1 tosses, and face n appears for the k^{th} time on toss m, is given by

(\frac{n − j − 1}{n})^{m−k} (\frac{1}{n})^{k−1} \binom{m − 1}{k − 1}\frac{1}{n}.

Consequently,

Pr(A_{i_{1}} and A_{i_{2}} and ⋯ and A_{i_{j}}) = ∑_{m=k}^{∞} (\frac{1}{n})^{k} (\frac{n − j − 1}{n})^{m−k} \binom{m − 1}{k − 1}

= (\frac{1}{n})^{k} (\frac{n}{n − j − 1})^{k} ∑_{m=k}^{∞} (\frac{n − j − 1}{n})^{m} \binom{m − 1}{k − 1}

= (\frac{1}{n − j − 1})^{k} (1 − \frac{n−j−1}{n})^{k}^{(\frac{n−j−1}{n})k} = \frac{1}{(j + 1)^{k}} ,

So, by inclusion-exclusion, the probability that every face has occurred at least once when face n is rolled for the k^{th} time is

(\frac{1}{1})^{k} \binom{n − 1}{0} − (\frac{1}{2})^{k} \binom{n − 1}{1} + ⋯ + (\frac{1}{j})^{k} \binom{n − 1}{j − 1} + ⋯ + (−1)^{n−1} (\frac{1}{n})^{k} \binom{n − 1}{n − 1}

= ∑_{j=1}^{n}(−1)^{j−1} (\frac{1}{j})^{k} \binom{n − 1}{j − 1}.

This leads to the unusual-looking identity

∑_{j_{1}=1}^{∞} ∑_{j_{2}=1}^{∞} ⋯ ∑_{j_{n−1}=1}^{∞} (\frac{1}{n})^{j_{1}+j_{2}+···+j_{n−1}+k} \binom{j_{1} + j_{2} + ⋯ + j_{n−1} + k − 1}{j_{1}, j_{2}, …, j_{n−1}, k − 1}

= ∑_{j=1}^{n}(−1)^{j−1} (\frac{1}{j})^{k} \binom{n − 1}{j − 1}.

4 The waiting time solution

The probability can also be thought of as a waiting time problem. See Feller [3, p. 166]. Think of the rolls of the die as a sequence of Bernoulli trials with success being the occurrence of face n with probability p = \frac{1}{n} and failure being the occurrence of any other face with probability q = 1 − p = 1 − \frac{1}{n}. For t ≥ 0, the probability of the k^{th} success on trial k + t is the probability that exactly t failures precede the k^{th} success. The probability of exactly t failures in k + t − 1 trials followed by success at trial k + t is given by

Pr(k^{th} success at trial k + t) = \binom{k + t − 1}{t} (\frac{1}{n})^{k−1} (1 − \frac{1}{n})^{t} \frac{1}{n}

= \binom{k + t − 1}{t} (\frac{1}{n})^{k} (1 − \frac{1}{n})^{t} .

Next, an expression for the probability that faces 1, 2, …, n − 1, but not n, all occur in t rolls (t ≥ n − 1, necessarily) is derived.

Recall that \left\{{t \atop n−1}\right\}, the Stirling number of the second kind, gives the number of ways of distributing t distinguishable balls (tosses of a die in our case) in n − 1 indistinguishable boxes (faces in our case) with no box empty. See Graham, Knuth, and Patashnik [4, p. 257] for facts about the Stirling numbers. If the boxes are now made distinguishable, there are (n − 1)! \left\{{t \atop n−1}\right\} distributions possible. Of the (n − 1)^{t} possible patterns of length t of faces 1, 2, …, n − 1, the probability that each of those n − 1 faces occurs at least once, with no face n, is therefore given by

Pr(faces 1, 2, …, n − 1 all occur in t rolls) = \frac{(n − 1)! \left\{{t \atop n−1}\right\}}{(n − 1)^{t}}.

It follows that the probability that every face has appeared at least once when face n occurs for the k^{th} time is given by

∑_{t=n−1}^{∞} Pr(k^{th} success at trial k + t) Pr(faces 1, 2, …, n − 1 all occur in t rolls)

= ∑_{t=n−1}^{∞} \frac{(n − 1)! \left\{{t \atop n−1}\right\}}{(n − 1)^{t}} (\frac{1}{n})^{k} (1 − \frac{1}{n})^{t} \binom{k + t − 1}{t}

The sequence T (t, m) = m! \left\{{t \atop m}\right\} (read by rows with t ≥ 0, 0 ≤ m ≤ t) appears in the On-Line Encyclopedia of Integer Sequences as \underline{A131689}. There are two formulas for the entries in this sequence not mentioned in the OEIS.

One, which is virtually the definition of m! \left\{{t \atop m}\right\}, is

m! \left\{{t \atop m}\right\} = ∑_{S_{t}} \binom{t}{t_{1}, t_{2}, …, t_{m}},

where the sum is taken over the set S_{t} of all partitions of t into m positive parts. This is so since the multinomial coefficient \binom{t}{t_{1},t_{2},...,t_{m}} gives the number of arrangements of t_{1} 1’s, t_{2} 2’s, and so on, up to t_{m} m’s.

A second expression for m! \left\{{t \atop m}\right\}, also involving the sum over S_{t} of all partitions of t into m positive parts, is not so obvious:

m! \left\{{t \atop m}\right\} = ∑_{S_{t}} 1^{t_{1}}2^{t_{2}} ⋯ m^{t_{m}}.

To see this is correct, let U(t, m) = \frac{1}{m!} ∑_{S_{t}} 1^{t_{1}}2^{t_{2}} ⋯ m^{t_{m}}. For convenience we will declare U(0, 0) = 1. Note that U(t, 0) = 0 for t > 0 since S_{t} will be empty in such cases. These are the same initial conditions satisfied by the Stirling numbers:

\left\{{0 \atop 0}\right\} = 1 and \left\{{t \atop 0}\right\} = 0 for t > 0.

In addition, the Stirling numbers satisfy the recursion

\left\{{t \atop m}\right\} = m \left\{{t − 1 \atop m}\right\} + \left\{{t − 1 \atop m − 1}\right\} for t > 0.

We will show that U satisfies the same recursion. Let t, m > 0. Then, letting A be the set of partitions of t − 1 into m positive parts, and letting B be the set of partitions of t − 1 into m − 1 positive parts, we see

mU(t − 1, m) + U(t − 1, m − 1)

= \frac{m}{m!} ∑_{A} 1^{t_{1}}2^{t_{2}} ⋯ m^{t_{m}} + \frac{1}{(m − 1)!} ∑_{B} 1^{t_{1}}2^{t_{2}} ⋯ (m − 1)^{t_{m−1}}

= \frac{1}{m!} ∑_{A} 1^{t_{1}}2^{t_{2}} ⋯ m^{t_{m}+1} + \frac{1}{m!} ∑_{B} 1^{t_{1}}2^{t_{2}} ⋯ (m − 1)^{t_{m−1}}m

The first sum accounts for all terms in U(t, m) with m raised to a power bigger than 1 while the second sum accounts for the terms with m raised to the first power, and so

mU(t − 1, m) + U(t − 1, m − 1) = U(t, m).

Since \left\{{t \atop m}\right\} and U(t, m) have the same initial conditions and obey the same recursion, it follows that

m! \left\{{t \atop m}\right\} = ∑_{S_{t}} 1^{t_{1}}2^{t_{2}} ⋯ m^{t_{m}}.

Comparing the various expressions derived here with the result of the inclusion-exclusion computation gives several summation identities:

p(n, k) = ∑_{j=1}^{n}(−1)^{j−1} (\frac{1}{j})^{k} \binom{n − 1}{j − 1}

= ∑_{t=n−1}^{∞} \frac{(n − 1)! \left\{{t \atop n−1}\right\}}{n^{k+t}} \binom{k + t − 1}{t}

= ∑_{t=n−1}^{∞} ∑_{S_{t}} \frac{1}{n^{k+t}} \binom{t}{t_{1}, t_{2}, …, t_{m}}\binom{k + t − 1}{t}

= ∑_{t=n−1}^{∞} ∑_{S_{t}} \frac{1^{t_{1}}2^{t_{2}} ⋯ (n − 1)^{t_{n−1}}}{n^{k+t}} \binom{k + t − 1}{t},

where, in the last two expressions, the sums are taken over the set S_{t} of all ordered partitions, (t_{1}, t_{2}, …, t_{n−1}), of t into n − 1 positive parts.

5 The Markov process solution

The problem can also be modeled as a Markov process with two absorbing states. The notation and terminology as given in Kemeny and Snell [5, p. 43] is used in what follows.

In Figure 1, the initial state is labeled \left[{0 \atop 0}\right]. Each roll of the die determines a state transition. If face n comes up, move to the state directly above the current state. If a face other than n comes up for the first time, move to the state to the right of the current state. In each state, the upper parameter gives the number of times face n has been tossed, and the lower parameter gives the number of different faces from 1, 2, 3, …, n−1 that have come up. There is a loop back for every state that is omitted from the figure for the sake of clarity: there is no change of state for faces 1, 2, …, n − 1 when they come up after the first time. Finally, the topmost state and the rightmost state are absorbing states. The probability of looping back in those two states is 1.

For each of the non-absorbing states \left[{s \atop t}\right], the probability of moving to the state directly above is \frac{1}{n}, and the probability of moving to the state directly to the right is \frac{n−1−s}{n}. The probability of staying in the same state is \frac{s}{n}. Number the transient states left to right and then from bottom to top, starting with s_{1} for state \left[{0 \atop 0}\right], ending with k(n − 1) for state \left[{n−2 \atop k−1}\right]. Let s_{k(n−1)+1} be the absorbing state on the right, and finally, let s_{k(n−1)+2} be the absorbing state at the top of the diagram. With this numbering of the states, and the matrix columns taken in the order s_{k(n−1)+1}, s_{k(n−1)+2}, s_{1}, s_{2}, s_{3}, …, s_{k(n−1)}, the canonical transition matrix has the form

P = [ \begin{matrix}I & 0 \\ R & Q \end{matrix} ] = [ \begin{matrix}1 & & 0 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & & 1 & 0 & 0 & 0 & ⋯ & 0 \\ & R & & & & Q \end{matrix} ] ,

Figure 1: The Markov Process with absorbing states.

where R is the k(n − 1) × 2 matrix giving the probabilities of moving from a transient state to one of the absorbing states, and Q is the k(n−1)×k(n−1) matrix giving the probabilities of moving between the transient states.

As a small example, for the case n = 5 and k = 3, the canonical matrix is

P = [ \begin{matrix}1 & & 0 & 0 & 0 & 0 & ⋯ & 0 \\ 0 & & 1 & 0 & 0 & 0 & ⋯ & 0 \\ & R & & & & Q \end{matrix} ] = [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{4}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{5} & \frac{3}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{2}{5} & \frac{2}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{5} & 0 & 0 & 0 & 0 & \frac{3}{5} & 0 & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{4}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{5} & \frac{3}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{2}{5} & \frac{2}{5} & 0 & 0 & \frac{1}{5} & 0 \\ \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{3}{5} & 0 & 0 & 0 & \frac{1}{5} \\ 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{4}{5} & 0 & 0 \\ 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{5} & \frac{3}{5} & 0 \\ 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{2}{5} & \frac{2}{5} \\ \frac{1}{5} & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{3}{5} \end{matrix} ] .

In this example, the fundamental matrix N = (I − Q)^{−1} is given by

N = [ \begin{matrix}1 & 1 & 1 & 1 & \frac{1}{5} & \frac{9}{20} & \frac{47}{60} & \frac{77}{60} & \frac{1}{25} & \frac{61}{400} & \frac{1489}{3600} & \frac{3799}{3600} \\ 0 & \frac{5}{4} & \frac{5}{4} & \frac{5}{4} & 0 & \frac{5}{16} & \frac{35}{48} & \frac{65}{48} & 0 & \frac{5}{64} & \frac{185}{576} & \frac{575}{576} \\ 0 & 0 & \frac{5}{3} & \frac{5}{3} & 0 & 0 & \frac{5}{9} & \frac{25}{18} & 0 & 0 & \frac{5}{27} & \frac{95}{108} \\ 0 & 0 & 0 & \frac{5}{2} & 0 & 0 & 0 & \frac{5}{4} & 0 & 0 & 0 & \frac{5}{8} \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & \frac{1}{5} & \frac{9}{20} & \frac{47}{60} & \frac{77}{60} \\ 0 & 0 & 0 & 0 & 0 & \frac{5}{4} & \frac{5}{4} & \frac{5}{4} & 0 & \frac{5}{16} & \frac{35}{48} & \frac{65}{48} \\ 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{3} & \frac{5}{3} & 0 & 0 & \frac{5}{9} & \frac{25}{18} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{2} & 0 & 0 & 0 & \frac{5}{4} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{4} & \frac{5}{4} & \frac{5}{4} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{3} & \frac{5}{3} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{2} \end{matrix} ] .

The probability we are interested is the (1, 1) entry in the matrix product B = NR. That entry gives the probability that the state s_{13} has been reached starting from s_{1}, and consequently that all five faces of the die will have come up when face 5 is rolled for the third time.

We find

B = [ \begin{matrix}\frac{12019}{18000} & \frac{5981}{18000} \\ \frac{415}{576} & \frac{161}{576} \\ \frac{85}{108} & \frac{23}{108} \\ \frac{7}{8} & \frac{1}{8} \\ \frac{137}{300} & \frac{163}{300} \\ \frac{25}{48} & \frac{23}{48} \\ \frac{11}{18} & \frac{7}{18} \\ \frac{3}{4} & \frac{1}{4} \\ \frac{1}{5} & \frac{4}{5} \\ \frac{1}{4} & \frac{3}{4} \\ \frac{1}{3} & \frac{2}{3} \\ \frac{1}{2} & \frac{1}{2} \end{matrix} ] ,

which agrees with

p(5, 3) = ∑_{j=1}^{5}(−1)^{j−1} (\frac{1}{j})^{3} \binom{4}{j − 1} = \frac{12019}{18000}.

The particularly simple structure of the transition matrix Q makes it possible to compute the (1, 1) entry in NR = (I − Q)^{−1}R easily. Let A and D be the n − 1 × n − 1 matrices

A = [ \begin{matrix}0 & \frac{n−1}{n} & 0 & 0 & ⋯ & 0 \\ 0 & \frac{1}{n} & \frac{n−2}{n} & 0 & ⋯ & 0 \\ 0 & 0 & \frac{2}{n} & \frac{n−3}{n} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & 0 & 0 & \frac{n−2}{n} \end{matrix} ]  and  D = [ \begin{matrix}\frac{1}{n} & 0 & 0 & 0 & ⋯ & 0 \\ 0 & \frac{1}{n} & 0 & 0 & ⋯ & 0 \\ 0 & 0 & \frac{1}{n} & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & 0 & 0 & \frac{1}{n} \end{matrix} ] .

For I representing identity matrices of appropriate sizes and with 0 representing the n − 1 × n − 1 zero matrix, I − Q is the k × k block matrix

I − Q = [ \begin{matrix}I − A & −D & 0 & 0 & ⋯ & 0 \\ 0 & I − A & −D & 0 & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & 0 & ⋯ & I − A \end{matrix} ] .

The matrix D = \frac{1}{n}I commutes with I − A. Consequently, N = (I − Q)^{−1} is

N = [ \begin{matrix}(I − A)^{−1} & D(I − A)^{−2} & D^{2}(I − A)^{−3} & D^{3}(I − A)^{−4} & ⋯ & D^{k−1}(I − A)^{−k} \\ 0 & (I − A)^{−1} & D(I − A)^{−2} & D^{2}(I − A)^{−3} & ⋯ & D^{k−2}(I − A)^{−k+1} \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & 0 & ⋯ & (I − A)^{−1} \end{matrix} ] .

The matrix I − A can be written as

I − A = [ \begin{matrix}1 & −\frac{n − 1}{n} & 0 & 0 & ⋯ & 0 \\ 0 & 1 − \frac{1}{n} & −\frac{n − 2}{n} & 0 & ⋯ & 0 \\ 0 & 0 & 1 − \frac{2}{n} & −\frac{n − 3}{n} & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & 0 & 0 & 1 − \frac{n − 2}{n} \end{matrix} ]

= \frac{1}{n} [ \begin{matrix}n & −(n − 1) & 0 & 0 & ⋯ & 0 \\ 0 & n − 1 & −(n − 2) & 0 & ⋯ & 0 \\ 0 & 0 & n − 2 & −(n − 3) & ⋯ & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & 0 & 0 & 2 \end{matrix} ]

That last matrix can be diagonalized, with the eigenvalues n, n − 1, n − 2, …, 2, in that order, along the diagonal, by multiplying on the left and right by

S = S^{−1} = [ \begin{matrix}\binom{n−1}{0} & −\binom{n−1}{1} & \binom{n−1}{2} & −\binom{n−1}{3} & ⋯ & (−1)^{n}\binom{n−1}{n−2} \\ 0 & −\binom{n−2}{0} & \binom{n−2}{1} & −\binom{n−2}{2} & ⋯ & (−1)^{n}\binom{n−2}{n−3} \\ 0 & 0 & \binom{n−3}{0} & −\binom{n−3}{1} & ⋯ & (−1)^{n}\binom{n−3}{n−4} \\ ⋮ & ⋮ & ⋮ & ⋮ & & ⋮ \\ 0 & 0 & 0 & ⋯ & ⋯ & (−1)^{n}\binom{1}{0} \end{matrix} ]

Letting E be that diagonal matrix, so that I − A = \frac{1}{n}SES, and assembling the various pieces, the (1, 1) entry in B = NR is

∑_{j=1}^{k} \frac{1}{n}c_{j},

where c_{j} is the (1, n − 1) entry in

D^{j−1}(I − A)^{−j} = (\frac{1}{n}I)^{j−1} (\frac{1}{n}SES)^{−j} = nSE^{−j}S.

That gives one more expression for p(n, k):

p(n, k) = ∑_{j=1}^{k} \frac{1}{n} ∑_{m=1}^{n−1} n\binom{n − 1}{m − 1}\frac{(−1)^{m−1}}{(n − m + 1)^{j}} (−1)^{n}\binom{n − m}{n − m − 1}

= ∑_{j=1}^{k} ∑_{m=1}^{n−1}(−1)^{n+m−1}\binom{n − 1}{m − 1}\frac{n − m}{(n − m + 1)^{j}} .

6 Related entries in the OEIS

Let p(n, k) denote the probability that all faces have appeared at least once when face n occurs for the k^{th} time. This probability is related to a family of integer sequences, several of which are given in the OEIS. Let L_{n} be the least common multiple of the integers 1, 2, 3, …, n, and let

G_{n}(x) = \frac{1}{∏_{j=1}^{n}(1 − \frac{L_{n}}{j} x)} = \frac{n!}{∏_{j=1}^{n}(j − L_{n}x)} = n! ∏_{j=1}^{n} \frac{1}{(j − L_{n}x)}.

For n = 1, 2, 3, 4, 5, the functions G_{n}(x) are generating functions for sequences in the OEIS:

\underline{A000012} : G_{1}(x) = 1 + x + x^{2} + x^{3} + ⋯ + x^{n} + ⋯
\underline{A126646} : G_{2}(x) = 1 + 3x + 7x^{2} + 15x^{3} + 31x^{4} + ⋯ + (2^{n+1} − 1)x^{n} + ⋯
\underline{A001240} : G_{3}(x) = 1 + 11x + 85x^{2} + 575x^{3} + ⋯
\underline{A028037} : G_{4}(x) = 1 + 25x + 415x^{2} + 5845x^{3} + ⋯
\underline{A103878} : G_{5}(x) = 1 + 137x + 12019x^{2} + ⋯

The generating functions in this family are related in a simple way involving the probabilities

p(n, k) = ∑_{j=1}^{n}(−1)^{j−1} (\frac{1}{j})^{k} \binom{n − 1}{j − 1}.

In fact,

G_{n}(x) = ∑_{k=0}^{∞} [∑_{j=1}^{n}(−1)^{j−1} (\frac{1}{j})^{k} \binom{n − 1}{j − 1} (\frac{nL_{n}^{k}}{j} )] x^{k}

= ∑_{k=0}^{∞} [∑_{j=1}^{n}(−1)^{j−1} (\frac{L_{n}}{j} )^{k} \binom{n}{j}] x^{k}.

To show this is the expansion of G_{n}(x), it is sufficient to determine the expansion of

g_{n}(x) = ∏_{j=1}^{n} \frac{1}{1 − \frac{1}{j}x},

and then replace x with L_{n}x. The partial fraction expansion of g_{n}(x) is

g_{n}(x) = ∏_{k=1}^{n} \frac{1}{1 − \frac{1}{k}x} = \frac{A_{1}}{1 − \frac{x}{1}} + \frac{A_{2}}{1 − \frac{x}{2}} + ⋯ + \frac{A_{n}}{1 − \frac{x}{n}} .

Consequently

1 = A_{1}∏_{{k=1 \atop k≠1}}^{n} (1 − \frac{x}{k}) + A_{2}∏_{{k=1 \atop k≠2}}^{n} (1 − \frac{x}{k}) + ⋯ + A_{n} ∏_{{k=1 \atop k≠n}}^{n} (1 − \frac{x}{k}).

For each j = 1, 2, …, n, setting x = j in turn gives

1 = A_{j} ∏_{{k=1 \atop k≠j}}^{n} (1 − \frac{j}{k} ) = (−1)^{j−1} \frac{j!(n − j)!A_{j}}{n!} ,

and so

A_{j} = (−1)^{j−1}\binom{n}{j}.

It follows that

g_{n}(x) = ∑_{k=0}^{∞} [∑_{j=1}^{n} A_{j} (\frac{1}{j})^{k}] x^{k} = ∑_{k=0}^{∞} [∑_{j=1}^{n}(−1)^{j−1} (\frac{1}{j})^{k} \binom{n}{j}] x^{k}

as promised.

The probabilities p(n, k) are also related to a number of sequences in the OEIS that are obtained from iterated sums of harmonic numbers.

A family of sequences is defined recursively by

h_{1} = (1, 1, 1, …, 1, …)

so h_{1,k} = 1 for all k ≥ 1.

For n > 1, the k^{th} term of the sequence h_{n} is given by

h_{n,k} = ∑_{j=1}^{k} \frac{h(n − 1, j)}{j}.

The first few sequences in this family are

h_{1} = (1, 1, 1, …, 1, …)
h_{2} = (1, \frac{3}{2}, \frac{11}{6}, \frac{25}{12}, \frac{137}{60}, \frac{49}{20}, \frac{363}{140}, \frac{761}{280}, \frac{7129}{2520}, \frac{7381}{2520}, \frac{83711}{27720}, \frac{86021}{27720}, \frac{1145993}{360360}, \frac{1171733}{360360}, …)

h_{3} = (1, \frac{7}{4}, \frac{85}{36}, \frac{415}{144}, \frac{12019}{3600}, \frac{13489}{3600}, \frac{726301}{176400}, \frac{3144919}{705600}, \frac{30300391}{6350400}, \frac{32160403}{6350400}, \frac{4102360483}{768398400}, …)

h_{4} = (1, \frac{15}{8}, \frac{575}{216}, \frac{5845}{1728}, \frac{874853}{216000}, \frac{336581}{72000}, \frac{129973303}{24696000}, \frac{1149858589}{197568000}, \frac{101622655189}{16003008000}, …)

h_{5} = (1, \frac{31}{16}, \frac{3661}{1296}, \frac{76111}{20736}, \frac{58067611}{12960000}, \frac{68165041}{12960000}, \frac{187059457981}{31116960000}, \frac{3355156783231}{497871360000}, …)

The terms of the sequence h_{2} are the harmonic numbers, with the k^{th} term commonly written as H_{k}. These are the partial sums of the harmonic series.

The numerators of the terms of these sequences, with all fractions reduced to lowest terms, are listed in the OEIS.

\underline{A001008} : 1, 3, 11, 25, 137, 49, 363, 761, 7129, 7381, 83711, 86021, 1145993, 1171733, …
\underline{A027459} : 1, 7, 85, 415, 12019, 13489, 726301, 3144919, 30300391, 32160403, 4102360483, …
\underline{A027462} : 1, 15, 575, 5845, 874853, 336581, 129973303, 1149858589, 101622655189, …
\underline{A072913} : 1, 31, 3661, 76111, 58067611, 68165041, 187059457981, 3355156783231 …

Theorem 1. For n, k ≥ 1, we have h(n, k) = kp(k, n).

Proof. The proof will be by induction. For n = 1 and all k ≥ 1, we see

h(1, k) = 1 = k (\frac{1}{k}) = kp(k, 1).

Assuming that h(n − 1, k) = kp(k, n − 1) for some n ≥ 2 and all k ≥ 1, we see that, for any k ≥ 1,

h(n, k) = ∑_{j=1}^{k} \frac{h(n − 1, j)}{j} = ∑_{j=1}^{k} \frac{jp(j, n − 1)}{j}

= ∑_{j=1}^{k} ∑_{m=1}^{j}(−1)^{m−1} \frac{1}{m^{n−1}} \binom{j − 1}{m − 1} = ∑_{m=1}^{k} ∑_{j=m}^{k}(−1)^{m−1} \frac{1}{m^{n−1}} \binom{j − 1}{m − 1}

= ∑_{m=1}^{k}(−1)^{m−1} \frac{1}{m^{n}} (∑_{j=m}^{k} m\binom{j − 1}{m − 1}) = ∑_{m=1}^{k}(−1)^{m−1} \frac{1}{m^{n}} (k\binom{k − 1}{m − 1})

= kp(k, n).

The next to last equality follows from the upper summation identity,

∑_{m=t}^{s} \binom{m}{t} = \binom{s + 1}{t + 1} for s ≥ t,

that shows

∑_{j=m}^{k} m\binom{j − 1}{m − 1} = m ∑_{j=m}^{k} \binom{j − 1}{m − 1} = m\binom{k}{m} = m (\frac{k}{m}) \binom{k − 1}{m − 1} = k\binom{k − 1}{m − 1}.

It follows from Theorem 1 that if the numerator of h(n, k) and k are relatively prime, then the numerator of p(k, n) is the same as the numerator of h(n, k), as given in the OEIS entries listed above, and the denominator of p(k, n) is k times the denominator of h(n, k). That observation leads to the question of when the numerator of h(n, k) and k are relatively prime.

Theorem 2. If p ≥ 5 is a prime, then p divides the numerator of h(2, p(p − 1)) (written in lowest terms), and consequently the numerator of h(2, p(p−1)) and p(p−1) are not relatively prime.

Proof. Carlitz [1] established an extension of Wolstenholme’s theorem by showing that for a prime p ≥ 5

\frac{1}{kp + 1} + \frac{1}{kp + 2} + \frac{1}{kp + 3} + ⋯ + \frac{1}{(k + 1)p − 1} ≡ 0 (mod p^{2}),

so that p^{2} is a factor of the numerator of that sum written in lowest terms. Now

h(2, p(p − 1)) = ∑_{j=1}^{p(p−1)} \frac{1}{j} = (∑_{k=0}^{p−2} ∑_{j=1}^{p−1} \frac{1}{kp + j} ) + \frac{1}{p} + \frac{1}{2p} + ⋯ + \frac{1}{(p − 1)p}

= (∑_{k=0}^{p−2} ∑_{j=1}^{p−1} \frac{1}{kp + j} ) + \frac{1}{p} (1 + \frac{1}{2} + ⋯ + \frac{1}{(p − 1)}) .

For each k = 0, 1, …, p − 2, write, in lowest terms,

\frac{1}{kp + 1} + \frac{1}{kp + 2} + \frac{1}{kp + 3} + ⋯ + \frac{1}{(k + 1)p − 1} = \frac{p^{2}n_{k}}{m_{k}} .

So

h(2, p(p − 1)) = \frac{1}{p} (\frac{p^{2}n_{0}}{m_{0}} ) + ∑_{k=0}^{p−2} \frac{p^{2}n_{k}}{m_{k}} = \frac{pn_{0}}{m_{0}} + ∑_{k=0}^{p−2} \frac{p^{2}n_{k}}{m_{k}} .

Since p does not divide the denominators m_{k}, it follows that the numerator of h(2, p(p − 1)) is a multiple of p.

In addition to the values of k given by Theorem 2, there are rare sporadic values of k not relatively prime to the numerator of h(n, k). The nine such sporadic values of k less than 500, 000 are listed in the following table.

k  gcd of numerator
of h(2, k) and k
77  11
1247  43
9328  11
102608  11
102718  11
116413  11
116501  11
342441  1153
372780  109

Extensive numerical experimentation suggests that the numerator of h(n, k) and k are relatively prime for all n ≥ 3 and all k ≥ 1. That leads to the following conjecture:

Conjecture 3. For n ≥ 3 and k ≥ 1, with fractions written in lowest terms, the numerator of p(k, n) equals the numerator of h(n, k), and the denominator of p(k, n) is k times the denominator of h(n, k).

7 Conclusion

The probability that when a fair n-sided die with faces numbered 1 to n is tossed repeatedly, every face has come up at least once when face n appears for the k^{th} time is computed in several different ways. Comparing the results gives a number of summation identities involving binomial coefficients. The probability is related to a family of sequences in the OEIS.

What may initially seem paradoxical is the slow rate at which the value of k increases as n increases in order to guarantee say .99 probability that all n faces have appeared at least once when face n comes up for the k^{th} time. For example, for n = 2, the probability that both faces have come up first exceeds .99 for k = 7. For n = 10, it is k = 10. For n = 100, it is k = 14. For n = 1000, it is k = 17. For n = 10000, it is k = 20. These values suggest k grows as the log of n.

8 Acknowledgments

The authors would like to thank an anonymous referee for the very careful reading of this paper, several helpful suggestions, and, in particular, for spotting and correcting two substantial errors in an earlier version of this paper.

References

[1] L. Carlitz, A note on Wolstenholme’s theorem. Amer. Math. Monthly 61 (1954), 174–176.

[2] F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin & Company Limited, 1962.

[3] W. Feller, An Introduction to Probability Theory and Its Applications, 3rd ed., Vol. 1, John Wiley & Sons, 1968.

[4] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.

[5] J. G. Kemeny and J. L. Snell, Finite Markov Chains, D. Van Nostrand Co., Inc., 1960.

[6] T. Magliozzi and R. Magliozzi, Car Talk Radio Show, National Public Radio, February

   8 2003, http://www.cartalk.com/content/puzzlers/2003 and
   http://www.cartalk.com/content/prison-switcharoo-0.

2010 Mathematics Subject Classification: Primary 11B99; Secondary 60C05. Keywords: occupancy problem, waiting time, inclusion-exclusion counting, Stirling number of the second kind, Markov chain, binomial identity, binomial sum, multinomial sum, binomial transformation.

(Concerned with sequences \underline{A000012}, \underline{A001008}, \underline{A001240}, \underline{A027459}, \underline{A027462}, \underline{A028037}, \underline{A072913}, \underline{A099946}, \underline{A103878}, \underline{A126646}, and \underline{A131689}.)

Received October 28 2014; revised version received January 13 2015. Published in Journal of Integer Sequences, January 25 2015.

Return to Journal of Integer Sequences home page.