El problema de Robbins

En teoría de la probabilidad , el problema de detención óptima de Robbins ^[1] , que lleva el nombre de Herbert Robbins , a veces se denomina problema del cuarto secretario o problema de minimizar el rango esperado con información completa. ^[2]

Sean X ₁ , ... , X _n variables aleatorias independientes, distribuidas idénticamente y uniformes en [0, 1]. Observamos las X _k secuencialmente y debemos detenernos exactamente en una de ellas. No se permite recordar observaciones anteriores. ¿Qué regla de detención minimiza el rango esperado de la observación seleccionada y cuál es su valor correspondiente?

Se desconoce la solución general a este problema de clasificación esperada de información completa. La principal dificultad es que el problema depende totalmente de la historia, es decir, la regla óptima depende en cada etapa de todos los valores precedentes, y no sólo de estadísticas suficientes más simples de estos. Sólo se conocen límites para el valor límite v cuando n tiende al infinito, es decir, 1,908 <  v  < 2,329. Se sabe que hay cierto margen para mejorar el límite inferior mediante cálculos adicionales para una versión truncada del problema. Todavía no se sabe cómo mejorar el límite superior que surge de la subclase de reglas de umbral sin memoria. ^{[3] [4] [5]}

Se propuso la versión de tiempo continuo del problema donde las observaciones siguen un proceso de llegada de Poisson de tasa homogénea 1. Bajo algunos supuestos, la función de valor correspondiente es acotada y de Lipschitz continua, y se deriva la ecuación diferencial para esta función de valor. ^[6] El valor límite de presenta la solución del problema de Robbins. Se muestra que para grandes , . Esta estimación coincide con los límites mencionados anteriormente. ${\displaystyle w(t)}$ ${\displaystyle w(t)}$ ${\displaystyle t}$ ${\displaystyle 1\leq w(t)\leq 2.33183}$

Krieger y Samuel-Cahn propusieron una regla subóptima simple, que funciona casi tan bien como la regla óptima. ^[7] La ​​regla se detiene con el más pequeño tal que para una constante c dada, donde es el rango relativo de la iésima observación y n es el número total de elementos. Esta regla ha añadido flexibilidad. Se puede utilizar una versión reducida del mismo para seleccionar un elemento con una probabilidad determinada . La regla se puede utilizar para seleccionar dos o más elementos. También se trata el problema de seleccionar un porcentaje fijo de n. ${\displaystyle i}$ ${\displaystyle R_{i}<ic/(n+i)}$ ${\displaystyle R_{i}}$ ${\displaystyle P}$ ${\displaystyle P<1}$ ${\displaystyle \alpha }$ ${\displaystyle 0<\alpha <1}$

Juego Chow-Robbins

Otro problema de parada óptimo que lleva el nombre de Robbins es el juego Chow-Robbins: ^{[8] [9]}

Dada una secuencia infinita de variables aleatorias IID con distribución , ¿cómo decidir cuándo detenerse para maximizar el promedio de la muestra ? ¿Dónde está el tiempo de parada? La probabilidad de detenerse finalmente debe ser 1 (es decir, no se le permite seguir tomando muestras y no detenerse nunca). ${\displaystyle X_{1},X_{2},...}$ ${\displaystyle F}$ ${\displaystyle {\frac {1}{n}}(X_{1}+\cdots X_{n})}$ ${\displaystyle n}$

Para cualquier distribución con segundo momento finito, existe una estrategia óptima, definida por una secuencia de números . La estrategia es seguir tomando muestras hasta . ^{[10] [11]} ${\displaystyle F}$ ${\displaystyle \beta _{1},\beta _{2},...}$ ${\displaystyle {\frac {1}{n}}(X_{1}+\cdots X_{n})\geq \beta _{n}}$

Estrategia óptima para grandesnorte

Si tiene un segundo momento finito, luego de restar la media y dividir por la desviación estándar, obtenemos una distribución con media cero y varianza uno. En consecuencia basta estudiar el caso de con media cero y varianza uno. ${\displaystyle F}$ ${\displaystyle F}$

Con esto, ¿dónde está la solución a la ecuación ^{[nota 1]} que se puede probar resolviendo el mismo problema en tiempo continuo, con un proceso de Wiener ? En el límite de , el problema de tiempo discreto se vuelve igual que el problema de tiempo continuo. ${\displaystyle \lim _{n}\beta _{n}/{\sqrt {n}}\approx \alpha =0.8399236757}$ ${\displaystyle \alpha }$ $${\displaystyle \alpha =\left(1-\alpha ^{2}\right)\int _{0}^{\infty }e^{\lambda \alpha -\lambda ^{2}/2}d\lambda }$$ ${\displaystyle n\to \infty }$

Esto fue demostrado de forma independiente ^[12] por. ^{[13] [14] [15]}

Cuando el juego es un juego justo de lanzamiento de moneda, con cara +1 y cruz -1, entonces hay un resultado más nítido ^[9] donde está la función zeta de Riemann . $${\displaystyle \beta _{n}=\alpha {\sqrt {n}}-1/2+{\frac {(-2\zeta (-1/2)){\sqrt {\alpha }}}{\sqrt {\pi }}}n^{-1/4}+O\left(n^{-7/24}\right)}$$ ${\displaystyle \zeta }$

Estrategia óptima para pequeñasnorte

Cuando n es pequeño, el límite asintótico no se aplica y encontrar el valor de es mucho más difícil. Incluso el caso más simple, en el que los lanzamientos de moneda son justos, no está completamente resuelto. ${\displaystyle \beta _{n}}$ ${\displaystyle X_{1},X_{2},...}$

Para el lanzamiento justo de una moneda, una estrategia es una decisión binaria: después de los lanzamientos, con k caras y (nk) cruces, ¿se debe continuar o detenerse? Dado que el paseo aleatorio 1D es recurrente y comienza en cualquier , la probabilidad de tener eventualmente más caras que cruces es 1. Por lo tanto, si , siempre se debe continuar. Sin embargo, si , es complicado decidir si detenerse o continuar. ^[dieciséis] ${\displaystyle n}$ ${\displaystyle k,(n-k)}$ ${\displaystyle k\leq n-k}$ ${\displaystyle k>n-k}$

^[17] encontró una solución exacta para todos . ${\displaystyle n\leq 489241}$

Elton ^[9] encontró soluciones exactas para todos y encontró una regla de decisión casi siempre óptima: detenerse tan pronto como ${\displaystyle n\leq 9.06\times 10^{7}}$ ${\displaystyle k-(n-k)\geq \Delta k_{n}}$ $${\displaystyle \Delta k_{n}=\left\lceil {\alpha {\sqrt {n}}\,\,-1/2\,\,+\,\,{\frac {\left({-2\zeta (-1/2)}\right){\sqrt {\alpha }}}{\sqrt {\pi }}}{n^{-1/4}}}\right\rceil }$$

Importancia

Una de las motivaciones para estudiar el problema de Robbins es que con su solución se resolverían todos los problemas clásicos (cuatro) de secretaria . Pero la razón principal es comprender cómo afrontar la dependencia histórica total en un problema (engañosamente fácil de parecer). En la Conferencia Internacional del Libro de Ester en Israel (2006), el problema de Robbins fue nombrado uno de los cuatro problemas más importantes en el campo de la detención óptima y el análisis secuencial .

Historia

Herbert Robbins presentó el problema descrito anteriormente en la Conferencia Internacional sobre Búsqueda y Selección en Tiempo Real ^{[nota 2]} en Amherst , 1990. Concluyó su discurso con las palabras Me gustaría ver este problema resuelto antes de morir . Desde entonces, los científicos que trabajan en el campo de la parada óptima han llamado a este problema el problema de Robbins . El propio Robbins murió en 2001.

Referencias

1. Chow, YS; Moriguti, S.; Robbins, Herbert Ellis ; Samuels, Stephen M. (1964). "Selección óptima basada en el rango relativo". Revista Israelí de Matemáticas . 2 (2): 81–90. doi : 10.1007/bf02759948 .
2. Bruss, F. Thomas (2005). "¿Qué se sabe sobre el problema de Robbins?". Revista de probabilidad aplicada . 42 (1): 108-120. doi : 10.1239/jap/1110381374 . JSTOR  30040773.
3. Bruss, F. Thomas ; Ferguson, S. Thomas (1993). "Minimizar el rango esperado con información completa". Revista de probabilidad aplicada . 30 (3): 616–626. doi : 10.1007/bf02759948 . ISSN  0021-9002. JSTOR  3214770.
4. Bruss, F. Thomas; Ferguson, S. Thomas (1996). "El problema de los semiprofetas y Robbins de minimizar el rango esperado". Apuntes de conferencias sobre estadística (LNS) . Conferencia de Atenas sobre probabilidad aplicada y análisis de series temporales. vol. 114. Nueva York, Nueva York: Springer Nueva York. págs. 1-17. doi : 10.1007/978-1-4612-0749-8_1 . ISBN 978-0-387-94788-4.
5. Asaf, David; Samuel-Cahn, Ester (1996). "El problema de la secretaria: minimizar el rango esperado con variables aleatorias iid". Avances en probabilidad aplicada . 28 (3): 828–852. doi : 10.2307/1428183 . ISSN  0001-8678. JSTOR  1428183.
6. Bruss, F. Thomas ; Cisne, Yvik C. (2009). "¿Qué se sabe sobre el problema de Robbins?". Revista de probabilidad aplicada . 46 (1): 1–18. doi : 10.1239/jap/1238592113 . JSTOR  30040773.
7. Krieger, Abba M.; Samuel-Cahn, Ester (2009). "El problema del secretario de minimizar el rango esperado: un enfoque subóptimo simple con generalización". Avances en probabilidad aplicada . 41 (4): 1041-1058. doi : 10.1239/aap/1261669585 . JSTOR  27793918.
8. Chow, YS; Robbins, Herbert (septiembre de 1965). "Sobre las reglas de parada óptimas para $ S_ {n}/n $". Revista de Matemáticas de Illinois . 9 (3): 444–454. doi : 10.1215/ijm/1256068146 . ISSN  0019-2082.
9. Elton, John H. (6 de junio de 2023). "Solución exacta del juego de Chow-Robbins para casi todos los n, utilizando el Triángulo catalán". arXiv : 2205.13499 [matemáticas].{{cite arXiv}}: CS1 maint: date and year (link)
10. Dvoretzky, Aryeh. "Existencia y propiedades de determinadas reglas de parada óptimas". Proc. Quinto Simposio de Berkeley. Matemáticas. Estadístico. Problema . vol. 1. 1967.
11. Teicher, H.; Wolfowitz, J. (1 de diciembre de 1966). "Existencia de reglas de parada óptimas para recompensas lineales y cuadráticas". Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete . 5 (4): 361–368. doi :10.1007/BF00535366. ISSN  1432-2064.
12. Simons, Gordon; Yao, Yi-Ching (1 de agosto de 1989). "Detener de manera óptima la media muestral de un proceso Wiener con una deriva desconocida". Procesos estocásticos y sus aplicaciones . 32 (2): 347–354. doi :10.1016/0304-4149(89)90084-7. ISSN  0304-4149.
13. Shepp, LA (junio de 1969). "Soluciones explícitas a algunos problemas de parada óptima". Los anales de la estadística matemática . 40 (3): 993–1010. doi : 10.1214/aoms/1177697604 . ISSN  0003-4851.
14. Taylor, Howard M. (1968). "Parada óptima en un proceso de Markov". Los anales de la estadística matemática . 39 (4): 1333-1344. doi : 10.1214/aoms/1177698259 . ISSN  0003-4851. JSTOR  2239702.
15. Caminante, Leroy H. (1969). "Con respecto a las reglas de detención del movimiento browniano y los paseos aleatorios". Boletín de la Sociedad Matemática Estadounidense . 75 (1): 46–50. doi : 10.1090/S0002-9904-1969-12140-3 . ISSN  0002-9904.
16. Häggström, Olle ; Wästlund, Johan (2013). "Análisis informático riguroso del juego Chow-Robbins". El Mensual Matemático Estadounidense . 120 (10): 893. doi : 10.4169/amer.math.monthly.120.10.893.
17. Christensen, Sören; Fischer, Simon (junio de 2022). "Sobre el problema Sn/n". Revista de probabilidad aplicada . 59 (2): 571–583. doi :10.1017/jpr.2021.73. ISSN  0021-9002.

Notas a pie de página

1. importar  numpy  como  np desde  scipy.integrate  importar  quad desde  scipy.optimize  importar  raízdef  f ( lambda_ ,  alfa ):  devuelve  np . exp ( lambda_  *  alfa  -  lambda_ ** 2/2  )​ ​def  ecuación ( alfa ):  integral ,  error  =  quad ( f ,  0 ,  np . inf ,  args = ( alfa ))  devuelve  integral  *  ( 1  -  alfa ** 2 )  -  alfasolución  =  raíz ( ecuación ,  0.83992 ,  tol = 1e-15 )# Imprime la solución si es  solución . éxito :  print ( f "Resuelto α = { solución . x [ 0 ] } con un residual de { solución . fun [ 0 ] } " ) else :  print ( "La solución no convergió" )

2. Las Conferencias Conjuntas de Investigación de Verano en Ciencias Matemáticas se llevaron a cabo en la Universidad de Massachusetts del 7 de junio al 4 de julio de 1990. Fueron patrocinadas por la AMS, SIAM y el Instituto de Estadística Matemática (IMS). Los temas de 1990 fueron: Modelos de probabilidad y análisis estadístico para clasificar datos, Dispersión inversa en la línea, Teoría de la deformación de álgebras y cuantificación con aplicaciones a la física, Estrategias para la búsqueda y selección secuencial en tiempo real, Problemas de Schottky y Lógica, campos y conjuntos subanalíticos.