4 votos

Maximiza la suma sin dos variables consecutivas

Variables aleatorias $x_1,x_2,\dots,x_{100}$ son dibujados de forma independiente de la distribución uniforme sobre $(0,1)$. Después de conocer los valores, nos permite seleccionar un subconjunto de ellos con tal de que no hay dos consecutivos variables escogidas. Lo que queremos es maximizar la suma de las variables seleccionadas. En la espera, qué podemos hacer?

Una forma de elegir es ignorar los valores y siempre elige $x_1,x_3,x_5,\dots,x_{99}$. Dado que cada variable tiene una expectativa de $1/2$, esto le da una espera suma de $50$. Pero debería ser posible hacerlo mejor si consideramos que el se dio cuenta de valores.

0voto

Mark Fischler Puntos 11615

Bien, la respuesta $$ \Bbb{E}[\max(x_1+x_3+\ldots x_99, x_2+x_4+\ldots x_{100})] $$ es no la respuesta correcta para la expectativa de valor, es un poco baja.

Para ver esto, considere el caso de sólo $4$ uniforme aleatorios en lugar de $100$.

Aquí, la expectativa en la propuesta de respuesta es $ \Bbb{E}[ \max(x_1+x_3, x_2+x_4)] $ y usted puede trabajar en su cabeza que esto es $\frac{37}{30}$. La expectativa es real

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

Incluso es posible que, para valores más altos de $2N$, que es la máxima suma usa menos de $N$ de la varia!

El cálculo exacto para $N=100$ es intratable y no el aspecto más interesante de la cuestión. La pregunta real es:

Muestran que la expectativa de la máxima de no-contiguos-par-que contiene la suma entre $2N$ uniforme variables en $(0,1)$ es de la forma

$$M(2N) = N + \frac{\sqrt{N}}{12\pi} + \Theta\left( N^s \right) $$ con algunos $s < \frac12$, y como un poco toughr un problema, encontrar $s$.

Tenga en cuenta que los dos primeros términos de la expansión de dar (a menos que haya cometido un error) el primer remolque de términos de la forma asintótica de que la propuesta de la respuesta habría implícita).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X