Suppose, we roll a fair die $n$ times. The expected value of how many times each side of the die will appear is $\frac{n}{6}$. The question is, what is the probability that any side of the die will come up more than $k$ times, where $n>k>\frac{n}{6}$? Or you could put it this way: what is the probability that no side will come up more than $k$ times? Clearly these two probabilities add up to 1.
Probability that no side of a dice is rolled more than $k$ times
-
0The question in https://math.stackexchange.com/questions/535868/probability-of-multiple-collisions-in-the-birthday-problem gives an approximate expression for the probability that at least one comes up at least $k$ times – 2017-11-02
3 Answers
I guess I figured it out. It turns out that this is computationally complex problem, but the idea is based on the multinomial distribution.
Multinomial distribution is generalization of Binomial distribution on the cases when you have arbitrary number of outcomes with fixed probabilities in each round. When the probabilities of outcomes are uniformly distributed we can write probability mass function as follows:
$\frac{L!}{\prod_{i=1}^n{\left[x_i!\right]}} n^{-\sum_{i=1}^{n}{x_i}}$
where, $L$ — number of die rolls, $n = 6$ number of equally alike outcomes and $x$ is outcome vector with $i$th element stands for how much times $i$th outcome has been seen. Mathematically speaking:
$x \in \mathbb{N}^n \mid \sum_{i=1}^{n}{x_i}=L$
The problem then is to find set of all possible outcome vectors $\mathrm{X}$ that:
$\forall x_i \in x \space x_i \leq k$
This is clearly computational problem, but when we know the set of matching outcome vectors $X$ then we can calculate overall probability that no side of a dice will come up greater than $k$ times
$ \sum_{x \in X}\left[ {\frac{L!}{\prod_{i=1}^n{\left[x_i!\right]}}n^{-\sum_{i=1}^{n}{x_i}} }\right] $
Let's look at the simplest cases and get the general idea from it.
$k=n-1$. Any specific sequence has probability (1/6)$^n$.
How many of these sequences have 1 occur $n-1$ times and 2 occur 1 time? $n$, since the 2 can occur in any one of the $n$ slots. So $n/6^n$ is the probability of $n-1$ 1s and one 2. But (1,2) is just one of the possible ordered pairs that achieve this. So now let's count the number of ordered pairs. Multiplying by it will provide the answer. This is easy to enumerate: {(1,2), (1,3), (1,4), (1,5), (1,6)} so there are 5 with 1 in the first position. The count will also be 5 for 2, 3, 4, 5, and 6. So we can do this $6(5) =30$ ways and so for $k=n-1$ the result is $n \cdot 6 \cdot 5/(6^n)= \frac{5n}{6^{n-1}}.$.
$k=n-2$. Now it is more complicated. We have to look at situations where one side occurs $n-2$ times and two others each occur once or one other occurs twice. First, let's count 1 occurring $n-2$ times 2 occurring 1 time and 3 occurring 1 time. This would be the number of ways can pick 2 slots out of $n$ for the triple (1,2,3) putting 2 in the slot furthest to the left. This number will then be multiplied by all ordered triples.
There are 3 ways to have 1 in the first slot and 2 in the second. The same is true for any other ordered pair. In the previous case, we found that there are 30 ordered pairs for the integers 1 to 6. So for distinct triples the probability is That would be $_nC_2= \frac{n!}{2! (n-2)!)}= \frac{3 (30)n(n-1)}{2 \cdot 6^n}= \frac{3 (15) n (n-1)}{6^n} = \frac{45n (n-1)}{6^{n}}.$
To this we need to add the triples that look like (1,2,2) multiplied by $1/6^n$. But these are in 1-1 correspondence with the ordered pairs (1,2,2) equivalent to (1,2) and (2,1,1) to (2,1). So we have 30 ordered pairs and since the first number can appear in any $n-2$ out of the $n$ slots or $_nC_2$ times. Hence we add $\frac{30 n (n-1)}{2 \cdot 6^n}=\frac{15 n (n-1)}{6^n}.$
The result is therefore $\frac{60 n(n-1)}{6^n} = \frac{10 n (n-1)}{6^{n-1}}.$
This seems to get more complicated but perhaps an induction formula can be found.
-
0@DenisBazhenov I haven't thought the whole thing through because this is a rather complex computational problem. But with regard to sequences like (1,1,1,6,6,6) I think this sextuple maps to the triplet (1,1,6). The first element is special because it is replicated n-5 times whereas permuting the other replicate sequences are indistinguishable. – 2012-07-07
For a fair die the probability that a particular side comes up on a roll is $1/6$. If you roll the die $n$ times the number of times that side comes up is binomial with success probability $1/6$. So for any $m$ the probability that the side occurs more than $m$ times is
$\sum_{k=m+1}^n {n \choose k} \left(\tfrac{1}{6}\right)^k \left(\tfrac{5}{6}\right)^{n-k}$
where ${n \choose k}= \frac{n!}{k! (n-k)!}$ (the number of ways to choose $k$ items out of $n$). In this case take $m = \lceil\frac{n}{6}\rceil$ where $\lceil r \rceil$ denotes the smallest integer greater than or equal to r.
-
0Yes, I understand that provided solution is correct for the any _single_ side of the die. But it's not the case. – 2012-07-07