Maximize sum with no two consecutive variables

Random variables $x_1,x_2,\dots,x_{100}$ are drawn independently from the uniform distribution over $(0,1)$. After knowing the values, we are allowed to choose a subset of them as long as no two consecutive variables are chosen. We want to maximize the sum of the chosen variables. In expectation, how high can we make it?

One way to choose is to ignore the values and always choose $x_1,x_3,x_5,\dots,x_{99}$. Since each variable has an expectation of $1/2$, this gives an expected sum of $50$. But it should be possible to do better if we consider the realized values.

• I think the EM algorithm should be useful here – Qwerty Jun 27 '16 at 18:31
• $$\max(x_1+x_3+\ldots+x_{99},x_2+x_4+\ldots+x_{100})$$ has a slightly larger expected value. It is enough to study the sums $$\sum_i x_{n_i}$$ where $x_{n_{i+1}}-x_{n_i}\in\{2,3\}$ (no other sums may attain the maximum). – Jack D'Aurizio Jun 27 '16 at 18:41
• Oh, wait: by symmetry, $(x_1,x_2,x_3,\ldots)$ has the same probability to occur as $(x_1,x_3,x_2,\ldots)$, so the above value, namely $$\mathbb{E}[\max(x_1+x_3+\ldots,x_2+x_4+\ldots)]$$ should be the exact answer. – Jack D'Aurizio Jun 27 '16 at 19:06

1 Answer

Well, the answer $$\Bbb{E}[\max(x_1+x_3+\ldots x_99, x_2+x_4+\ldots x_{100})]$$ is not the correct answer for the expectation value, it is a bit low.

To see this, consider the case of only $4$ uniform randoms instead of $100$.

Here, the expectation in the proposed answer is $\Bbb{E}[ \max(x_1+x_3, x_2+x_4)]$ and you can work out in your head that this is $\frac{37}{30}$. The actual expectation is

$\Bbb{E}[ \max(x_1+x_3, x_2+x_4, x_1+x_4)] = \frac{27}{20}$

It is even possible, for higher values of $2N$, that the maximal sum uses fewer than $N$ of the variates!

The exact calculation for $N=100$ is intractable and not the most interesting aspect of the question. The real question is:

Show that the expectation of the maximal no-contiguous-pair-containing sum among $2N$ uniform variates on $(0,1)$ is of the form

$$M(2N) = N + \frac{\sqrt{N}}{12\pi} + \Theta\left( N^s \right)$$ with some $s < \frac12$, and as a bit toughr a problem, find $s$.

Note that the first two terms of that expansion give (unless I have made a mistake) the first tow terms of the asymptotic form that the proposed answer would have implied).

• (When I said you can work it out in your head, I am assuming an arbitrarily large head. I actually did the three integrals it breaks up into on paper.) – Mark Fischler Jun 27 '16 at 21:33