MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I throw k-sided dice n times and want to know the probability $p$ of observing a set of counts with individual probability higher than $x$.

Example, let k=2,n=2, fair dice. Possible sets of counts are (0,2),(1,1),(2,0). Individual probabilities of those counts are 1/4,1/2 and 1/4 respectively. Probability of getting outcome with individual probability above 0 is 1, above 1/4 is 1/2, above 1/2 is 0.

What is the relationship between $p$ and $x$? For k=3, line gives surprisingly good fit

This is a generalization of a related unanswered question

Douglas Zare suggests to think of counts as lattice sites of a random walk and use Central Limit theorem. This suggests that relationship is going to be quadratic for k=5, and indeed, parabola seems to give a decent upper bound in that case

n = 21;
types = Flatten[
   Permutations /@ (IntegerPartitions[n, {3}, Range[0, n]]/n), 1];
prob[p_, q_] := n! Times @@ MapThread[(#1)^(n #2)/(n #2)! &, {p, q}];
cum[p_, cutoff_] := 
  Total[Select[prob2[p, #] & /@ types, # >= cutoff &]];
p0 = RandomChoice[Select[types, FreeQ[#, 0] &]];
pvals = prob[p0, #] & /@ Union[types];
cvals = cum[p0, #] & /@ pvals;
data = Transpose[{pvals, cvals}];
Show[ListPlot[data, PlotRange -> All], 
 Plot @@ {Fit[data, {1, x}, x], {x, 0, Max[pvals]}, PlotStyle -> Red}]
share|cite|improve this question
(0,2),(1,1),(2,0) are tuples of counts, not sets of counts. Also, what language is your code in? – Ricky Demer Oct 4 '10 at 21:12
@Ricky: Looks like Mathematica. – Charles Oct 4 '10 at 21:20
Tuple (b1,b2,...) represents set {(1,b1),(2,b2),...} where pair (a,b) indicates that event a happened b times. Language is Mathematica – Yaroslav Bulatov Oct 4 '10 at 21:38
How have you managed to obtain negative values for (p), which is a probability? Perhaps I am being dense. – Tom Smith Oct 4 '10 at 22:21
x axis was at y=0.2 which is confusing, fixed – Yaroslav Bulatov Oct 4 '10 at 22:30

The following is not rigorous, but it explains the linearity for $k=3$, and I believe it can be made rigorous.

The counts are naturally arranged in a simplex with $k$ vertices by projecting orthogonally to the line $x_1 = x_2 = ... x_k$. You can view the counts as the endpoints of a random walk starting from the center of the simplex (the projection of the origin).

The Central Limit Theorem suggests that the multinomial coefficients at distance $d$ from the center of the simplex are about $c_1 \exp(-d^2/2)$. For $k=3$ and $d\lt n$, the number of vertices of distance at most $d$ is proportional to $d^2$, so there are about $c_2 d$ points of distance between $d$ and $d+1$. That suggests that the probability of encountering a probability at least $q=c_1\exp(-d^2/2)$ is about $\int_0^d c_2 x ~c_1 \exp(-x^2/2) dx$ which is linear in $q$.

In other dimensions ($k\ne3$), the result of the integral is not linear in $\exp(-d^2/2)$.

share|cite|improve this answer
Thanks, this seems to be a promising approach. For k=3, random walks seem to be over the hexagonal lattice. Any idea what this lattice is called for general k? – Yaroslav Bulatov Oct 5 '10 at 20:15
To clarify, for $k=5$, the indefinite integral is $(a_1 x^2+a_2)\exp(−x^2/2)+C$ which is not quadratic in $exp(−x^2/2)$, it looks like $(a_3\log(q)+a_4)q+C$. – Douglas Zare Oct 5 '10 at 21:07
The endpoints are in a copy of the $A_k$ lattice, the lattice points in $\mathbf Z^{k+1}$ whose coordinate sum is $n$ instead of $0$. – Douglas Zare Oct 5 '10 at 21:11
$k=5$ adds two extra dimensions over $k=3$, shouldn't that multiply the integrand by $x^2$? – Yaroslav Bulatov Oct 5 '10 at 21:48
That $x$ is not the same $x$ as you are plotting, which is closer to $q=c_1 \exp(-x^2/2)$. – Douglas Zare Oct 5 '10 at 21:58

If you're concerned with very small values of x it will be better to compute p = 1 - P(counts with individual probability at most x). This way you'll be summing far fewer terms and unless your x is very very small with k and n very very large then you need not worry about round off error.

I'm not sure about your coding, but your description deals with integer compositions here not integer partitions.

Let's just handle the binomial case k=2. Then .5 is the probability of each outcome.

if x is given then in your notation and I don't do my 1- trick: p = (sum from j=1 to j=n where I only count terms when j is such that (n choose j).5^n>x) of (n choose j).5^n. Note that .5^n is really best understood as .5^(n-j)*.5^j.

So it is easy to tell where you're going to hit the x axis, take the middle binomial coefficient*.5^n.

So this is really a step function. But yes linear is close but not exact relationship. If you look at successive left hand endpoints of the steps you should be able to convince yourself that if you interpolate linearly between those then it would not be linear. I've sort of convinced myself that the slopes between the left hand endpoints are basically 2*.5^n*(n choose j)/(n-1 choose j-1) for appropriate j, so the differences in the slopes between successive left endpoints differ by at most a factor of n/n-1 and often a much smaller factor which for n large basically goes to having the same slope between each adjacent pair of left endpoints.

I hope this helps. Since I'm new here I could use the reputation to put a bounty on one of my problems :) .

share|cite|improve this answer
It's concave for k=2 and convex for k=4. k=3 seems to be the only one where relationship is linear – Yaroslav Bulatov Oct 5 '10 at 3:57
By the way, this problem for k=2 is well studied, and all the formulas I see (check the link in desc.) are either loose approximations or are complicated. k=3 seems to have a tight+simple approximation over whole range of x. Nice formulas for large x and/or large k would be useful – Yaroslav Bulatov Oct 5 '10 at 4:08

Your Answer


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.