Probability of observing outcome with low individual probability

Question

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}]

Answer 1

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

Answer 2

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