# Probability that no side of a dice is rolled more than $k$ times

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.

-
So are you asking for probability that no side of dice will come up for more than k times or that a particular given side will not come up more than k times? – Wonder Jul 6 '12 at 11:15
I think it must be one particular side. If you are asking that none of the six sides come up more than the greatest integer of n/6 then you are asking for the probability that all sides come up exactly n/6 times (assuming n is a multiple of six). – Michael Chernick Jul 6 '12 at 12:25
If the question says "any side of a dice will come up no more than k times", I would interpret that as "no side comes up more than $k$ times" – Arthur Jul 6 '12 at 12:37
Yes, exactly. I mean no side comes up more than $k$ times. Changed question a little bit, to be more clear about it. – Denis Bazhenov Jul 7 '12 at 0:00
Are you looking for exact formulas, or (upper) bounds? – TMM Jul 7 '12 at 0:07

Let's look at the simplest cases and get the general idea from it. 1. 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 number 1s and 1 number 2. But (1,2) is just 1 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.(1,2) 2. (1,3) 3. (1,4) 4. (1,5), 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 6 5/(6$^n$)= 5n/ 6$^n$ $^-$ $^1$.

1. k=n-2 Now it is more complicated we have to look at situations where one side occurs n-2 time and two others each occur once or one other occurs twice. First let's count 1 occurring n-2 times 2 occuring 1 time and 3 occuring 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 nC2=n!/(2! (n-2)!)=

3 (30)n(n-1)/(2 6$^n$)= 3 (15) n (n-1)/6$^n$=

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 correspondencewith 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 nC2 time. Hence we add 30 n (n-1) /(2 6$^n$)

=15 n (n-1)/ 6$^n$.

The result is therefore 60 n(n-1)/6$^n$ = 10 n (n-1)/6$^n$ $^-$ $^1$.

This seems to get more complicated but perhaps an induction formula can be found.

-
I can't figure out the simple approach to eliminate double counts from sequences when $\frac{n}{2}>k>\frac{n}{6}$. Suppose $n=6$ and $k=3$, with naive combinatorial approach we will double count sequence {1,1,1,6,6,6} (one time for a 1, and one time for a 6). How could we eliminate those? – Denis Bazhenov Jul 7 '12 at 11:38
@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. – Michael Chernick Jul 7 '12 at 12:37

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.

-
Binomial is about number of successes in sequence of experiments where we have only two outcomes. And this is perfectly fit if I need to calculate the probability of $any fixed$ side of a dice. But I need to calculate the probability that no side of a dice will come up more than $k$ times. I guess I was a little bit confusing about subject of question, sorry :) – Denis Bazhenov Jul 7 '12 at 0:12
I don't care that you have six outcomes. I dichotomized. If you want to know how many times the side with 1 dot comes up you have p=1/6 as the probability that a 1 dot come up on any roll of the DIE (die is singular, dice is plural)and 5/6 is the probability that some other value comes up. So if you are asking about the chance for any specified side my answer is correct. – Michael Chernick Jul 7 '12 at 1:35
Yes, I understand that provided solution is correct for the any single side of the die. But it's not the case. – Denis Bazhenov Jul 7 '12 at 9:09

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]$$

-