Skip to main content
1 of 3
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

If I understand the problem correctly then $\mathbb{E}(X_i)=\frac{m}{n}.$ if I don't, then the rest of this answer may not be very useful.

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$ by one each but would give the same expectation for the maximum of the $S_i.$ That way of setting up the problem might be clearer.

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 double all the entries we would get a composition of $2m$ with twice the expected maximum. To get an arbitrary composition of $ 2m$ we might move some of the parts up or down by 1 but that would not have a big effect on the expected maximum. Beyond that I'll just say that the calculations below support this supposition.

I think that it might be possible to find the distribution of the maximum or an explicit formula for the expected maximum (perhaps just in the case that $m$ is a multiple of $n$ and perhaps just the growth rate.) It is not hard to have a computer program perform the calculations (I did $n \le 4$ and $m \le 70$ with Maple.) The values which arise (according to my calculations) are easy to analyze.

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-1)/2}{2}=\frac{m}{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)}m.$ 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$ there is some other expression which I did not totally work out.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104