Number of combinations of $m$ numbers such that $k$ is the second (or $x$th) highest?

Question

Looking to code some probabilities based on dice rolls, but a mechanic that is slowing me down deals with isolating the value shown by the second highest rolled die (and subsequently third highest, etc.)

So say I've got $n$ fair dice of size $m$, of the $m^n$ possible permutations sorted by size, how often would you expect to see k in the second highest slot, assuming $k = 1,…,m$?

I did some brute force up to $5$ d4s to see if I could infer any trends. This question led me to the formula $k^n - (k-1)^n$ to calculate occurance rates of highest values, and I can retrofit it to give lowest value by $(m-k+1)^n - (m-k)^n$. This has worked for all values I've been able to brute force.

Knowing how to calculate highest and lowest and knowing that total occurance rate for any given number is m^n means that I can derive the middle value when $n=3$, by using $m^n - (m-k+1)^n - (m-k)^n - k^n - (k-1)^n$, so a general form for all $n$ could be linked to that somehow, but I'm unable to derive it offhand.

So ndm is 3d4, there are $64$ possible permutations, only one roll can provide a $1$ as the highest value ${1,1,1}$, but seven rolls can put $2$ as the highest value $\lbrace1,1,2\rbrace,\lbrace1,2,1\rbrace,\lbrace2,1,1\rbrace,\lbrace1,2,2\rbrace,\lbrace2,1,2\rbrace,\lbrace2,2,1\rbrace$ and $\lbrace2,2,2\rbrace$, nineteen rolls put $3$ as the highest value, and thirty-seven rolls put $4$ in the highest slot. In the lowest slot, $4$ mirrors the $1$ for the lowest, with only $\lbrace4,4,4\rbrace$ working, low three mirrors high two with seven rolls, two has nineteen, and one has thirty-seven.

What I'm looking for is some equation that would allow me to calculate the occurrence rates for each non-highest or lowest slot, so with the 3d4 example, one crops up in second place ten times, two shows up twenty two times, as does three, and four is back down to ten.

How would I find the occurrence rates for the second highest in things like 4d4 when one shows up $13$ times, two $67$ times, three $109$ times and four $67$ times? Then beyond that, what would be the general form for the number of times $k$ shows up as the $x$th term of $n$ dice of size $m$?

Answer 1

I found this question which pointed me to Wikipedia's entry on Order Statistics and discrete random variables, and included this summation (sorry for not knowing mathjax) sum (n choose j)((1−(k/m))^j(k/m)^(n−j)−(1−(k/m)+(1/m))^j((k/m)−(1/m))^(n−j)), j=0 to n-x

I then plugged that into Wolfram Alpha as I couldn't figure how to get summation iteration to work at this level in excel with the m,n and x for values of dice size, number of dice and position I want to find (1 being lowest die, n being highest) respectively. This equation gave probability equations for values k, while I was looking for occurance rate, but plugging in dice values for the situations I had already brute forced got me the answers I needed as long as I remembered to multiply by the total possible outcomes.

So for rolling five d4 and looking for the second highest (so x of 4) I went to wolfram alpha, put in "sum (n choose j)((1−(k/m))^j(k/m)^(n−j)−(1−(k/m)+(1/m))^j((k/m)−(1/m))^(n−j)), j=0 to n-x for m=4, n=5, x=4" and got out 1/256(-5x^4+30x^3-40x^2+25x-6) into which you can multiply by m^n (or in this case drop the fraction and multiply by four as 4^5 is 4 times 256), plug in a k dice value and each answer matched what I had brute forced. Putting in 4(-5x^4+30x^3-40x^2+25x-6) for x=2 gave 176, the correct number of twos that can appear as the second highest number in the 1024 permutations of five d4.

Thank you all for your assistance, hope this can help anyone else looking for something similar.

Answer 2

Fix $k \in \{1,...,m\}$. We roll $n$ fair die with $m$ faces and order resulting numbers by magnitude. What is the probability the second highest die has magnitude $k$? Well this is precisely the probability that $n-2$ die have result in $\{1,...,k\}$, one dice has result $=k$, and one dice has result in $\{k,...,m\}$. We count the number of ways this could happen. There are $_n C_{n-2} = \frac{n(n-1)}{2}$ subsets of the $n$ die of size $n-2$. For each of these subsets, there is precisely $k^{n-2}$ ways of having the outputs between $\{1,...,k\}$ for each dice in the subset. Once a size $n-2$ subset is fixed and the outputs are all between 1 and $k$, there are precisely $2(m-k+1)$ ways to choose the remaining two die so that the second highest magnitude dice has magnitude $k$ (one of the dice has to have magnitude $k$ and the other can be any of the $m-k+1$ values $\{k,...,m\}$, the two comes from the fact that we can choose either of the two die to be the one with magnitude $k$). The $2(m-k+1)$ choice are independent of the $k^{n-2}$ choices, hence for each fixed size $n-2$ subset of $n$ die, there are $2(m-k+1)k^{n-2}$ different ways to have $k$ be the magnitude of the 2nd highest magnitude dice. Since there are $\frac{n(n-1)}{2}$ distinct such subsets, there are at most $n(n-1)k^{n-2} (m-k+1)$ distinct ways to have $k$ be the magnitude of the 2nd highest magnitude dice.

This provides an upper bound on the probability, but there is some over-counting going on (you can convince yourself that the case where all the dice come out as $k$ get counted for size $n-2$ subset). I don't have the dedication to figure out exactly how much over-counting there is, but perhaps you can.