4
$\begingroup$

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.

  • 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?2012-07-06
  • 0
    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).2012-07-06
  • 1
    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"2012-07-06
  • 0
    Yes, exactly. I mean no side comes up more than $k$ times. Changed question a little bit, to be more clear about it.2012-07-07
  • 0
    Are you looking for exact formulas, or (upper) bounds?2012-07-07
  • 0
    I guess upper bound would be sufficient for my purposes2012-07-07
  • 0
    Okay so I guess now you are picking a k strictly greater smallest integer greater than n/6. This will certainly depend on what k you choose and is not possible for k= smallest integer greater than n/6 because one side comes up on every draw implying the sum of the times each side comes up must equal n. If one is less than n/6 at least 1 must be greater.2012-07-07
  • 0
    The 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$ times2017-11-02

3 Answers 3

0

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

1

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$ 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}}.$$.

  2. $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
    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?2012-07-07
  • 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
0

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.

  • 0
    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 :)2012-07-07
  • 0
    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.2012-07-07
  • 0
    Yes, I understand that provided solution is correct for the any _single_ side of the die. But it's not the case.2012-07-07