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

I am interested in the possibility of generating probability distributions using inequality constraints. For instance assume that we have three urns with total of a 10 balls. Thus,

$a + b + c = 10$

Additionally it has the constraint

$a \geq b \geq c$

The allowable triples will correspond to the integer partitions of 10 with width 3, such as:

$(7, 2, 1)$

If you were given a ball and wanted to know the probability that it can from urn $a$, it seems reasonable to sum all the balls in the urn $a$ for all 14 partitions, divided by the total number of balls. In this particular case we would have,

$total \ ball \ count = balls \ per \ partition * partition \ count = 10 * 14 = 140$
$Prob(a) = 90 / 140 \approx .64$

So I have a few questions.

First, am I even on the mark? Is this a valid approach for calculating the probability that the ball comes from urn $a$? If so has this approached been discussed in literature, hopefully in more generality?

I am specifically interested in what the asymptotic behavior is as the number of balls and urns increase.

Here is the code I am using in Haskell to calculate probabilities:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27026#a27026

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Whether this is a valid approach for calculating the probability will depend on what assumptions you are making on the probabilities of the various partitions. In particular, this calculation seems to require for its validity that all partitions be equally likely. Do you actually want (10,0,0) to be as likely as (4,3,3)?

Edit: Concerning asymptotic behavior, take the case where the number of balls equals the number of urns; call it $n$. One can ask for the proportion of balls in the first urn as a function of $n$, which is the same as asking for the average size of the biggest part in a partition of $n$ (which is also the same as asking for the average number of parts in a partition of $n$). This was studied by Kessler and Livingston, The expected number of parts in a partition of $n$, Monatshefte Math 81 (1976) 203-212. Let $P(n)$ be the total number of parts in all the partitions of $n$ (which is the same as the sum of the largest parts in all the partitions of $n$), and let $p(n)$ be the number of partitions of $n$. Then $${P(n)\over p(n)}=\sqrt{3n\over2\pi}(\log n+2\gamma-\log(\pi/2))+O(\log^3n)$$ where $\gamma$ is Euler's constant. More information at sequence A006128 at the Online Encyclopedia of Integer Sequences.

EDIT 15 July: Let $f_{j,k}(n)$ be the sum of the $j$-th biggest parts over all partitions of $n$ into at most $k$ parts, $$f_{j,k}(n)=\sum_{\eqalign{a_1\ge\dots\ge a_k&\ge0\cr a_1+\dots+a_k&=n\cr}}a_j,$$ and let $p_k(n)$ be the number of partitions of $n$ into at most $k$ parts. You are asking for the asymptotic behavior of $f_{j,k}(n)/np_k(n)$ as $k$ and $n$ increase, but it is not clear how you want them to increase (that is, what relation they should bear to each other as they increase), nor is it clear what you want $j$ to be doing while $k$ and $n$ are increasing. Perhaps you are only interested in the case $j=1$, which is the case in your example.

In any event, you need asymptotics for $p_k(n)$. From the generating function $$\sum_np_k(n)x^n={1\over(1-x)(1-x^2)\cdots(1-x^k)}$$ one can get, for fixed $k$, $p_k(n)=C_kn^{k-1}+O(n^{k-2})$, where $C_k=(k!(k-1)!)^{-1}$ (I hope someone checks my calculations here).

Now I can tell you something about $f_{k,k}(n)$ - this is the case when you're interested in the $\it last$ urn. Let's write $g_k(n)=f_{k,k}(n)$. It's not hard to prove that $g_k(n+k)-g_k(n)=p_k(n)$, from which it follows that $$\sum_ng_k(n)x^n={x^k\over(1-x)\cdots(1-x^{k-1})(1-x^k)^2}$$ and then you get, again for fixed $k$, $g_k(n)=D_kn^k+O(n^{k-1})$, where $D_k=k^{-1}(k!)^{-2}$. So, the probability that the ball is from the last urn approaches $k^{-2}$ as $n$ increases with $k$ fixed.

I didn't do so well with the first urn. Let's just take the case $k=3$. We want $$h_3(n)=f_{1,3}(n)=\sum_{\eqalign{a\ge b\ge c&\ge0\cr a+b+c&=n\cr}}a.$$ Starting with $n=1$, this produces the sequence $1,3,6,11,17,27,37,52,69,90,113,144\dots$. I didn't find this sequence in the Online Encyclopedia of Integer Sequences. I think, but can't prove, that the generating function is $$\sum_nh_3(n)x^n={x+3x^2+4x^3+3x^4\over(1-x)^2(1-x^3)^2}.$$ This gives $h_3(n)=(11/216)n^3+O(n^2)$. Together with $p_3(n)=(1/12)n^2+O(n)$, you get the probability of the ball coming from the first of the three urns converging to 11/18, as $n$ increases (and conditional on my unproved formula for the generating function).

EDIT 8 February 2011: There's a typo in the last display, it should be $$\sum_nh_3(n)x^n={x+3x^2+4x^3+3x^4\over(1-x^2)^2(1-x^3)^2}.$$ George Andrews wrote out a proof of this formula (and his method should apply more generally to $\sum_nf_{j,k}(n)x^n$). Let $a=r+s+t$, $b=s+t$, $c=t$, then the generating function is $\sum_{r,s,t}(r+s+t)x^{r+2s+3t}$, which can be split up into three pieces each of which is two geometric progressions times a sum of the shape $\sum_uuy^u$. That last sum is well-known, and after some algebra the conjectured formula pops out.

share|improve this answer
    
Yes, I am assuming each partition is equally likely. –  Jonathan Fischoff Jul 6 '10 at 4:25
    
Well, given that each partition is equally likely, and given that given a partition each ball is equally likely, then, yes, your formula computes what you want it to. I won't comment on your code since I'm not qualified to do so (and I'm not sure MO is the place for validating code). –  Gerry Myerson Jul 6 '10 at 5:35
    
The code works. Its just there if someone else wants to calculate it for any reason. I can take it down if it is not kosher. –  Jonathan Fischoff Jul 6 '10 at 5:54
    
Oh and thanks for walking through my logic :) –  Jonathan Fischoff Jul 6 '10 at 5:54
    
Woah. Just saw your edit. I did not expect that. –  Jonathan Fischoff Jul 7 '10 at 4:47
show 1 more 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.