How to determine the number of trials done for a discrete uniform random distribution?

Question

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)

Answer 1

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!

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.