3
$\begingroup$

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}]
$\endgroup$
8
  • $\begingroup$ (0,2),(1,1),(2,0) are tuples of counts, not sets of counts. Also, what language is your code in? $\endgroup$
    – user5810
    Oct 4, 2010 at 21:12
  • $\begingroup$ @Ricky: Looks like Mathematica. $\endgroup$
    – Charles
    Oct 4, 2010 at 21:20
  • $\begingroup$ Tuple (b1,b2,...) represents set {(1,b1),(2,b2),...} where pair (a,b) indicates that event a happened b times. Language is Mathematica $\endgroup$ Oct 4, 2010 at 21:38
  • $\begingroup$ How have you managed to obtain negative values for (p), which is a probability? Perhaps I am being dense. $\endgroup$
    – Tom Smith
    Oct 4, 2010 at 22:21
  • $\begingroup$ x axis was at y=0.2 which is confusing, fixed $\endgroup$ Oct 4, 2010 at 22:30

2 Answers 2

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Oct 5, 2010 at 20:15
  • $\begingroup$ 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$. $\endgroup$ Oct 5, 2010 at 21:07
  • $\begingroup$ 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$. $\endgroup$ Oct 5, 2010 at 21:11
  • $\begingroup$ $k=5$ adds two extra dimensions over $k=3$, shouldn't that multiply the integrand by $x^2$? $\endgroup$ Oct 5, 2010 at 21:48
  • $\begingroup$ That $x$ is not the same $x$ as you are plotting, which is closer to $q=c_1 \exp(-x^2/2)$. $\endgroup$ Oct 5, 2010 at 21:58
-1
$\begingroup$

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 :) .

$\endgroup$
2
  • $\begingroup$ It's concave for k=2 and convex for k=4. k=3 seems to be the only one where relationship is linear $\endgroup$ Oct 5, 2010 at 3:57
  • $\begingroup$ 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 $\endgroup$ Oct 5, 2010 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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