Algoritmo de probabilidades

Método de cálculo de estrategias óptimas para problemas de último éxito.

En teoría de la decisión , el algoritmo de probabilidades (o algoritmo de Bruss ) es un método matemático para calcular estrategias óptimas para una clase de problemas que pertenecen al dominio de los problemas de parada óptima . Su solución se deriva de la estrategia de probabilidades , y la importancia de la estrategia de probabilidades radica en su optimización, como se explica a continuación.

El algoritmo de probabilidades se aplica a una clase de problemas llamados problemas del último éxito . Formalmente, el objetivo en estos problemas es maximizar la probabilidad de identificar en una secuencia de eventos independientes observados secuencialmente el último evento que satisface un criterio específico (un "evento específico"). Esta identificación debe realizarse en el momento de la observación. No se permite revisar las observaciones anteriores. Por lo general, quien toma las decisiones define un evento específico como un evento que es de verdadero interés en vista de "detenerse" para realizar una acción bien definida. Estos problemas se encuentran en varias situaciones.

Ejemplos

Dos situaciones diferentes ejemplifican el interés por maximizar la probabilidad de detenerse en un último evento específico.

1. Supongamos que se anuncia la venta de un automóvil al mejor postor (la mejor "oferta"). Deje que los compradores potenciales respondan y soliciten ver el automóvil. Cada uno insiste en una decisión inmediata del vendedor de aceptar o no la oferta. Defina una oferta como interesante y codifique 1 si es mejor que todas las ofertas anteriores y codifique 0 en caso contrario. Las ofertas formarán una secuencia aleatoria de 0 y 1. Sólo los 1 interesan al vendedor, quien puede temer que cada 1 sucesivo sea el último. De la definición se desprende que el último 1 es la oferta más alta. Maximizar la probabilidad de vender el último significa, por tanto, maximizar la probabilidad de vender mejor . ${\displaystyle n}$
2. Un médico, que utiliza un tratamiento especial, puede utilizar el código 1 para un tratamiento exitoso, 0 en caso contrario. El médico trata a una secuencia de pacientes de la misma manera y quiere minimizar cualquier sufrimiento y tratar a todos los pacientes receptivos de la secuencia. Detenerse en el último 1 en una secuencia aleatoria de 0 y 1 lograría este objetivo. Dado que el médico no es un profeta, el objetivo es maximizar la probabilidad de detenerse en el último 1. (Ver Uso compasivo ). ${\displaystyle n}$

Definiciones

Considere una secuencia de eventos independientes . Asocie con esta secuencia otra secuencia de eventos independientes con valores 1 o 0. Aquí , llamado éxito, representa el evento en el que la k-ésima observación es interesante (según lo define quien toma las decisiones) y no es interesante. Estas variables aleatorias se observan secuencialmente y el objetivo es seleccionar correctamente el último éxito cuando se observa. ${\displaystyle n}$ ${\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}$ ${\displaystyle \,I_{k}=1}$ ${\displaystyle \,I_{k}=0}$ ${\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}$

Sea la probabilidad de que el k-ésimo evento sea interesante. Además deja y . Tenga en cuenta que representa las probabilidades de que el k-ésimo evento resulte interesante, lo que explica el nombre del algoritmo de probabilidades. ${\displaystyle \,p_{k}=P(\,I_{k}\,=1)}$ ${\displaystyle \,q_{k}=\,1-p_{k}}$ ${\displaystyle \,r_{k}=p_{k}/q_{k}}$ ${\displaystyle \,r_{k}}$

Procedimiento algorítmico

El algoritmo de probabilidades suma las probabilidades en orden inverso

${\displaystyle r_{n}+r_{n-1}+r_{n-2}\,+\cdots ,\,}$

hasta que esta suma alcance o supere el valor 1 por primera vez. Si esto sucede en el índice s , guarda s y la suma correspondiente.

${\displaystyle R_{s}=\,r_{n}+r_{n-1}+r_{n-2}+\cdots +r_{s}.\,}$

Si la suma de las probabilidades no llega a 1, establece s  = 1. Al mismo tiempo calcula

${\displaystyle Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,}$

La salida es

1. ${\displaystyle \,s}$, el umbral de parada
2. ${\displaystyle \,w=Q_{s}R_{s}}$, la probabilidad de ganar.

estrategia de probabilidades

La estrategia de probabilidades es la regla de observar los eventos uno tras otro y detenerse en el primer evento interesante desde el índice s en adelante (si lo hay), donde s es el umbral de parada de la salida a.

La importancia de la estrategia de probabilidades y, por tanto, del algoritmo de probabilidades, radica en el siguiente teorema de probabilidades.

Teorema de probabilidades

El teorema de las probabilidades establece que

1. La estrategia de probabilidades es óptima , es decir, maximiza la probabilidad de detenerse en el último 1.
2. La probabilidad de ganar de la estrategia de probabilidades es igual ${\displaystyle w=Q_{s}R_{s}}$
3. Si , la probabilidad de ganar es siempre al menos 1/ e = 0,367879... , y este límite inferior es el mejor posible . ${\displaystyle R_{s}\geq 1}$ ${\displaystyle w}$

Características

El algoritmo de probabilidades calcula la estrategia óptima y la probabilidad óptima de ganar al mismo tiempo. Además, el número de operaciones del algoritmo de probabilidades es (sub)lineal en n. Por lo tanto, no puede existir ningún algoritmo más rápido para todas las secuencias, de modo que el algoritmo de probabilidades sea, al mismo tiempo, óptimo como algoritmo.

Fuentes

Bruss 2000 ideó el algoritmo de probabilidades y acuñó su nombre. También se le conoce como algoritmo de Bruss (estrategia). Se pueden encontrar implementaciones gratuitas en la web.

Aplicaciones

Las aplicaciones van desde preguntas médicas en ensayos clínicos sobre problemas de ventas, problemas de secretaria , selección de cartera , estrategias de búsqueda (unidireccionales), problemas de trayectoria y problema de estacionamiento hasta problemas de mantenimiento en línea y otros.

Existe, con el mismo espíritu, un teorema de probabilidades para procesos de llegada en tiempo continuo con incrementos independientes , como el proceso de Poisson (Bruss 2000). En algunos casos, las probabilidades no necesariamente se conocen de antemano (como en el ejemplo 2 anterior), por lo que la aplicación del algoritmo de probabilidades no es directamente posible. En este caso, cada paso puede utilizar estimaciones secuenciales de las probabilidades. Esto es significativo si el número de parámetros desconocidos no es grande en comparación con el número n de observaciones. Sin embargo, la cuestión de la optimización es más complicada y requiere estudios adicionales. Las generalizaciones del algoritmo de probabilidades permiten diferentes recompensas por no detenerse y por detenerse incorrectamente, así como reemplazar los supuestos de independencia por otros más débiles (Ferguson (2008)).

Variaciones

Bruss y Paindaveine 2000 discutieron el problema de seleccionar los últimos éxitos. ${\displaystyle k}$

Tamaki 2010 demostró un teorema de probabilidades multiplicativas que aborda el problema de detenerse en cualquiera de los últimos éxitos. Matsui & Ano (2014) obtienen un límite inferior ajustado de probabilidad de ganar. ${\displaystyle \ell }$

Matsui & Ano 2017 discutió el problema de seleccionar entre los últimos éxitos y obtuvo un límite inferior ajustado de probabilidad de ganar. Cuando el problema es equivalente al problema de probabilidades de Bruss. Si el problema es equivalente al de Bruss & Paindaveine 2000. Un problema discutido por Tamaki 2010 se obtiene configurando ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle \ell =k=1,}$ ${\displaystyle \ell =k\geq 1,}$ ${\displaystyle \ell \geq k=1.}$

problema de opción múltiple

A un jugador se le permiten opciones y gana si alguna de ellas es el último éxito. Para el problema clásico de la secretaria, Gilbert y Mosteller 1966 analizaron los casos . El problema de las probabilidades se analiza en Ano, Kakinuma y Miyoshi 2010. Para más casos de problemas de probabilidades, consulte Matsui y Ano 2016. ${\displaystyle r}$ ${\displaystyle r=2,3,4}$ ${\displaystyle r=2,3}$

Una estrategia óptima para este problema pertenece a la clase de estrategias definidas por un conjunto de números umbral , donde . ${\displaystyle (a_{1},a_{2},...,a_{r})}$ ${\displaystyle a_{1}>a_{2}>\cdots >a_{r}}$

Específicamente, imagine que tiene cartas de aceptación etiquetadas desde hasta . Tendría oficiales de solicitud, cada uno con una letra. Continúa entrevistando a los candidatos y clasificándolos en un cuadro que todos los funcionarios de solicitudes pueden ver. Ahora el oficial enviaría su carta de aceptación al primer candidato que sea mejor que todos los candidatos . (Las cartas de aceptación no enviadas se entregan por defecto a los últimos solicitantes, al igual que en el problema estándar de secretaria). ${\displaystyle r}$ ${\displaystyle 1}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle i}$ ${\displaystyle 1}$ ${\displaystyle a_{i}}$

Cuando Ano, Kakinuma y Miyoshi (2010) demostraron que el límite inferior estricto de la probabilidad de ganar es igual a Para un entero positivo general , Matsui y Ano (2016) demostraron que el límite inferior estricto de la probabilidad de ganar es la probabilidad de ganar de la variante del problema de secretaria en la que se debe Elija los k candidatos principales utilizando solo k intentos . ${\displaystyle r=2}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}.}$ ${\displaystyle r}$

Cuando , los estrechos límites inferiores de las probabilidades de ganar son iguales a , y respectivamente. ${\displaystyle r=3,4,5}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}$ ${\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},}$

Para más casos numéricos para y un algoritmo para casos generales, consulte Matsui & Ano 2016. ${\displaystyle r=6,...,10}$

Ver también

• Impares
• Ensayo clínico
• Acceso ampliado
• problema de secretaria

Referencias

• Año, K.; Kakinuma, H.; Miyoshi, N. (2010). "Teorema de probabilidades con múltiples posibilidades de selección". Revista de probabilidad aplicada . 47 (4): 1093-1104. doi : 10.1239/jap/1294170522 . S2CID  17598431.
• Bruss, F. Thomas (2000). "Sume las probabilidades a uno y deténgase". Los anales de la probabilidad . 28 (3). Instituto de Estadística Matemática: 1384-1391. doi : 10.1214/aop/1019160340 . ISSN  0091-1798.
  • "Una nota sobre los límites del teorema de probabilidades de detención óptima", Annals of Probability vol. 31, 1859–1862, (2003).
  • "El arte de tomar una decisión correcta", Boletín de la Sociedad Matemática Europea , Número 62, 14-20, (2005).
• TS Ferguson : (2008, inédito)
• Bruss, PIE; Paindaveine, D. (2000). "Seleccionar una secuencia de últimos éxitos en ensayos independientes" (PDF) . Revista de probabilidad aplicada . 37 (2): 389–399. doi : 10.1239/jap/1014842544.
• Gilbert, J; Mosteller, F (1966). "Reconocer el máximo de una secuencia". Revista de la Asociación Estadounidense de Estadística . 61 (313): 35–73. doi :10.2307/2283044. JSTOR  2283044.
• Matsui, T; Año, K (2014). "Una nota sobre un límite inferior para el teorema de las probabilidades multiplicativas de parada óptima". Revista de probabilidad aplicada . 51 (3): 885–889. doi : 10.1239/jap/1409932681 .
• Matsui, T; Año, K (2016). "Límites inferiores para el problema de probabilidades de Bruss con múltiples detenciones". Matemáticas de la Investigación de Operaciones . 41 (2): 700–714. arXiv : 1204.5537 . doi :10.1287/moor.2015.0748. S2CID  31778896.
• Matsui, T; Año, K (2017). "Compare la relación de polinomios simétricos de probabilidades a uno y deténgase". Revista de probabilidad aplicada . 54 : 12-22. doi :10.1017/jpr.2016.83. S2CID  41639968.
• Shoo-Ren Hsiao y Jiing-Ru. Yang: "Selección del último éxito en ensayos dependientes de Markov", Journal of Applied Probability , vol. 93, 271–281, (2002).
• Tamaki, M (2010). "Sume las probabilidades multiplicativas a uno y deténgase". Revista de probabilidad aplicada . 47 (3): 761–777. doi : 10.1239/jap/1285335408 . S2CID  32236265.
• Mitsushi Tamaki: "Detención óptima en trayectorias y el problema de las papeletas", Journal of Applied Probability vol. 38, 946–959 (2001).
• E. Thomas, E. Levrat, B. Iung: "El algoritmo de Bruss como contribución a un mantenimiento preventivo", Sciences et Technologies de l'automation , vol. 4, 13-18 (2007).

enlaces externos

• Algoritmo de Bruss http://www.p-roesler.de/odds.html