¿Cuál es el valor esperado de la suma del subvector de suma máxima si los elementos de la matriz son números reales aleatorios elegidos uniformemente entre [-1,1]?

Answer 1

No he encontrado una solución de forma cerrada para este problema. Sin embargo, parece que puede obtener la respuesta con bastante precisión simplemente con una simulación empírica. También actualicé mi respuesta para incluir algunas ideas nuevas basadas en una pista de Wang Xinjie (ver comentario).

Casos simples Sea [math] M (n) [/ math] la suma máxima obtenida para una matriz aleatoria de longitud [math] n [/ math]. Para valores pequeños de [matemáticas] n [/ matemáticas], no es demasiado difícil calcular [matemáticas] E [M (n)] [/ matemáticas] exactamente. Por ejemplo, si [matemática] n = 1 [/ matemática] observe que [matemática] E [M (n) | x_1 <0] = 0 [/ matemática] y [matemática] E [M (n) | x_1 \ ge 0] = \ frac {1} {2} [/ matemática]. (Tenga en cuenta que el libro de Bentley menciona explícitamente que las submatrices de longitud cero están permitidas, por lo que [matemática] M (n) \ ge 0 [/ matemática] siempre.) Cada posibilidad ocurre con [matemática] \ frac {1} {2} [/ matemática] probabilidad entonces [matemática] E [M (n)] = \ frac {1} {4} [/ matemática]. Para [matemática] n = 2 [/ matemática], puede usar nuevamente el razonamiento caso por caso para resolver que [matemática] E [M (n)] = \ frac {1} {2} [/ matemática]. Después de este punto, sin embargo, se vuelve considerablemente más desordenado.

Simulaciones empíricas. Valores pequeños anteriores de [math] n [/ math], puede usar simulaciones empíricas para mostrar que [math] E [M (n)] = O (\ sqrt {n}) [/ math]. Específicamente obtuve [matemáticas] E [M (n)] \ aproximadamente 0.72262 \ sqrt {n} -0.56488 [/ matemáticas] al realizar una regresión lineal de estimaciones simuladas de [matemáticas] E [M (n)] [/ matemáticas] contra [math] \ sqrt {n} [/ math] (para [math] n \ in [0..1000] [/ math], 10000 muestras cada una). El ajuste es extremadamente bueno asintóticamente, pero tiende a subestimarse para pequeñas [matemáticas] n [/ matemáticas].

Conexión de caminata aleatoria (basada en una pista). Considere una caminata simétrica aleatoria de longitud [matemática] n [/ matemática] que comienza en 0, en la cual cada paso implica tomar un desplazamiento que se distribuye uniformemente en [matemática] [- 1,1] [/ matemática]. Deje que [math] S_i [/ ​​math] denote la ubicación después de [math] i [/ math] pasos en la caminata aleatoria. Es fácil ver que la distribución de [math] S_i [/ ​​math] es idéntica a la distribución de la suma de los primeros elementos [math] i [/ math] de la matriz en el problema. Continuando por estas líneas, se puede mostrar que [matemáticas] E [M (n)] = E [\ max_ {i, j: i \ le j} (S_j-S_i)] [/ matemáticas], la última de las cuales es la expectativa del aumento máximo en la caminata aleatoria (o dado que la caminata aleatoria es simétrica, es equivalente a la expectativa de la reducción máxima (ver http://en.wikipedia.org/wiki/Dra… para más información) de la caminata aleatoria )

Para [math] n [/ math] suficientemente grande (con algunos movimientos de mano admitidos), la caminata aleatoria descrita anteriormente se puede aproximar bien como un proceso de movimiento browniano, lo que nos permite utilizar resultados conocidos (http: //alumnus.caltech. edu / ~ amir …) para argumentar que [matemáticas] E [M (n)] = O (\ sqrt {n}) [/ matemáticas].

Answer 2

Aquí hay respuestas exactas para algunos casos pequeños, cortesía de Mathematica. Lamentablemente, el cálculo se vuelve muy lento después de estos.

 En [1]: = f [n_]: = Expectativa [Max [0, Max [Tabla [Suma [x [k], {k, i, j}], {i, n}, {j, i, n }]]], Distribuido [Tabla [x [i], {i, n}], Distribución uniforme [Tabla [{- 1, 1}, {n}]]]] En [2]: = Tabla [f [n ], {n, 5}] Fuera [2] = {1/4, 1/2, 23/32, 291/320, 4141/3840}