2
$\begingroup$

I am having trouble with solving the following problem:

The probability that a $d$-sided dice lands on its $k$th side is equal to $p_k$ for $k\in \{k\in\mathbb{N},k≤d\}$ and $p_1+p_2+p_3+...+p_d=1$. Roll this dice (at least once) until every side is rolled equally many times. Find a function $F(p_1,p_2...)$ which gives the expected number of rolls $n$ after which that happens.

I have attempted to solve it by counting distinct sequences, and than taking a weighted average: the sum of all $n$s times the probability of this occurring after $n$ rolls. Using this method, I have managed to obtain a result for a two-sided dice (a coin) by using Catalan numbers. This does, however, not work for higher dimensions.

Does anyone have an idea on how this could be solved for at least a 3 or 4-sided dice?

Edit: I gave my idea for counting the distinct sequences for an equality to occur after exactly $n$ steps in this post: Number of ways a dice can roll every side equally many times for the first time after x rolls

$\endgroup$
  • 3
    $\begingroup$ Consider the random walk on the cubic lattice whose steps are $(1,0,0)$, $(-1,0,0)$, $(0,1,0)$, $(0,-1,0)$, $(0,0,1)$ and $(0,0,-1)$ if the roll of the dice is $1$, $2$, $3$, $4$, $5$ or $6$ respectively. Then the random walk is at $(0,0,0)$ at least every time every side is rolled equally many times. One knows the 3D simple random walk is transient hence its return time is infinite with positive probability, hence, with positive probability, the six sides of the die are never rolled equally many times. In particular the expectation you are after is infinite. $\endgroup$ – Did Jan 30 '16 at 16:43
  • $\begingroup$ For a 4-sided die, the same reasoning shows that the time until every side is rolled equally many times has infinite expectation. For a 2-sided die (aka a coin), the time until every side is rolled equally many times is almost surely finite and has infinite expectation, hence I am curious to see the result you say you obtained in this case. $\endgroup$ – Did Jan 30 '16 at 16:45
  • 1
    $\begingroup$ This is not what your question asks at all. Note that as soon as some $p_i$ are unequal, the probability that every side is rolled equally many times ever, is less than 1. $\endgroup$ – Did Jan 30 '16 at 17:10
  • 1
    $\begingroup$ The unequal case is really elementary: pick some sides $i\ne j$ with $p_i\ne p_j$ and record only the rolls $i$, encoded as a step $+1$, and the rolls $j$, encoded as a step $-1$. The resulting integer-valued process is a biased one-dimensional random walk, which returns to zero with probability less than $1$. Hence already the time for sides $i$ and $j$ to be rolled equally many times, has infinite expectation. $\endgroup$ – Did Jan 30 '16 at 17:40
  • 2
    $\begingroup$ @Did Perhaps you should write that as an answer? $\endgroup$ – leonbloy Jan 30 '16 at 18:08
0
$\begingroup$

With no further assumptions, it's zero rolls.

For every side to be rolled equally many times, with $k$ sides, you must roll a multiple of $k$ times, say $jk$ times. The condition is surely met with $j=0$. If the condition is ever to be met for larger $j$, at least two assumptions that you have not stated are needed:

  • You must roll the die at least once.
  • The probability of rolling a given side is neither zero nor one.

Without these assumption, we stand on $j=0$, the number of rolls is zero.

$\endgroup$

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.