\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf A Prisoner Problem Variation } \vskip 1cm \large 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\\ \href{mailto:jerry.metzger@und.edu}{\tt jerry.metzger@und.edu}\\ \href{mailto:thomas.richards@und.edu}{\tt thomas.richards@und.edu}\\ \end{center} \newcommand{\stirling}[2]{\left\{\genfrac{}{}{0pt}{}{#1}{#2}\right\}} \vskip .2in \begin{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^{\rm th}$ time. The results lead to a number of summation identities. The probabilities are related to several sequences in Sloane's {\it On-Line Encyclopedia of Integer Sequences}. \end{abstract} \section{Introduction} \subsection{The puzzle} {\it 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? } \bigskip That is the puzzle as presented by Tom and Ray Magliozzi on their National Public Radio show {\it Car Talk} \cite{mm}. \subsection{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 {\it 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 {\it visits} total; otherwise switch B is flipped. When the {\it 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. \subsection{A variation} In this note, the switches are removed from the puzzle and the number of prisoners is some $n\geq 1$. A monitor is elected whose duty is to declare, when escorted to the {\it 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 {\it occupancy problems} of the type discussed by David and Barton \cite{db}. In the terminology of that text, the problem would be presented as: {\it If balls are distributed one at a time randomly into boxes numbered $1,2,3,\dots,n$, what is the probability that there are no empty boxes when the $k^{\rm 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^{\rm th}$ time? \section{The {\it 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^{\rm th}$ time. When face $n$ comes up for the $k^{\rm th}$ time, and every other face has occurred at least once, the preceding tosses will consist of $j_{i}\geq 1$ occurrence of faces $i=1,2,\dots,n-1$ and $k-1$ occurrences of face $n$. The probability of any one such pattern is given by \[ \left(\frac{1}{n}\right)^{j_{1}+j_{2}+\cdots+j_{n-1}+ k-1}. \] The number of such patterns is given by the multinomial coefficient \[ \binom{j_{1}+j_{2}+\cdots+j_{n-1}+k-1}{ j_{1}, j_{2},\dots,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 \[ \sum_{j_1=1}^{\infty}\sum_{j_2=1}^{\infty}\cdots \sum_{j_{n-1}=1}^{\infty}\left(\frac{1}{n}\right)^{j_{1}+j_{2}+\cdots+j_{n-1}+ k-1}\binom{j_{1}+j_{2}+\cdots+j_{n-1}+k-1}{ j_{1}, j_{2},\dots,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^{\rm th}$ time is \begin{gather*} \frac{1}{n}\sum_{j_1=1}^{\infty}\sum_{j_2=1}^{\infty}\cdots \sum_{j_{n-1}=1}^{\infty}\left(\frac{1}{n}\right)^{j_{1}+j_{2}+\cdots+j_{n-1}+ k-1} \binom{j_{1}+j_{2}+\cdots+j_{n-1}+k-1}{ j_{1}, j_{2},\dots,j_{n-1},k-1} \\[10pt] =\sum_{j_1=1}^{\infty}\sum_{j_2=1}^{\infty}\cdots \sum_{j_{n-1}=1}^{\infty}\left(\frac{1}{n}\right)^{j_{1}+j_{2}+\cdots+j_{n-1}+ k} \binom{j_{1}+j_{2}+\cdots+j_{n-1}+k-1}{j_{1}, j_{2},\dots,j_{n-1},k-1}. \end{gather*} \section{The {\it inclusion{-}exclusion} solution} The probability is computed again, this time by inclusion{-}exclusion. For $j=1,2,\dots,n-1$, let $A_{j}$ be the event that face $j$ has not come up when face $n$ appears for the $k^{\rm th}$ time. Then the probability that every face has come up at least once when face $n$ is tossed for the $k^{\rm th}$ time is \[ p(n,k) = 1 - \Pr(A_{1} \text{ or } A_{2} \text{ or } \cdots\text{ or } A_{n-1}). \] Using the summation formula \[ \sum_{m=k}^{\infty} \binom{m-1}{k-1} x^{m} = \left(\frac{x}{1-x}\right)^{k}, \] it follows that for each of the $\binom{n-1}{j}$ possible choices of $j$ of the events, and for any $m\geq k$, the probability that face $n$ appears $k-1$ times in the first $m-1$ tosses, and face $n$ appears for the $k^{\rm th}$ time on toss $m$, is given by \[ \left(\frac{n-j-1}{n}\right)^{m-k} \left(\frac{1}{n}\right)^{k-1}\binom{m-1}{k-1} \frac{1}{n}. \] Consequently, \begin{align*} \Pr(A_{i_{1}} \text{ and } A_{i_{2}} \text{ and } \cdots \text{ and } A_{i_{j}}) &= \sum_{m=k}^{\infty} \left(\frac{1}{n}\right)^{k}\left(\frac{n-j-1}{n}\right)^{m-k} \binom{m-1}{k-1} \\[5pt] & = \left(\frac{1}{n}\right)^{k} \left(\frac{n}{n-j-1}\right)^{k}\,\sum_{m=k}^{\infty} \left(\frac{n-j-1}{n}\right)^{m} \binom{m-1}{k-1}\\[5pt] & = \left(\frac{1}{n-j-1}\right)^{k} \frac{\left(\frac{n-j-1}{n}\right)^{k}}{\left(1 - \frac{n-j-1}{n}\right)^{k}} = \frac{1}{(j+1)^{k}}, \end{align*} So, by inclusion{-}exclusion, the probability that every face has occurred at least once when face $n$ is rolled for the $k^{\rm th}$ time is \[ \left(\frac{1}{1}\right)^{k}\binom{n-1}{0} -\left(\frac{1}{2}\right)^{k}\binom{n-1}{1}+ \cdots +\left(\frac{1}{j}\right)^{k}\binom{n-1}{j-1}+ \cdots +(-1)^{n-1} \left(\frac{1}{n}\right)^{k}\binom{n-1}{n-1}\] \[=\sum_{j=1}^{n} (-1)^{j-1} \left(\frac{1}{j}\right)^{k} \binom{n-1}{j-1}.\] This leads to the unusual{-}looking identity \begin{gather*} \sum_{j_1=1}^{\infty}\sum_{j_2=1}^{\infty}\cdots \sum_{j_{n-1}=1}^{\infty}\left(\frac{1}{n}\right)^{j_{1}+j_{2}+\cdots+j_{n-1}+ k} \binom{j_{1}+j_{2}+\cdots+j_{n-1}+k-1}{j_{1}, j_{2},\dots,j_{n-1},k-1} \\[10pt] = \sum_{j=1}^{n} (-1)^{j-1} \left(\frac{1}{j}\right)^{k} \binom{n-1}{j-1}. \end{gather*} \section {The {\it waiting time} solution} The probability can also be thought of as a waiting time problem. See Feller \cite[p.\ 166]{feller}. Think of the rolls of the die as a sequence of Bernoulli trials with {\it success} being the occurrence of face $n$ with probability $p = \frac{1}{n}$ and {\it failure} being the occurrence of any other face with probability $q = 1-p = 1-\frac{1}{n}$. For $t\geq 0$, the probability of the $k^{\rm th}$ success on trial $k+t$ is the probability that exactly $t$ failures precede the $k^{\rm th}$ success. The probability of exactly $t$ failures in $k+t-1$ trials followed by success at trial $k+t$ is given by \begin{align*} \Pr(k^{\rm th} \text{ success at trial } k+t) &= \binom{k+t-1}{t}\left(\frac{1}{n}\right)^{k-1}\left(1 -\frac{1}{n}\right)^{t} \frac{1}{n}\\[5pt] &= \binom{k+t-1}{t}\left(\frac{1}{n}\right)^{k}\left(1 -\frac{1}{n}\right)^{t}. \end{align*} Next, an expression for the probability that faces $1,2,\ldots,n-1$, but not $n$, all occur in $t$ rolls ($t\geq n-1$, necessarily) is derived. Recall that $\stirling{t}{n-1}$, 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 \cite[p.\ 257]{gkp} for facts about the Stirling numbers. If the boxes are now made distinguishable, there are $(n-1)! \stirling{t}{n-1}$ distributions possible. Of the $(n-1)^{t}$ possible patterns of length $t$ of faces $1,2,\ldots,n-1$, the probability that each of those $n-1$ faces occurs at least once, with no face $n$, is therefore given by \[ \Pr(\text{faces } 1,2,\ldots, n-1 \text{ all occur in } t \text{ rolls}) = \frac{(n-1)!\stirling{t}{n-1}}{(n-1)^{t}}. \] It follows that the probability that every face has appeared at least once when face $n$ occurs for the $k^{\rm th}$ time is given by \begin{align*} \sum_{t=n-1}^{\infty} & \Pr(k^{\rm th} \text{ success at trial } k+t) \Pr(\text{faces } 1,2,\ldots, n-1 \text{ all occur in } t\text{ rolls})\\ &= \sum_{t=n-1}^{\infty}\frac{(n-1)!\stirling{t}{n-1}}{(n-1)^{t}}\left(\frac{1}{n}\right)^{k}\left(1 -\frac{1}{n}\right)^{t}\binom{k+t-1}{t}\\ \end{align*} The sequence $T(t,m) = m!\stirling{t}{m}$ (read by rows with $t\geq 0$, $0\leq m\leq t$) appears in the On-Line Encyclopedia of Integer Sequences as \seqnum{A131689}. There are two formulas for the entries in this sequence not mentioned in the OEIS. One, which is virtually the definition of $m!\stirling{t}{m}$, is \[ m!\stirling{t}{m} = \sum_{S_{t}} \binom{t}{t_{1},t_{2},\ldots,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},\ldots,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!\stirling{t}{m}$, also involving the sum over $S_{t}$ of all partitions of $t$ into $m$ positive parts, is not so obvious: \[ m!\stirling{t}{m} = \sum_{S_{t}} 1^{t_{1}}2^{t_{2}}\cdots m^{t_{m}}. \] To see this is correct, let $U(t,m) = \frac{1}{m!}\sum_{S_{t}} 1^{t_{1}}2^{t_{2}}\cdots 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: \[ \stirling{0}{0} = 1 \qquad \text{and} \qquad \stirling{t}{0} = 0 \quad \text{for } t>0. \] In addition, the Stirling numbers satisfy the recursion \[ \stirling{t}{m} = m\stirling{t-1}{m} + \stirling{t-1}{m-1} \quad \text{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 \begin{gather*} mU(t-1,m) + U(t-1,m-1) \\[5pt] = \frac{m}{m!} \sum_{A} 1^{t_{1}}2^{t_{2}}\cdots m^{t_{m}} + \frac{1}{(m-1)!}\sum_{B}1^{t_{1}}2^{t_{2}}\cdots (m-1)^{t_{m-1}} \\[5pt] = \frac{1}{m!} \sum_{A} 1^{t_{1}}2^{t_{2}}\cdots m^{t_{m}+1} + \frac{1}{m!}\sum_{B}1^{t_{1}}2^{t_{2}}\cdots (m-1)^{t_{m-1}}m \\[5pt] \end{gather*} 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 $\stirling{t}{m}$ and $U(t,m)$ have the same initial conditions and obey the same recursion, it follows that \[ m!\stirling{t}{m} = \sum_{S_{t}} 1^{t_{1}}2^{t_{2}}\cdots m^{t_{m}}. \] Comparing the various expressions derived here with the result of the inclusion{-}exclusion computation gives several summation identities: \begin{align*} p(n,k) &= \sum_{j=1}^{n} (-1)^{j-1} \left(\frac{1}{j}\right)^{k} \binom{n-1}{j-1}\\ &= \sum_{t=n-1}^{\infty}\frac{(n-1)!\stirling{t}{n-1}}{n^{k+t}} \binom{k+t-1}{t}\\ &= \sum_{t=n-1}^{\infty}\sum_{S_{t}}\frac{1}{n^{k+t}} \binom{t}{t_{1},t_{2},\ldots,t_{m}}\binom{k+t-1}{t}\\ &= \sum_{t=n-1}^{{\infty} }\sum_{S_{t}} \frac{1^{t_{1}}2^{t_{2}}\cdots(n-1)^{t_{n-1}}}{n^{k+t}}\binom{k+t-1}{t}, \end{align*} where, in the last two expressions, the sums are taken over the set $S_{t}$ of all ordered partitions, $(t_{1},t_{2},\dots,t_{n-1})$, of $t$ into $n-1$ positive parts. \section {The {\it 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 \cite[p.\ 43]{ks} is used in what follows. In Figure \ref{markov}, the initial state is labeled $\genfrac{[}{]}{0pt}{}{0}{0}$. 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 {\it different} faces from $1,2,3,\dots,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,\dots,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$. \begin{figure}[htbp] \begin{center} \includegraphics[width=5.5truein, height=3.5truein]{markov-1.eps} \caption{\bf The Markov Process with absorbing states.} \label{markov} \end{center} \end{figure} For each of the non{-}absorbing states $\genfrac{[}{]}{0pt}{}{s}{t}$, 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 $\genfrac{[}{]}{0pt}{}{0}{0}$, ending with $k(n-1)$ for state $\genfrac{[}{]}{0pt}{}{n-2}{k-1}$. 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, \ldots, s_{k(n-1)}$, the canonical transition matrix has the form \[ P = \left[ \begin{array}{c|c} I & 0 \\ \hline R & Q \end{array} \right] = \left[\begin{array} {cc|ccccc} 1 & 0 & 0 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & 0 & 0 & \cdots & 0\\ \hline & {\kern -15pt R} & & & Q & & \\ \end{array}\right], \] where $R$ is the $k(n-1)\times 2$ matrix giving the probabilities of moving from a transient state to one of the absorbing states, and $Q$ is the $k(n-1)\times 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=\left[ \begin{array} {cc|ccccc} 1 & 0 & 0 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & 0 & 0 & \cdots & 0\\ \hline & {\kern -15pt R} & & & Q & & \\ \end{array} \right] = \left[ \begin{array}{cc|cccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\[.5em] 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\[.5em] \hline 0 & 0 & 0 & \frac{4}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\[.5em] 0 & 0 & 0 & \frac{1}{5} & \frac{3}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 \\[.5em] 0 & 0 & 0 & 0 & \frac{2}{5} & \frac{2}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 \\[.5em] \frac{1}{5} & 0 & 0 & 0 & 0 & \frac{3}{5} & 0 & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 & 0 \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{4}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 & 0 \\[.5em] 0 & 0 &0 & 0 & 0 & 0 & 0 & \frac{1}{5} & \frac{3}{5} & 0 & 0 & \frac{1}{5} & 0 & 0 \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{2}{5} & \frac{2}{5} & 0 & 0 & \frac{1}{5} & 0 \\[.5em] \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{3}{5} & 0 & 0 & 0 & \frac{1}{5} \\[.5em] 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{4}{5} & 0 & 0 \\[.5em] 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{1}{5} & \frac{3}{5} & 0 \\[.5em] 0 & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{2}{5} & \frac{2}{5} \\[.5em] \frac{1}{5} & \frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{3}{5} \\[.5em] \end{array} \right]. \] In this example, the fundamental matrix $N =(I-Q)^{-1}$ is given by \[ N = \left[ \begin{array}{cccccccccccc} 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} \\[.5em] 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} \\[.5em] 0 & 0 & \frac{5}{3} & \frac{5}{3} & 0 & 0 & \frac{5}{9} & \frac{25}{18} & 0 & 0 & \frac{5}{27} & \frac{95}{108} \\[.5em] 0 & 0 & 0 & \frac{5}{2} & 0 & 0 & 0 & \frac{5}{4} & 0 & 0 & 0 & \frac{5}{8} \\[.5em] 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & \frac{1}{5} & \frac{9}{20} & \frac{47}{60} & \frac{77}{60} \\[.5em] 0 & 0 & 0 & 0 & 0 & \frac{5}{4} & \frac{5}{4} & \frac{5}{4} & 0 & \frac{5}{16} & \frac{35}{48} & \frac{65}{48} \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{3} & \frac{5}{3} & 0 & 0 & \frac{5}{9} & \frac{25}{18} \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{2} & 0 & 0 & 0 & \frac{5}{4} \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{4} & \frac{5}{4} & \frac{5}{4} \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{3} & \frac{5}{3} \\[.5em] 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \frac{5}{2} \\[.5em] \end{array} \right]. \] 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 =\left[ \begin{array}{cc} \frac{12019}{18000} & \frac{5981}{18000} \\[.5em] \frac{415}{576} & \frac{161}{576} \\[.5em] \frac{85}{108} & \frac{23}{108} \\[.5em] \frac{7}{8} & \frac{1}{8} \\[.5em] \frac{137}{300} & \frac{163}{300} \\[.5em] \frac{25}{48} & \frac{23}{48} \\[.5em] \frac{11}{18} & \frac{7}{18} \\[.5em] \frac{3}{4} & \frac{1}{4} \\[.5em] \frac{1}{5} & \frac{4}{5} \\[.5em] \frac{1}{4} & \frac{3}{4} \\[.5em] \frac{1}{3} & \frac{2}{3} \\[.5em] \frac{1}{2} & \frac{1}{2} \\[.5em] \end{array} \right], \] which agrees with \[ p(5,3) = \sum_{j=1}^{5} (-1)^{j-1}\left(\frac{1}{j}\right)^{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\times n-1$ matrices \[ A = \left[ \begin{array}{cccccc} 0 & \frac{n-1}{n} & 0 & 0 & \cdots & 0\\[.7em] 0 & \frac{1}{n} & \frac{n-2}{n} & 0 & \cdots & 0\\[.7em] 0 & 0 & \frac{2}{n} & \frac{n-3}{n} & \cdots & 0\\[.7em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.7em] 0 & 0 & 0 & 0 & 0 & \frac{n-2}{n}\\[.7em] \end{array} \right] \qquad \text{ and } \qquad D = \left[ \begin{array}{cccccc} \frac{1}{n} & 0 & 0 & 0 & \cdots & 0\\[.7em] 0 & \frac{1}{n} & 0 & 0 & \cdots & 0\\[.7em] 0 & 0 & \frac{1}{n} & 0 & \cdots & 0\\[.7em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.7em] 0 & 0 & 0 & 0 & 0 & \frac{1}{n}\\[.7em] \end{array} \right]. \] For $I$ representing identity matrices of appropriate sizes and with $\bf{0}$ representing the $n-1 \times n-1$ zero matrix, $I-Q$ is the $k\times k$ block matrix \[ I-Q = \left[ \begin{array}{cccccc} I-A & -D & \bf{0} & \bf{0} & \cdots & \bf{0}\\[.5em] \bf{0} & I-A & -D & \bf{0} & \cdots & \bf{0}\\[.5em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.5em] \bf{0} & \bf{0} & \bf{0} & \bf{0} & \cdots & I-A\\[.5em] \end{array} \right]. \] The matrix $D = \frac{1}{n}I$ commutes with $I-A$. Consequently, $N = (I-Q)^{-1}$ is \[ N = \left[ \begin{array}{cccccc} (I-A)^{-1} & D(I-A)^{-2} & D^{2}(I-A)^{-3}& D^{3}(I-A)^{-4} & \cdots & D^{k-1}(I-A)^{-k}\\[.5em] \bf{0} & (I-A)^{-1} & D(I-A)^{-2} & D^{2}(I-A)^{-3} & \cdots & D^{k-2}(I-A)^{-k+1} \\[.5em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.5em] \bf{0} & \bf{0} & \bf{0} & \bf{0} & \cdots & (I-A)^{-1}\\[.5em] \end{array} \right]. \] The matrix $I-A$ can be written as \begin{align*} I-A &= \left[ \begin{array}{cccccc} 1 &\displaystyle -\frac{n-1}{n} & 0 & 0 & \cdots & 0\\[.7em] 0 &\displaystyle 1-\frac{1}{n} &\displaystyle -\frac{n-2}{n} & 0 & \cdots & 0\\[.7em] 0 & 0 &\displaystyle 1-\frac{2}{n} &\displaystyle -\frac{n-3}{n} & \cdots & 0\\[.7em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.7em] 0 & 0 & 0 & 0 & 0 &\displaystyle 1-\frac{n-2}{n}\\[.7em] \end{array} \right] \\[1em] &= \frac{1}{n} \left[ \begin{array}{cccccc} n & -(n-1) & 0 & 0 & \cdots & 0\\[.7em] 0 & n-1 & -(n-2) & 0 & \cdots & 0\\[.7em] 0 & 0 & n-2 & -(n-3) & \cdots & 0\\[.7em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.7em] 0 & 0 & 0 & 0 & 0 & 2\\[.7em] \end{array} \right] \end{align*} That last matrix can be diagonalized, with the eigenvalues $n,n-1,n-2,\dots,2$, in that order, along the diagonal, by multiplying on the left and right by \[ S = S^{-1} = \left[ \begin{array}{cccccc} \binom{n-1}{0} & -\binom{n-1}{1}& \binom{n-1}{2} & -\binom{n-1}{3} & \cdots & (-1)^{n }\binom{n-1}{n-2}\\[.7em] 0 & -\binom{n-2}{0} & \binom{n-2}{1} & -\binom{n-2}{2} & \cdots & (-1)^{n}\binom{n-2}{n-3}\\[.7em] 0 & 0 & \binom{n-3}{0}& -\binom{n-3}{1} & \cdots & (-1)^{n}\binom{n-3}{n-4}\\[.7em] \vdots & \vdots & \vdots & \vdots & & \vdots\\[.7em] 0 & 0 & 0 & \cdots & \cdots & (-1)^{n}\binom{1}{0}\\[.7em] \end{array} \right] \] 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 \[ \sum_{j=1}^{k} \frac{1}{n} c_{j}, \] where $c_{j}$ is the $(1,n-1)$ entry in \[ D^{j-1}(I-A)^{-j} = \left(\frac{1}{n}I\right)^{j-1}\left(\frac{1}{n}SES\right)^{-j} = nSE^{-j}S. \] That gives one more expression for $p(n,k)$: \begin{align*} p(n,k) &= \sum_{j=1}^{k}\frac{1}{n}\sum_{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}\\[5pt] &= \sum_{j=1}^{k}\sum_{m=1}^{n-1} (-1)^{n+m-1} \binom{n-1}{m-1}\frac{n-m}{(n-m+1)^{j}}. \end{align*} \section {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^{\rm 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,\dots,n$, and let \[ G_{n}(x) = \frac{1}{\prod_{j=1}^{n} (1- \frac{L_{n}}{j} x)} = \frac{n!}{\prod_{j=1}^{n} (j- L_{n}x)} = n! \prod_{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: \begin{align*} \seqnum{A000012} &: G_{1}(x) = 1+x+x^{2} + x^{3} + \cdots +x^{n} + \cdots\\[7pt] \seqnum{A126646} &: G_{2}(x) = 1+ 3x + 7x^{2} + 15x^{3}+31x^{4} + \cdots + (2^{n+1}-1)x^{n} + \cdots\\[7pt] \seqnum{A001240} &: G_{3}(x) = 1+ 11x + 85x^{2} + 575x^{3} + \cdots\\[7pt] \seqnum{A028037} &: G_{4}(x) = 1 + 25x + 415x^{2} + 5845x^{3} +\cdots\\[7pt] \seqnum{A103878} &: G_{5}(x) = 1 +137x + 12019x^{2} + \cdots\\[7pt] \end{align*} The generating functions in this family are related in a simple way involving the probabilities \[ p(n,k) = \sum_{j=1}^{n} (-1)^{j-1}\left(\frac{1}{j}\right)^{k} \binom{n-1}{j-1}. \] In fact, \begin{align*} G_{n}(x) &=\sum_{k=0}^{\infty} \left[\sum_{j=1}^{n}(-1)^{j-1}\left(\frac{1}{j}\right)^{k}\binom{n-1}{j-1}\left(\frac{nL_{n}^{k}}{j}\right)\right]x^k\\[5pt] &= \sum_{k=0}^{\infty}\left[\sum_{j=1}^{n}(-1)^{j-1}\left(\frac{L_{n}}{j}\right)^{k} \binom{n}{j}\right]x^{k}. \end{align*} To show this is the expansion of $G_{n}(x)$, it is sufficient to determine the expansion of \[ g_{n}(x) =\prod_{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) =\prod_{k=1}^{n} \frac{1}{1- \frac{1}{k} x} = \frac{A_{1}}{1-\frac{x}{1}} +\frac{A_{2}}{1-\frac{x}{2}} +\cdots+\frac{A_{n}}{1-\frac{x}{n}}. \] Consequently \[ 1 = {A_{1}}{\prod_{\genfrac{}{}{0pt}{}{k=1}{k\not=1}}^{n}\left(1-\frac{x}{k}\right)} +{A_{2}}{\prod_{\genfrac{}{}{0pt}{}{k=1}{k\not=2}}^{n}\left(1-\frac{x}{k}\right)} +\cdots+{A_{n}}{\prod_{\genfrac{}{}{0pt}{}{k=1}{k\not=n}}^{n}\left(1-\frac{x}{k}\right)}. \] For each $j=1,2,\dots,n$, setting $x = j$ in turn gives \[ 1 = A_{j} {\prod_{\genfrac{}{}{0pt}{}{k=1}{k\not=j}}^{n}\left(1-\frac{j}{k}\right)} = (-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) = \sum_{k=0}^{\infty} \left[\sum_{j=1}^{n} A_j \left(\frac{1}{j}\right)^k\right]x^{k} = \sum_{k=0}^{\infty} \left[\sum_{j=1}^{n} (-1)^{j-1} \left(\frac{1}{j}\right)^k\binom{n}{j}\right]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} = \left(1,1,1,\ldots,1,\ldots \right) \] so $h_{1,k} = 1$ for all $k\geq 1$. For $n >1$, the $k^{\rm th}$ term of the sequence $h_{n}$ is given by \[ h_{n,k} = \sum_{j=1}^{k} \frac{h(n-1,j)}{j}. \] The first few sequences in this family are \begin{align*} h_{1} &= \left(1,1,1,\ldots,1,\ldots \right)\\[5pt] h_{2} &= \left(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},\ldots\right)\\[5pt] h_{3} &= \left(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},\ldots\right)\\[5pt] h_{4} &= \left( 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},\ldots \right)\\[5pt] h_{5} &= \left(1,\frac{31}{16},\frac{3661}{1296},\frac{76111}{20736},\frac{58067611}{12960000},\frac{68165041}{12960000},\frac{187059457981}{31116960000},\frac{3355156783231}{497871360000},\ldots\right) \end{align*} The terms of the sequence $h_{2}$ are the harmonic numbers, with the $k^{\rm 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. \begin{align*} \seqnum{A001008} &:1, 3, 11, 25, 137, 49, 363, 761, 7129, 7381, 83711, 86021, 1145993, 1171733, \ldots\\[3pt] \seqnum{A027459} &: 1,7,85,415,12019,13489,726301,3144919,30300391,32160403,4102360483,\ldots\\[3pt] \seqnum{A027462} &: 1,15,575,5845,874853,336581,129973303,1149858589,101622655189,\ldots\\[3pt] \seqnum{A072913} &:1,31,3661,76111,58067611,68165041,187059457981, 3355156783231\ldots\\[3pt] \end{align*} \begin{theorem} \label{h=kp} For $n,k\geq 1$, we have $h(n,k) = kp(k,n)$. \end{theorem} \begin{proof} The proof will be by induction. For $n=1$ and all $k\geq 1$, we see \[ h(1,k) = 1 = k\left(\frac{1}{k}\right) = kp(k,1). \] Assuming that $h(n-1,k) = kp(k,n-1)$ for some $n\geq 2$ and all $k\geq 1$, we see that, for any $k\geq 1$, \begin{align*} h(n,k) &= \sum_{j=1}^{k} \frac{h(n-1,j)}{j} = \sum_{j=1}^{k} \frac{jp(j,n-1)}{j}\\[5pt] &= \sum_{j=1}^{k}\sum_{m=1}^{j}(-1)^{m-1}\frac{1}{m^{n-1}}\binom{j-1}{m-1} = \sum_{m=1}^{k}\sum_{j=m}^{k}(-1)^{m-1}\frac{1}{m^{n-1}}\binom{j-1}{m-1}\\[5pt] &= \sum_{m=1}^{k} (-1)^{m-1}\frac{1}{m^{n}} \left(\sum_{j=m}^{k} m\binom{j-1}{m-1}\right) = \sum_{m=1}^{k} (-1)^{m-1}\frac{1}{m^{n}}\left( k\binom{k-1}{m-1}\right)\\[5pt] &= kp(k,n). \end{align*} The next to last equality follows from the {\it upper summation identity}, \[ \sum_{m=t}^{s} \binom{m}{t} = \binom{s+1}{t+1}\quad \text{ for } s\geq t, \] that shows \[ \sum_{j=m}^{k} m\binom{j-1}{m-1} = m\sum_{j=m}^{k} \binom{j-1}{m-1} = m\binom{k}{m} = m\left(\frac{k}{m}\right)\binom{k-1}{m-1} = k\binom{k-1}{m-1}. \] \end{proof} It follows from Theorem~\ref{h=kp} 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. \begin{theorem}{\label{applyWol}} If $p\geq 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. \end{theorem} \begin{proof} Carlitz \cite{carlitz} established an extension of Wolstenholme's theorem by showing that for a prime $p\geq 5$ \[ \frac{1}{kp+1}+ \frac{1}{kp+2} + \frac{1}{kp+3}+ \cdots + \frac{1}{(k+1)p -1} \equiv 0 \,\pmod{p^2}, \] so that $p^2$ is a factor of the numerator of that sum written in lowest terms. Now \begin{align*} h(2,p(p-1)) & = \sum_{j=1}^{p(p-1)} \frac{1}{j} = \left(\sum_{k=0}^{p-2} \sum_{j=1}^{p-1} \frac{1}{kp+j} \right)+ \frac{1}{p}+\frac{1}{2p} +\cdots+ \frac{1}{(p-1)p}\\[5pt] & = \left(\sum_{k=0}^{p-2} \sum_{j=1}^{p-1} \frac{1}{kp+j} \right)+ \frac{1}{p}\left(1+\frac{1}{2} + \cdots +\frac{1}{(p-1)}\right). \end{align*} For each $k=0,1,\ldots,p-2$, write, in lowest terms, \[ \frac{1}{kp+1}+ \frac{1}{kp+2} + \frac{1}{kp+3}+ \cdots + \frac{1}{(k+1)p -1} = \frac{p^2 n_k}{m_k}. \] So \[ h(2,p(p-1)) = \frac{1}{p}\left(\frac{p^2n_0}{m_0}\right)+\sum_{k=0}^{p-2}\frac{p^2n_k}{m_k} = \frac{pn_0}{m_0}+\sum_{k=0}^{p-2}\frac{p^2n_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$. \end{proof} In addition to the values of $k$ given by Theorem~\ref{applyWol}, there are rare {\it 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. \begin{center} \begin{tabular}{|c|c|} \hline $k$ & gcd of numerator\\ \ & of $h(2,k)$ and $k$\\ \hline $77$ & $11$ \\ \hline $1247$ & $43$ \\ \hline $9328$ & $11$ \\ \hline $102608$ & $11$ \\ \hline $102718$ & $11$ \\ \hline $116413$ & $11$ \\ \hline $116501$ & $11$ \\ \hline $342441$ & $1153$ \\ \hline $372780$ & $109$ \\ \hline \end{tabular} \end{center} Extensive numerical experimentation suggests that the numerator of $h(n,k)$ and $k$ are relatively prime for all $n\geq 3$ and all $k\geq1$. That leads to the following conjecture: \begin{conjecture} For $n\geq 3$ and $k\geq 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)$. \end{conjecture} \section{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^{\rm 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^{\rm 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$. \section{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. \begin{thebibliography}{9} \bibitem{carlitz} L.{~}Carlitz, A note on Wolstenholme's theorem. {\it Amer. Math. Monthly\/} {\bf 61} (1954), 174--176. \bibitem{db} F. N.{~}David and D. E.{~}Barton, \textit{Combinatorial Chance}, Charles Griffin \& Company Limited, 1962. \bibitem{feller} W.{~}Feller, \textit{An Introduction to Probability Theory and Its Applications}, 3rd ed., Vol.~1, John Wiley \& Sons, 1968. \bibitem{gkp} R.{~}Graham, D.{~}Knuth, and O.{~}Patashnik, {\it Concrete Mathematics}, 2nd ed., Addison-Wesley, 1994. \bibitem{ks} J. G.{~}Kemeny and J. L.{~}Snell, \textit{Finite Markov Chains}, D. Van Nostrand Co., Inc., 1960. \bibitem{mm} T.{~}Magliozzi and R.{~}Magliozzi, Car Talk Radio Show, National Public Radio, February 8 2003, \url{http://www.cartalk.com/content/puzzlers/2003} and\newline \url{http://www.cartalk.com/content/prison-switcharoo-0}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11B99; Secondary 60C05. \noindent \emph{Keywords}: occupancy problem, waiting time, inclusion{-}exclusion counting, Stirling number of the second kind, Markov chain, binomial identity, binomial sum, multinomial sum, binomial transformation. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000012}, \seqnum{A001008}, \seqnum{A001240}, \seqnum{A027459}, \seqnum{A027462}, \seqnum{A028037}, \seqnum{A072913}, \seqnum{A099946}, \seqnum{A103878}, \seqnum{A126646}, and \seqnum{A131689}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received October 28 2014; revised version received January 13 2015. Published in {\it Journal of Integer Sequences}, January 25 2015. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}