0
$\begingroup$

Suppose we have $k$ fair $n$-sided die (so each face rolls with probability $1/n$), with each face of the die labelled as $a_i$ $ (i=1, \ldots, n)$, with the values of the $a_i$ being unknown to us.

Whenever we throw the $k$ dice (call this a $k$-roll), by means of magic/a friend, we are told what the sum of the dice rolls are. Then what is the expected number of $k$-rolls in order to determine what the $a_i$ are uniquely?


Firstly, I feel that I should justify that this method can determine the $a_i$ uniquely in a finite number of $k$-rolls. The general jist is that we can ignore the cases where we get a solution except for when we $k$-roll the same face $k$ times; the full proof is given below.

Proof: Let $S$ be the set of $k$-rolls which all give the same face, so $|S| = n$, and thus the probability of $k$-rolling and getting a $\bar{r} \in S$ is $n/n^k = n^{k-1}$. Therefore, almost surely we will eventually $k$-roll a $\bar{r} \in S$, which gives us (without loss of generality) all $a_1$'s, and therefore we get an equation $ka_1 = \lambda_1$ say, so regardless of whether we knew what $a_1$ was before this point, we know that almost surely we'll know it after a finite number of $k$-rolls. Now if $S_1 = S \setminus \{ \text{the $k$-roll with all faces $a_i$} \}$, the probability of $k$-rolling and getting a $\bar{r} \in S_1$ is $(n-1)/n^k$, so by repeating the argument from before, we know almost surely there's a finite amount of time between knowing $a_1$ and knowing $a_1$ and $a_2$ (say). Repeating this argument inductively gives the result.

Letting $E(k,n)$ be the expected number of $k$-rolls required when we have $n$ dice, then there are a few simple cases:

  • $E(1,n) = nH_n$ - Here $H_n$ is the $n$-th harmonic number, so $H_1 = 1, H_2 = 3/2,$ etc. If $X_j$ is the number of $1$-rolls necessary to determine $j+1$ of the $a_i$ already knowing $j$ of them, then $X_0 + X_1 + \ldots + X_{n-1}$ is the number of rolls necessary to have $1$-rolled each $a_i$ at least once. As each of the $X_j$ are distributed geometrically with parameter $1 - j/n$, it follows that $$ \mathbb{E}(X_0 + X_1 + \cdots + X_{n-1}) = \sum_{j=0}^{n-1} \frac{n}{n-j} = n \sum_{j=1}^n \frac{1}{j} = nH_n.$$ I want to use a similar argument, along with the proof from earlier, to conclude that $E(n,k) \leq n^kH_n$, but I'm not too sure if I can do so.

  • $E(k,1) = 1$ - This shouldn't come as a suprise to anyone.

Unfortunately, for the vastly more complicated cases, I'm pretty clueless as how to proceed. Maybe there's some method of conditioning on cases to give recurrence relations, or some clever way of dealing with the simulataneous equations, but I can't see one. Dealing with things case by case can get nasty fairly quickly (for example, for $E(2,2)$, even though there are only $3$ equations to worry about it, $a_1 + a_2 = ?$ occurs with probability $1/2$, whereas the other two occur with probability $1/4$, so there are no nice symmetry approaches). Does anyone have any ideas? While asking for an exact answer may be asking too much, if anyone can provide asymptotic values, or answers for special cases (say $E(2,n)$ for $n \geq 2$), I'd probably accept those.

$\endgroup$
  • $\begingroup$ I don't see a way to do this in the generality you ask for. It depends on how many duplicates there are in the sums of the $a_i$ $\endgroup$ – Ross Millikan Sep 15 '14 at 2:31
  • $\begingroup$ @RossMillikan By "duplicates there are in the sums of the $a_i$", do you mean the number of times we rethrow something of the type $a_1 + 3a_2 = 5$, i.e. when a new roll of the dice gives one we've already found, or that we rolled $3$ of the $a_i$ in the above to begin with? $\endgroup$ – Andrew D Sep 15 '14 at 15:33
  • $\begingroup$ I was thinking of multiple ways to make the same sum. For two six-sided dice you can make $7$ in $6$ different ways, for example. $\endgroup$ – Ross Millikan Sep 15 '14 at 18:14
  • $\begingroup$ @RossMillikan Ah, I see what you mean. $\endgroup$ – Andrew D Sep 15 '14 at 18:30
  • $\begingroup$ @AndrewD: I'm terribly sorry, I've erroneously downvoted your question, instead of upvoting it. If you modify your question without changing the content, I will undo my downvote! Best regards, $\endgroup$ – Markus Scheuer Apr 23 '15 at 6:59
2
$\begingroup$

Doesnt exist a method for this if you want a fixed expected number of rolls. The expected number of rolls to determine the sample-space is reciprocally defined by the composition of dice, the sample-space isnt fixed to an exact number of sums.

You can throw dice at the moment where the apparition of new sums (the sample-space) decrease to a point (I dont know in this moment how you can calculate it... it maybe a function related to an expected number of samples and that follow the law of larger numbers... this depend on the information you have about what is rolled as number of dice or number of sides of each dice).

The representations of frequency vs sum is a "discrete curved distribution" that represent the coefficients of a polynomial, so you must fit to this shape a polynomial that represent the generating function for this setup. Because the dice are fair the generating function will be of the type

$$f(x)=\prod_{j}\left(\sum_{i} x_j^{a_i}\right)^{n_j}$$

where the $j$ represent a type of dice with a determined composition of $a_i$, and $n_j$ the number of dice of this type rolled. If i is the same for all dice the task maybe more easy. Two problems from here:

1) Searching the original generating function from the plain generating function

2) May exist more than one solution for a distribution

The complexity depends about the info that you have... if you know how much dice are rolled or the number of sides of the dice rolled.

By now I dont know the possible techniques to "reverse-engineering" a plain generating function. I hope this answer maybe useful to you. Maybe you can approach to this using the reverse of a discrete Fourier transform.

$\endgroup$
  • $\begingroup$ The idea of looking at generating functions could be quite useful - I'll have a go with it at some point. Thanks! $\endgroup$ – Andrew D Sep 15 '14 at 15:35

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.