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

Given a number $m$, a random composition (strong) of this number into $n$ positive parts so that we can get $n$ random variable $X_1, X_2,\dots, X_n$ with $$X_1+X_2+\cdots+X_n=m$$

Note that all compositions of $m$ have the same probability.

Let $Y_i = X_i - \mathbb{E}(X_i)$, $S_i = Y_1 + \cdots + Y_i$

I want to calculate $\mathbb{E}(\max_{1 \le i \le n} S_i)$.

share|improve this question
And why do you want to compute this? Is this homework? –  Igor Rivin Jan 11 '12 at 13:13
@IgorRivin It is not homework. I want to analyze a algorithm I proposed. And it can be converted to the above problem. –  Fan Zhang Jan 11 '12 at 13:59
@Fan Zhang Are you assuming that the parts are written in increasing order? If not then all of the $E(X_i)$'s are the same, just by considering all possible permutations. –  Alan Haynes Jan 11 '12 at 14:20
@AH I am not assuming that the parts are written in increasing order. It is number composition, so order is significant here. –  Fan Zhang Jan 11 '12 at 15:17
@Fan: OK, but again what range for $n$ and $m$? are you interested in asymptotics when they tend to infinity? –  Ori Gurel-Gurevich Jan 13 '12 at 18:29

3 Answers 3

up vote 11 down vote accepted

[Edited to add Sage plots of the asymptotic distributions for $n=2,3,4,5,6,7$ and $n=10,20,30,40$]

There are $m-1 \choose n-1$ "compositions" of $m$ into $n$ positive parts $X_i$, because they correspond bijectively with choices of $n-1$ partial sums out of $\lbrace 1, 2, \ldots, m-1\rbrace$. By symmetry, each $X_i$ has expectation $m/n$. For large $n$ and much larger $m$, the sequence of normalized partial sums $$ S_i = \sum_{h=1}^i Y_h = \sum_{h=1}^i (X_h - \mathbb{E}(X_h)) = \Bigl(\sum_{h=1}^i X_h \Bigr) - \frac{i}{n} m $$ looks like a scaled "Brownian bridge", i.e. ${\rm BB}(t) = B(t) - B(1)t$ where $B(t)$ is Brownian motion on $[0,1]$. The distribution of $\max_t {\rm BB}(t)$ is known thanks to a reflection trick, and thus so is its expectation. If I did this right, for $\sigma > 0$ the probability that $S_\max := \max_i S(i)$ exceeds $\sigma$ approaches $\exp(-2n(\sigma/m))^2$, which would make $$ \mathbb{E}(S_\max) \sim \int_0^\infty e^{-2n(\sigma/m)^2} d\sigma = \sqrt{\frac\pi{8n}} \cdot m. $$ Since the question at hand asks only for the expectation of $S_\max$, not subtler features of its distribution, the estimate should be reasonably good for moderately large $n$ and $m$. As Aaron Meyerowitz noted, for fixed $n$ we have $$ \mathbb{E}(S_\max) = c_n m + O(1) $$ as $m \rightarrow \infty$; computation of the constants $c_n$ for $n \leq 40$ suggests that $n^{1/2} c_n \rightarrow \sqrt{\pi/8}$ but not very quickly: $n^{1/2} (\sqrt{\pi/8} - n^{1/2} c_n)$ seems to be converging to about $0.66$, and while $\sqrt{\pi/8} = 0.626657\ldots$, the computed $n^{1/2} c_n$ first exceeds $0.5$ only at $n = 27$. The formulas below may give a start towards proving this behavior.

Getting good estimates for finite values of $n$ seems unwieldy because computing the probability that $\max_i S(i) \leq \sigma$ requires counting "compositions" that satisfy $X_1 + \ldots + X_i \leq (i/n) m + \sigma$ for each $\sigma$, which gives rise to an intimidating inclusion-exclusion. Fortunately the answers to this mathoverflow query, which appeared just yesterday, give for any increasing integer sequence $0 < a_1 < a_2 < \ldots < a_N$ a nice determinant formula for the number of $N$-tuples $(x_1,\ldots,x_N)$ of integer sequences satisfying $0 < x_1 < \ldots < x_N$ and $x_i \leq a_i$ for each $i \leq N$. In our setting, we compute the number of "compositions" with $\max_i S(i) \leq \sigma$ by taking $N = n-1$, $x_i = \sum_{h=1}^i X_h$, and each $a_i = \min (m-1, \lfloor (i/n) m + \sigma \rfloor)$. The determinant has order $N$, with $(i,j)$ entry equal $a_i + j - i \choose j - i + 1$ [which is $1$ on the first subdiagonal $i = j+1$, and $0$ on the triangle $i > j+1$ under this subdiagonal]. This makes it feasible to compute exactly the distribution of $S_\max$ for moderately large $n$ and any $m$, and also the asymptotic distribution as $m \rightarrow \infty$.

For given $n$, the asymptotic distribution of $S_\max / m$ is piecewise polynomial, but takes a while to look like the limiting form proportional to $\sigma \exp(-2n(\sigma/m)^2) d\sigma$; notably it is discontinuous at $\sigma = 1/n$ with a substantial jump downwards. Here are Sage plots showing these distributions in red/orange/green/blue/purple/black for $n=2$ through $n=7$:

(The total area is $(n-1)/n$, not $1$, because $1/n$ of the measure is concentrated at $\sigma = 0$). Likewise for $n=10,20,30,40$, plotting only $0 < \sigma < 0.6$ because the density is too small to be seen for $\sigma \geq 0.6$:

(after much more computing, most of it for the $40 \times 40$ determinants; at $n=40$ the graph finally crests after the downwards plunge at $1/n$).

Finally, a tabulation of the values of $c_n$ for $n = 1, 2, \ldots, 40$. For each $n$ I give $n^n c_n$, which is an integer except for $n=2$ when $c_2 = 1/8$. This value, as well as each of $c_3 = 4/3^3$, $c_4 = 39/4^4$, and $c_5 = 472 / 5^5$, agrees with A.Meyerowitz's calculations.

[1, 0]
[2, 1/2]
[3, 4]
[4, 39]
[5, 472]
[6, 6900]
[7, 118716]
[8, 2354072]
[9, 52911216]
[10, 1330107840]
[11, 36991592500]
[12, 1127914077312]
[13, 37420777559496]
[14, 1342183358856704]
[15, 51756244887797100]
[16, 2135359495833676800]
[17, 93864296121282210784]
[18, 4379542774345464496128]
[19, 216178594161376244063076]
[20, 11255374377126199463936000]
[21, 616463053079082019376239800]
[22, 35432440194603405959506034688]
[23, 2132478311049609494982190450204]
[24, 134116927093400952330702474706944]
[25, 8798258310785305861553627142930000]
[26, 601017143689398400881632598032384000]
[27, 42684847106441394367226307718311565716]
[28, 3147222817221577402622824207375266742272]
[29, 240582153893938356991908848927905622445736]
[30, 19043079550271688145972837306025115648000000]
[31, 1558981284930199828739239320361571788041021900]
[32, 131855889346498739861328689280063889600321421312]
[33, 11509801310013312943392059948175963018705195688896]
[34, 1035923337749909421439098617643978496876513679376384]
[35, 96047358406199526246797502389944873251740366086562500]
[36, 9165799239775410749318809193562746250766254788837376000]
[37, 899564153243436548625817312320806272340082850282897445784]
[38, 90727638906463992065814103522957255273344987915765288009728]
[39, 9396779387234810402125876063643842517670905874506382252419196]
[40, 998740925886849063603687252012149942602287367747692134400000000]
share|improve this answer
@noam-d-elkies Would you please give more detail about how to calculate the $C_n n^n$? –  Fan Zhang Feb 6 '12 at 9:53

If I understand the problem correctly then $\mathbb{E}(X_i)=\frac{m}{n}$ So that the $Y_i$ are values from $0-\frac mn,1-\frac{m}{n},\dots,m-\frac mn$ which add to $0$.

If we would instead compose $m-n$ as an ordered sum of $n$ non-negative integers this would have the effect of lowering the $X_i$ and expectation by one each but would give the same $Y_i$ and expectation for the maximum of the $S_i.$ That way of setting up the problem might lead to neater expressions.

It seems to me that the expected maximum would asymptotically be $$c_nm+e_r+O(1/m)$$ where $e_r$ depends on the congruence class of $m$ mod $n.$ The fuzzy reasoning is that if we were to take a composition of $m$ and triple all the entries we would get a composition of $m'=3m$ with thrice the expected maximum. To get an arbitrary composition of $ 3m$ we might move some of the parts up or down by 1, but that would not have a big effect on the ratio of the expected maximum to $m'$. Beyond that I'll just say that the calculations below support this supposition with $$c_2=\frac{1}{8},c_3=\frac{4}{27},c_4=\frac{39}{256},c_5=\frac{472}{3125}.$$

More specifically, calculations strongly suggest for each $0 \le r \le n-1$ there is a polynomial $p_r(q)$ of degree $n$ such that for $m=qn+r$ $$\mathbb{E}(S_{\max})=\frac{p_r(q)}{(m-1)(m-2)\dots(m-n)}.$$ In all cases the leading coefficient is the same, namely $n^{n}c_n.$ Assuming that that is the case, one can find the coefficients of $p_r(q)$ and hence $c_n$ by computing $\mathbb{E}(S_{\max})$ for $m=r,n+r,2n+r,\dots,n^2+r.$ And going a bit further provides a check. Eventually this would be too hard a calculation, but the obvious naive strategy works well for a while (I did $n \le 4$ and $m \le 70$ with Maple.)

later N. Elkies' great answer explains (and establishes) these facts and much more, but I leave this amended naive approach for what it is worth.

For $n=2$ the expected value of the maximum is $\frac{m-1}{8}$ or $\frac{m-1}{8}-\frac{1}{8(m-1)}$ according as $m$ is odd or even. In the odd case, for $1 \le X_1 \le \frac{m-1}{2}$ the maximum is $S_2=0.$ And for $\frac{m+1}{2} \le X_1 \le m-1$ the maximum is $S_1=X_1-\frac{m}{2}$ with expected value $\frac{1/2+(m-2)/2}{2}=\frac{m-1}{4}.$ When $m$ is even there is also the composition into 2 equal parts with $S_1=S_2=0$ and it slightly lowers the answer. After some arithmetic the expected maximum turns out to be as stated.

For $n=3$ the expected maximum appears to be about $\frac{4}{27}m$ and exactly $\frac{2(q-1)^2(2q-3)}{(m-1)(m-2)},\frac{2(q-1)q(2q-3)}{(m-1)(m-2)}$ or $\frac{2q^2(2q-3)}{(m-1)(m-2)}$ according as $m=3q-1,m=3q$ or $m=3q+1.$ The sequence A200067 from the OEIS may be related.

In the case that $n=4$ the expected maximum appears to be $\frac{39}{256}m+O(1)$ In the case $m=4q$ the expected maximum appears to be exactly $\frac{3(13q^2-13q+3)q(q-1)}{(m-1)(m-2)(m-3)}.$ When $m=4q-1$ or $m=4q+1$ the term q(q-1) is replaced by $(q-1)^2$ or $q^2$ respectively. This is similar to the $n=3$ case above. For $m=4q+2$ it comes out to be $\frac{3q^2(13q^2+2)}{(m-1)(m-2)(m-3)}$

For $n=5$ similar considerations give an expected maximum of $\frac{472}{3125}m+O(1)$

share|improve this answer
Could you please post your maple program to calculate the Cn? –  Fan Zhang Jan 22 '12 at 5:03
It is built in. >with(combinat): then >composition(5,3); will return {[1, 1, 3], [1, 2, 2], [1, 3, 1], [2, 1, 2], [2, 2, 1], [3, 1, 1]}. You can see how it is programmed by restarting putting in >with(combinat): >interface(verbosepreoc=3): then >print(combination): (Restart to avoid seeing extensive remembered results!) It is pretty short. –  Aaron Meyerowitz Jan 23 '12 at 5:28

I can't comment , but based on Noam D. Elkies's numbers and OEIS A000435 it looks as if

$$c_n = \frac{(n-1)!}{2 n^n} \sum_{k=0}^{n-2} \frac{n^k}{k!}.$$

share|improve this answer
@Henry Do you understand Elkie's approach? –  Fan Zhang Apr 18 '12 at 1:45

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.