Inequality constraints, probability distributions, and integer partitions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T04:14:15Z http://mathoverflow.net/feeds/question/30716 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30716/inequality-constraints-probability-distributions-and-integer-partitions Inequality constraints, probability distributions, and integer partitions Jonathan Fischoff 2010-07-06T03:44:00Z 2011-02-08T04:18:34Z <p>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,</p> <p>$a + b + c = 10$</p> <p>Additionally it has the constraint</p> <p>$a \geq b \geq c$</p> <p>The allowable triples will correspond to the integer partitions of 10 with width 3, such as:</p> <p>$(7, 2, 1)$</p> <p>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, </p> <p>$total \ ball \ count = balls \ per \ partition * partition \ count = 10 * 14 = 140$<br> $Prob(a) = 90 / 140 \approx .64$</p> <p>So I have a few questions. </p> <p>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? </p> <p>I am specifically interested in what the asymptotic behavior is as the number of balls and urns increase.</p> <p>Here is the code I am using in Haskell to calculate probabilities:<br> <a href="http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27026#a27026" rel="nofollow">http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27026#a27026</a></p> http://mathoverflow.net/questions/30716/inequality-constraints-probability-distributions-and-integer-partitions/30722#30722 Answer by Gerry Myerson for Inequality constraints, probability distributions, and integer partitions Gerry Myerson 2010-07-06T04:24:24Z 2011-02-08T04:18:34Z <p>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)?</p> <p>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. </p> <p>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&amp;\ge0\cr a_1+\dots+a_k&amp;=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. </p> <p>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). </p> <p>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. </p> <p>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&amp;\ge0\cr a+b+c&amp;=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). </p> <p>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. </p>