10
$\begingroup$

A recent question has inspired the following one.

$M$ people ($M\ge2$) play the following game. Each round every person admitted to the round rolls a $K$-sided dice ($K\ge2$), the sides being marked with numbers from $1$ to $K$. If only a single person has the highest score, the game ends. Otherwise the people with the highest score are admitted to the next round and the game continues. What is the probability that the game ends exactly in $n$ rounds?

$\endgroup$
1

2 Answers 2

8
$\begingroup$

Neat problem! Thanks for posting.

The first thing to notice is that at any state of the game, if you have $a$ players remaining, then the probability of yielding $b$ players in the next round is independent of which round you're at. Hence we can talk about $P(a,b)$, the probability of transitioning from $a$ players to $b$ players in one round.

Playing a round with $a > 1$ players, there $K^a$ possible rolls. To find the number of ways we end up with $b \geq 1$ players, we first note that there are $a \choose b$ ways to pick which $b$ players continue. Then, letting $k$ denote the value that these $b$ players roll, we find that there are $(k-1)^{a-b}$ ways for the players to roll this result: the $b$ continuing players must all roll $k$, and the remaining players must all roll between $1$ and $k-1$. Hence we can write (with the convention $0^0 = 1$) $$P(a,b) = \frac{{a\choose b}\displaystyle\sum_{k=1}^K (k-1)^{a-b}}{K^a}$$

Once you have these probabilities, the game itself is a Markov chain. Your states are the integers from $1$ to $M$ denoting the number of players remaining. In any step, the probability of transitioning from state $a$ to state $b$ with $a \ge b \ge 1$ and $a \ne 1$ is exactly $P(a,b)$. State 1 is an absorbing state, and transitions to state 1 with probability 1. All other transition probabilities are 0. So your transition matrix looks like $$T=\left(\begin{matrix}P(M,M) & P(M,M-1) & P(M,M-2) & \cdots & P(M,1)\\ 0 & P(M-1,M-1) & P(M-1,M-2) & \cdots & P(M-1,1)\\ &&\vdots\\0 & 0 & \cdots & P(2,2) & P(2,1)\\ 0 & 0 & \cdots & 0 & 1\end{matrix}\right)$$

The entry in the upper right corner of $T^n$ is the probability of being in state 1 (i.e. the game has ended) after $n$ rounds. But, since this is an absorbing state, this is the probability that the game ends in round $n$ or before. To get the probability of ending after exactly $n$ rounds, you need to subtract the entry in the upper right corner of $T^{n-1}$ from the upper right entry of $T^n$.

$\endgroup$
5
  • $\begingroup$ Thank you for this nice and very profound answer. I came almost to the same point and found closed-form solution for $M=3$. I wonder if it is managable to find such closed-form expression for $\left (T^n\right)_{M,1}$ in general case. $\endgroup$
    – user
    Feb 21, 2019 at 22:21
  • $\begingroup$ One suggesion. The expressions will look nicer if you redefine $k\mapsto k+1$. Besides it is necessary in the expression for $P (a,b) $ to start the summation with $k=0$ (in your version with $k=1$) together with the convention $0^0=1$. Otherwise the expression gives wrong value for $a=b $. $\endgroup$
    – user
    Feb 21, 2019 at 22:31
  • $\begingroup$ I doubt a closed form is possible for general $M$. There is an alternative with a rational multivariate generating function, but it essentially just reproduces the matrix multiplication in polynomial form. The problem is that the number of "paths" from $M$ to $1$ becomes uncontrollable as $n$ gets larger. $\endgroup$ Feb 21, 2019 at 22:34
  • $\begingroup$ Yes, you are right. I will edit the solution. But I believe leaving the index of summation as $k$ is important for the clarity of the argument, even though it leads to a slightly less elegant expression for $P(a,b)$. $\endgroup$ Feb 21, 2019 at 22:34
  • $\begingroup$ It has appeared that the problem does admit a closed-form solution (see my answer). $\endgroup$
    – user
    Feb 25, 2019 at 2:31
5
$\begingroup$

The aim of this answer is to present a closed-form solution for the problem. It represents further development of the idea described in the answer of Jeremy Dover. The hard and probably boring part of the proof will be given in the appendix.

For convinience we rewrite the $M\times M$ dimensional matrix $T(M,K)$ introduced by Jeremy Dover as: $$ T_{ij}=\frac 1{K^i}\binom ij\sum_{k=0}^{K-1}k^{i-j}. $$ In the sense of transition states the process starts at $T_{MM}$ and ends at $T_{M1}$.

As the matrix $T$ is triangular its eigenvalues are trivially its diagonal elements $\lambda_m=T_{mm}=\frac{1}{K^{m-1}},\; m=1\dots M.$ As all eigenvalues are distinct the matrix is apparantly diagonalizable by a similarity transformation: $$ \text{diag}(\lambda_1,\lambda_2,\dots,\lambda_M)=X^{-1}TX. $$ Knowing the transformation matrix $X$ the powers of the matrix $T$ can be computed as: $$ T^n=X\text{diag}(\lambda_1^n,\lambda_2^n,\dots,\lambda_M^n)X^{-1}.\tag1 $$

Fortunately, the structures of matrices $X$ and $X^{-1}$ are rather simple (see Appendix): $$ X_{ij}=(1-\delta_{i,j-1})\binom i{j-1};\quad X^{-1}_{ij}=\frac 1i\binom ij b_{i-j}, $$ where $b_k$ are the Bernoulli numbers ($b_1=-\frac12$).

Plugging the values into (1) one obtains: $$ T^n_{M1}(M,K)=\sum_{m=1}^M X_{Mm}\lambda_m^n X^{-1}_{m1} =\sum_{m=1}^M\binom M{m-1}\frac{b_{m-1}}{K^{(m-1)n}} =\sum_{m=0}^{M-1}\binom M{m}\frac{b_{m}}{K^{nm}}.\tag2 $$

Finally, the probability for the game to end in the $n$-th round reads: $$ \boxed{P_n(M,K)=T^n_{M1}-T^{n-1}_{M1}=\sum_{m=0}^{M-1}\binom M{m}\frac{1-K^m}{K^{nm}}b_{m}.} $$


Note added:

It may be convenient to rewrite the expression (2) as: $$ T^n_{M1}(M,K)={\cal B}_M\left(\frac1{K^n}\right), $$ where the function ${\cal B}_M(x)$ is defined as: $$ {\cal B}_M(x)=\sum_{m=0}^{M-1}\binom M{m}b_{m}x^m\equiv x^M\left[B_M\left(\frac1x\right)-b_M\right], $$ with $B_M(x)$ being the Bernoulli polynomial.


Appendix

Proposition 1. The following identity holds for any $p,n\in\mathbb Z_+$: $$ \sum\limits_{k=0}^{p-1} {\binom {p} k} \sum\limits_{j=0}^{n-1} j^k=n^p.\tag{*} $$

Proof: $$\begin {align} &(j+1)^{p}=\sum\limits_{k=0}^{p} {\binom {p} k} j^k\\ \implies& (j+1)^{p} - j^{p} =\sum\limits_{k=0}^{p-1} {\binom {p} k} j^k\\ \implies&\sum\limits_{j=0}^{n-1} \left[(j+1)^{p} - j^{p}\right] = \sum\limits_{j=0}^{n-1} \sum\limits_{k=0}^{p-1} {\binom {p} k} j^k\\ \implies& n^{p}= \sum\limits_{k=0}^{p-1} {\binom {p} k} \sum\limits_{j=0}^{n-1} j^k. \end {align} $$ Introducing the notation $S^{(n)}_k= \sum\limits_{j=0}^{n-1} j^k$ the set of the equations $(*)$ with the exponent of $n$ varying from $1$ to $p$ is equivalent to the matrix equation: $$ \left(\begin{array}l n\vphantom{\binom00}\\ n^2\vphantom{\binom00}\\ n^3\vphantom{\binom00}\\ \vdots\\ n^p\vphantom{\binom00} \end{array}\right)= \begin{pmatrix} \binom10&0&0&\cdots& 0\\ \binom20&\binom21&0&\cdots& 0\\ \binom30&\binom31&\binom32&\cdots& 0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ \binom p0&\binom p1&\binom p2&\cdots& \binom p{p-1}\\ \end{pmatrix} \left(\begin{array}l S^{(n)}_0\\ S^{(n)}_1\\ S^{(n)}_2\\ \vdots\\ S^{(n)}_{p-1} \end{array}\right). $$

Denoting the matrix of binomial coefficients as $X$, one observes that its determinant is non-zero and the equation can be inverted obtaining: $$ \left(\begin{array}l S^{(n)}_0\\ S^{(n)}_1\\ S^{(n)}_2\\ \vdots\\ S^{(n)}_{p-1} \end{array}\right)= \begin{pmatrix} X^{-1}_{11}&0&0&\cdots& 0\\ X^{-1}_{21}&X^{-1}_{22}&0&\cdots& 0\\ X^{-1}_{31}&X^{-1}_{32}&X^{-1}_{33}&\cdots& 0\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ X^{-1}_{p1}&X^{-1}_{p2}&X^{-1}_{p3}&\cdots& X^{-1}_{pp}\\ \end{pmatrix} \left(\begin{array}l n\vphantom{\binom00}\\ n^2\vphantom{\binom00}\\ n^3\vphantom{\binom00}\\ \vdots\\ n^p\vphantom{\binom00} \end{array}\right). $$

Comparing the expression with the well-known one: $$ S^{(n)}_{p-1}=\frac1p\sum_{j=0}^{p-1}\binom pj b_j n^{p-j}= \frac1p\sum_{j'=1}^{p}\binom p{j'} b_{p-j'} n^{j'},\tag{**} $$ one obtains:

Proposition 2. The matrix elements of $X^{-1}$ are: $$ X^{-1}_{ij}=\frac 1i\binom ij b_{i-j}, $$ where $b_k\equiv b^-_k$ are the Bernoulli numbers taken with the convention $b_1=-\frac12$. Observe that on the cited above Wikipedia page the formula similar to (**) is given for $S^{(n+1)}_p$ in terms of $b^+$ without a direct mention of this.

Proposition 2 can be proved also directly.

Proposition 3. The columns of the matrix $X$ are the eigenvectors of the matrix $T$.

Proof. Acting by matrix $T$ on the $m$-th column of the matrix $X$: $$ v^{(m)}_j=\begin{cases} 0,& 1\le j<m;\\ \binom{j}{m-1},& m\le j\le M. \end{cases} $$ one obtains: $$\begin{align} \sum_{j=1}^M T_{ij} v^{(m)}_j &=\sum_{j=m}^M\frac 1{K^i}\binom ij\binom{j}{m-1}\sum_{k=0}^{K-1}k^{i-j}\\ &=\frac 1{K^i}\binom i{m-1}\sum_{j=m}^i\binom{i+1-m}{i-j}\sum_{k=0}^{K-1}k^{i-j}\\ &=\frac 1{K^i}\binom i{m-1}\sum_{j'=0}^{i-m}\binom{i+1-m}{j'}\sum_{k=0}^{K-1}k^{j'}\\ &\stackrel{(*)}=\frac 1{K^i}\binom i{m-1}K^{i+1-m}\\ &=\frac 1{K^{m-1}}\binom i{m-1}=\lambda_m v^{(m)}_i. \end{align} $$

$\endgroup$
1
  • 2
    $\begingroup$ Very, VERY nice! $\endgroup$ Feb 25, 2019 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.