MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following question

$\quad$Problem about expectation of maximum partial sum:

can be reduced to determing
$$f(m,n) = \sum \max_{1\le i \le n}(x_1 + ... + x_i - \frac{m}{n} i)$$ where the sum is taken over all tuples $(x_1,...,x_n)$ of positive integers such that $x_1 + ... + x_n=m$.

Perhaps it's possible to evaluate this expression.

share|cite|improve this question
It would help others to follow the format. What is the actual question? Are you asking for a closed form, upper or lower bounds, or a quick algorithm? Please edit to specify. Gerhard "Ask Me About System Design" Paseman, 2012.01.12 – Gerhard Paseman Jan 12 '12 at 20:36
Tanks for your hint. Closed form would be perfect, an upper bound would also be very interesting. A (coarse) lower bound can be derived by counting those $x$ such that $x_1>m/n$. If I succeed, I'll post the lower bound later on and in this turn I'll specify the question in a better way. – Ralph Jan 12 '12 at 20:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.