Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say I have a discrete uniformly random die which rolls values in the range $[min,max]$. And say I roll that die $N$ times and record the total sum $Sum$.

Given $min$, $max$, and $Sum$, I'd like to determine $N$ with some amount of certainty.

So for example, let's say I roll a normal 6-sided die $N$ times and get a sum of 30. I'd like to know, with, say, 95% certainty, a range of values that $N$ is in.

(This is not a homework question; I encountered the problem when writing this answer and realized I have no idea how to solve it)

share|improve this question

5 Answers 5

up vote 1 down vote accepted
+50

It seems from your answer to the RPG question that you're interested in the case where the number of rolls is relatively large, so I'm going to make some approximations.

This is basically a question in renewal theory. The theorem that you want is the renewal central limit theorem - see for example "A Central Limit Theorem" here. The notation is a bit tricky, but essentially:

  • the die rolls become the "interarrival process". So you have $X = (X_1, X_2, \ldots)$ which are all independent and uniformly distributed; in particular they have the discrete uniform distribution on $[a, b]$, so $E(X) = (b+a)/2$ and $Var(X) = ((b-a+1)^2-1)/12$. For ease of notation later, we'll set $\mu = (b+a)/2$ and $\sigma^2 = ((b-a+1)^2 - 1)/12$.

  • the "counting variable" $N_t$ is the number of die rolls needed to reach the sum $t$.

  • by the renewal CLT, $N_t$ is approximately normal with mean $t/\mu$ and standard deviation $\sigma \sqrt{t/\mu^3}$.

Let's look at the case in your original question. There you have $t = 3393-700 = 2693$. The minimum and maximum interarrival times are $a = 18, b = 30$, so $\mu = 24, \sigma = \sqrt{(13^2-1)/12} = \sqrt{14}$. The mean number of generations is therefore $2693/24 \approx 112.2$ and the standard deviation is $\sqrt{14} \sqrt{2693/24^3} \approx 1.65$, so a 95-percent confidence interval would be something like $112.2 \pm 3.2$.

share|improve this answer

This question is a typically well-known question in Estimation Theory.

Using Maximum Likelihood Estimation we can find the most probable value for $N$, with respect to $sum$, $min$ , and $max$.

We know that the probability distribution for one roll is $$ P[x_i=n]=\frac1{max-min+1}, \qquad n=min,min+1,\cdots, max $$ and since rolls are independent of each others, we know that the probability distribution of $y=\sum_{i=1}^N x_i$ is convolution of pdf of each $x_i$. Therefore her it is N times convolution of $P[x_i=n]$ by itself (or inverse Z-transform of Z-transform of $P[x_i=n]$ to the power of $N$)

In Maximum likelihood estimation we are looking for a value of the parameter of $N$ that maximizes likelihood of observing $y = sum$. So the problem is : $$ \max_N f(N)=P(n=sum|N) = \\ \mathcal Z^{-1}\left[\left(\mathcal Z \left[\frac1{max-min+1}\left(\delta(n-min)+\cdots + \delta(n-max)\right)\right]\right)^N\right]\large|_{n=sum} \\ = \left( \frac1{max-min+1} \right)^N\mathcal Z^{-1}\left[\left(z^{-min} + \cdots + z^{-max} \right)^N\right]\large|_{n=sum} $$ where $\mathcal Z$ and $\mathcal Z^{-1}$ are Z-transform and inverse Z-transform operators, respectively.

Now all of that you should do is finding $N$ which maximizes $f(N)$, which is as simple as doing a derivation!

share|improve this answer
    
MLE yields a pointwise estimate while the OP asks for a confidence interval. –  Did Aug 1 '13 at 19:21
    
@Did Yes you are right. But after finding the most probable $N$, he could evaluate $P(n=sum|N)$ for $N$ in neighborhood of that $N$, and see how the probability decreases. –  Mahdi Khosravi Aug 1 '13 at 20:03
1  
Sorry but I fail to see a relationship between P(Sum=n|N) and a CI for N. –  Did Aug 1 '13 at 23:59

You need to describe what has made the experiment stop at that result.

If $min, max, N, Sum$ are all positive, perhaps somebody was aiming at $Sum$ with the intention of restarting the experiment if they had missed $Sum$ after $max$ throws knowing they would never hit it. Then you could work out the probability of hitting $Sum$ after a given number of steps, and this would give you a distribution for $N$.

So in your example of a standard fair die, you would have for example a probability of hitting $Sum=30$ with $N=5$ of $\frac{1}{6^5}$, a probability of $N=10$ of $\frac{2930455 }{6^{10}}$, and a probability of $N=29$ of $\frac{29}{6^{29}}$, etc. [This Java applet counts compositions, for example with "Compositions of" 30, "Exact number of terms" 10, and "Each term no more than" 6, though there are other approaches.] Add up the probabilities and they come to about $0.28569$, so you need to divide them each by this to give a distribution with a total probability of $1$.

You will find that the mean is about $8.81$, the median $9$ and the mode $8$. You would not have been far away with the simpler approximation $\frac{Sum}{(min+max)/2}$ which in this case is about $8.57$. The intervals $[6,11]$ and $[7,12]$ each cover just over 95% of the probability.

share|improve this answer
    
This implicitely assumes a uniform prior on N. –  Did Aug 1 '13 at 19:23
    
@Did: The description of the experiment in my second paragraph, with repeats if the pre-decided $Sum$ is missed, leads directly to the probabilities. No prior is necessary (or indeed meaningful). There may be a Bayesian formulation with a particular improper prior combining with the likelihood to produce the same results, but I do not regard it as the same thing: "equivalent to" might be better than "implicitly assumes" –  Henry Aug 1 '13 at 21:58
    
Sorry but I fail to see how the repeated experiment in your second paragraph is related to the question asked. –  Did Aug 2 '13 at 0:03
    
@Did: It gives a mechanism for reaching a pre-decided $Sum$ almost surely. –  Henry Aug 2 '13 at 0:16

I have wrote a hand-written solution, I hope it will not annoy you much.

ANSWER

share|improve this answer
    
@blueraja If you need any clarification, do ask. –  kaka Aug 1 '13 at 18:04
    
Since this is a discrete uniform random variable pdf would not be $\frac1{b-a}$ and also here CRT theorem doesn't apply, so you can't assume $S$ is a normal random variable –  Mahdi Khosravi Aug 1 '13 at 18:34
    
Thats why, I transform back to discrete domain by taking the ceiling and floor functions. –  kaka Aug 1 '13 at 19:16

Well If you let $S=X_1+X_2+...+X_N$ where $X_1,...,X_N$ are random variables representing each dice roll then mgf of S is

$M(t)=\frac{1}{6^N}(e^t+e^{2t}+...+e^{6t})^N$ so $P(S=s \, and \, N=n)$ is the coefficient of $e^{st}$ in this which you can find a formula for.

You could model $N$ as

$P(N=n/S=s)=P(S=s \, and \, N=n)/P(S=s)$

a conditional r.v this would be possible just sum P(S=s) across all values of N that could give that sum. Then find the Expected value and the probabilty of n(s) around that till you get close to .95. This is only really practical with a computer but the answer will be exact not an aproximation.

For example for $s=4$ $N$ can be $1$ to $4$ and doing the above calculations give $P(N=1)=.629$ , $P(N=2)=.314$ , $P(N=3)=.0524$ and $P(N=4)=.002915$ so you can be 95% confident that you rolled once or twice.

This was all done with a 6 sided dice but you just have to change the mgf for a different dice this will even work for negative numbers on a dice or non identical dice... the mgf for max, min would be $M(t)=\frac{1}{(max-min)^N}(e^{min*t}+e^{(min+1)t}+...+e^{max*t})^N$ and everything is the same.

share|improve this answer
    
Oh i see I answered the wrong question but at least you have the distribution. –  rummi Aug 7 '13 at 20:04
    
K i fixed it to answer op's question –  rummi Aug 7 '13 at 20:26
    
if you dont know how to find formula for the coefficient of $e^{st}$ I could add that to answer. –  rummi Aug 7 '13 at 21:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.