Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose a dice with $q$ faces is rolled $N$ times, where $N$ is very big.

We define a multinomial variable $X=(X_1,\ldots,X_q)$ which counts how many times any face is occurred ($X_i$ is the number of occurrence of the $i$-th face).

Suppose we don't know if the dice is fair or not, namely if the probability distribution of the outcome of the dice is uniform or not.

If we know the value of $X$, how can we use it to estimate the probability distribution of the dice?

In particular, let $\epsilon>0$ be fixed. How can we use the value of $X$ to understand if there's a face $i$ such that $|P(\mbox{the dice's outcome is } i) -\frac{1}{q}|>\epsilon$?

Clearly, I expect to use a statistical method, hence my prediction can be wrong, but I would like to esteem my error probability.

ps: in the case $q=2$, it can be made defining the binomial which counts how many times one of the two faces occurs. If $N$ is big, that binomial can be approximated by a gaussian and the gaussian has mean $\frac{N}{2}$ if and only if the dice is fair. Thus we can settle a threshold $T>0$ and say that the dice is fair if $|X-\frac{N}{2}|>T$ and is unfair otherwise. $T$ is choosen according to the minimum value for $\epsilon$ and the error probability can be easily computed with the normal table.

share|improve this question
add comment

4 Answers 4

Use concentration of measure. For 2 dimensions, Hoeffding's inequality. See the appendix of the book on empirical processes by van der Vaart and Wellenr for the multinomial case.

share|improve this answer
add comment

The conjugate prior of the multinomial distribution is Dirichlet -- it is a distribution over the parameters (the probabilities of outcomes) of the multinomial.

Define

D = Dirichlet(X + 1)

(the 1 represents the non-informative prior belief that all probability vectors are equiprobable.)

And then integrate over the region of the pdf that you're interested in.

I can expand on this answer if you like.

share|improve this answer
add comment

The classical approach is to build a Neyman-Pearson style hypothesis test (warning: incredibly ugly mathematics, in desperate need of replacement, but ubiquitous).

Say you rolled your die $N$ times to produce $X$. Let the multinomial distribution have parameters $(p_1, p_2, ..., p_6)$, where $\sum_i p_i = 1$. Then construct a one dimensional measure such as $Q = \| X/N - p \|$, using your favorite $p$-norm. Calculate the probability distribution of $Q$.

Your null hypothesis in this case is $p_i = \frac{1}{6}$ for all $i$. For a test of level of significance $\alpha$ (conventionally 0.05 or 0.01), there is a region $[a,b]$ such that $\int_a^b p(Q = x) dx = 1 - \alpha$. Actually, there are many such, and there are other criteria to choose among them. In your case, invariance might be a good one: you expect the whole problem to be symmetric if you let $Q$ go to $-Q$, in which case the interval should be symmetric about 0, i.e., $[-a,a]$.

For a given value of $Q$ from your data, you do the integral over $[-Q,Q]$ and get $1 - \alpha$. That $\alpha$ is the lowest level of significance at which the observed data will be significant.

As I said, classical hypothesis testing is a very ugly theory. There are other approaches, such as minimax tests which you can construct via Bayes priors, since the set of all Bayes priors contains but is usually not much larger than the set of all admissible statistical procedures.

share|improve this answer
add comment

This contains an answer: roughly speaking, the entropy of the observation $x=(x_1,\ldots,x_q)$ based on $n$ rolls, with respect to the uniform distribution is $$ h(x)=-\sum_{k=1}^q(x_k/n)\log(qx_k/n), $$ and the associated p-value is $$ \exp(-nh(x)). $$ If $x$ is drawn from the uniform distribution, $h(x)$ is of order $1/n$ and $nh(x)$ converges to the $\chi^2$-distribution with $q-1$ degrees of freedom, otherwise $h(x)$ is of order $1$ and measures how far apart the empirical distribution of $x$ and the uniform distribution are.

share|improve this answer
add comment

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.