If a trial consists of throwing an n-sided fair die having numbers a1,a2,a3...,an on its faces. What will be the expected number of trials required before we get atleast k1 times a1, k2 times a2,....kn times an.

I think it can be modelled as the expected value of negative multinomial distribution because each individual follows a multinomial distribution. In the simpler case where the trial is binomial, we can model "The expected number of trials required before we get k successes" as negative binomial.

An example for understanding...suppose that there is 3 sided dice with numbers 1,2 and 3 and I want to know the expected number of trials before I get to see say 4 1s, 5 2s and 6 3s.

PS: I cannot find any good free resource available on the net on Negative multinomial distributions

  • $\begingroup$ "Dice" is plural. The singular is "die". Is this a fair die? $\endgroup$ – saulspatz Jul 29 '19 at 23:27
  • $\begingroup$ Thanks, I edited the Question. yeah, the die is fair $\endgroup$ – Prabhat Sharma Jul 30 '19 at 1:00

I don't normally like to make two answers to the same question, but this approach is so different from my prior answer that it seems like the right thing to do. Again, I'll just discuss your example.

We can model the problem as a finite-state absorbing Markov chain. We represent the state of the system as an ordered triple $(i,j,k)$ with $0\leq i\leq4,\ 0\leq j\leq5,\ 0\leq k\leq6.$ This means that $i$ $1$'s, $j$ $2$'s, and $k$ $3$'s have been rolled, except that if $i=4$ it means that at least $4$ $1$'s have been rolled, and similarly when $j=5$ or $k=6$. The chain has $210$ states, and the state $(4,5,6)$ is the only absorbing state.

As explained on the Wikipedia page, there is an exact formula for the expected time to absorption. I wrote a python script to calculate it.

import numpy as np
from functools import reduce
import itertools
import sys

def product(seq):
    return reduce(lambda x,y:x*y, seq, 1)

def indexFunction(seq):
    s = [s+1 for s in seq]
    coeffs = [1]
    for t in s[:-1]:

    def index(seq):
        z = zip(coeffs, seq)
        return sum(a*b for a,b in z)

    return index

def transitionFunction(seq):
    def trans(state, i):
        state = list(state)
        state[i] = min(state[i]+1, seq[i])
        return state
    return trans

def rolls(seq):
    n = product(s+1 for s in seq)  # number of states
    p = 1/len(seq)                         # probability of given roll
    states = itertools.product(*(range(s+1) for s in seq))
    index = indexFunction(seq)
    trans = transitionFunction(seq)

     # build transition matrix
    Q = np.zeros((n,n))  
    for s in states:
        source = index(s)
        for i in range(len(seq)):
            target = index(trans(s, i))
            Q[source, target] += p

     # expected time to absorption        
    Q= Q[:-1,:-1]         
    I = np.eye(n-1)
    N= np.linalg.inv(I-Q) 
    one = np.ones((n-1))
    return (N@one)[0]

seq= [int(arg) for arg in sys.argv[1:]]
for idx, t in enumerate(seq):
    print('%d occurs at least %d times'%(idx+1,t))
print(rolls(seq), "expected rolls")

Assuming this script is named rolls.py, then

python rolls.py 4 5 6


1 occurs at least 4 times
2 occurs at least 5 times
3 occurs at least 6 times
21.389264801531347 expected rolls

so about $21.4$ rolls are required.

This script will work for any number of faces on the die, and any number of required occurrences, so long as the overall matrix doesn't get too big.

| cite | improve this answer | |
  • $\begingroup$ @saulpatz Thanks for your answer. Can you suggest me a beginner-friendly link for understanding markov chain. This problem I actually encountered as a dynamic programming problem but I thought it may be solved directly using probability concepts. $\endgroup$ – Prabhat Sharma Jul 30 '19 at 20:41
  • $\begingroup$ I'm afraid I don't know of any such links, and since I don't know your mathematical background, I don't know what you would consider friendly. All I can suggest is that you Google "Markov chain" and look at what comes up. For example, this page has a good description, although the emphasis is on modeling, rather than probability. Just thing about why the $n$th power of the transition matrix gives the $n$-step transition probabilities. (It's just matrix multiplication.) $\endgroup$ – saulspatz Jul 30 '19 at 21:03
  • $\begingroup$ Thanks @saulspatz. I've understood Markov chains and solved my problem :) $\endgroup$ – Prabhat Sharma Jul 31 '19 at 19:49

I'll just treat your example. I'm not sure how difficult it would be to express this in closed form; I haven't tried. We must distinguish between the cases where the last throw, the one that fulfills all the conditions, is a $1,2,$ or $3$. Suppose it is a $1$. Then we know that we threw $k\geq5$ $2$'s and $j\geq6$ $3$'s and that in the $k+j+3$ rolls prior to the last we rolled exactly $3$ $1$'s. We can make similar analyses when the last roll was a $2$ or a $3$. The expected number of rolls is $$\sum_{k=5}^\infty\sum_{j=6}^\infty(k+j+4){k+j+3\choose3,k,j}3^{-(k+j+4)}+\\ \sum_{i=4}^\infty\sum_{j=6}^\infty(i+j+5){i+j+4\choose4,i,j}3^{-(i+j+5)}+\\ \sum_{i=4}^\infty\sum_{k=5}^\infty(i+k+6){i+k+5\choose5,i,k}3^{-(i+k+6)} $$ where, of course, the first sum deals with the case where a $1$ is rolled last, the second where $2$ is last, and the third where $3$ is last.

| cite | improve this answer | |
  • $\begingroup$ Is it necessary that we roll 3 1's exactly k+j+3 rolls prior to current roll? Can't we roll 1 in between k+j+3 roll i.e. say first we roll say 2 1's then k-m 2's and j-m 3's then roll 1 1's and then remaining m 2s and m 3's? $\endgroup$ – Prabhat Sharma Jul 30 '19 at 1:08
  • $\begingroup$ Btw I found this which address my problem. $\endgroup$ – Prabhat Sharma Jul 30 '19 at 1:09
  • $\begingroup$ It has to be true for some values of $k$ and $j$. We must have rolled $3$ $1$'s prior to the fourth one, right? $\endgroup$ – saulspatz Jul 30 '19 at 2:04
  • $\begingroup$ Yes, I should have thought of the double dixie-cup paper. I know I've read it, but I can't recall exactly what it says at the moment. $\endgroup$ – saulspatz Jul 30 '19 at 2:06
  • $\begingroup$ But still, the papers attached are too complex and gives a closed-form solution involving solving of integrals $\endgroup$ – Prabhat Sharma Jul 30 '19 at 12:55

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.