Hispanopedia Wiki
Articulo de referencia

Algoritmo de probabilidades

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 perte...

Hispanopedia WikiContenido en espanolLectura gratuita

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 esta estrategia radica en su optimalidad, como se explica más adelante.

El algoritmo de probabilidades se aplica a una clase de problemas denominados problemas de último éxito . Formalmente, el objetivo de estos problemas es maximizar la probabilidad de identificar, en una secuencia de eventos independientes observados consecutivamente, el último evento que cumpla un criterio específico (un "evento específico"). Esta identificación debe realizarse en el momento de la observación. No se permite revisar observaciones anteriores. Generalmente, quien toma la decisión define un evento específico como aquel de verdadero interés para "detenerse" y emprender una acción bien definida. Este tipo de problemas se presentan en diversas 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").norte{\displaystyle n}Los compradores potenciales responden y piden ver el coche. Cada uno insiste en una decisión inmediata del vendedor sobre si aceptar o no la oferta. Definimos una oferta como interesante y la codificamos con 1 si es mejor que todas las ofertas anteriores, y con 0 en caso contrario. Las ofertas formarán una secuencia aleatoria de 0 y 1. Solo los 1 interesan al vendedor, quien puede temer que cada 1 sucesivo sea el último. De la definición se deduce que el último 1 es la oferta más alta. Por lo tanto, maximizar la probabilidad de vender con el último 1 significa maximizar la probabilidad de vender al mejor precio .
  2. Un médico, al utilizar un tratamiento especial, puede usar el código 1 para un tratamiento exitoso, 0 en caso contrario. El médico trata una secuencia denorte{\displaystyle n}El médico trata a todos los pacientes de la misma manera, busca minimizar el sufrimiento y tratar a cada paciente que responda al tratamiento en la secuencia. Detenerse en el último 1 de dicha secuencia aleatoria de 0s y 1s lograría este objetivo. Dado que el médico no es profeta, el objetivo es maximizar la probabilidad de detenerse en el último 1. (Véase Uso compasivo ).

Definiciones

Consideremos una secuencia denorte{\displaystyle n}eventos independientes . Asocie con esta secuencia otra secuencia de eventos independientes.I1,I2,…,Inorte{\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}} con valores 1 o 0. Aquí Ik=1{\displaystyle \,I_{k}=1}, llamado éxito, representa el evento de que la k-ésima observación sea interesante (según lo define el responsable de la toma de decisiones), yIk=0{\displaystyle \,I_{k}=0}para lo que no es interesante. Estas variables aleatoriasI1,I2,…,Inorte{\displaystyle I_{1},\,I_{2},\,\dots ,\,I_{n}}se observan secuencialmente y el objetivo es seleccionar correctamente el último éxito cuando se observa.

Dejarpagk=PAG(Ik=1){\displaystyle \,p_{k}=P(\,I_{k}\,=1)}Sea la probabilidad de que el k-ésimo evento sea interesante. Además, sea qk=1−pagk{\displaystyle \,q_{k}=\,1-p_{k}}yrk=pagk/qk{\displaystyle \,r_{k}=p_{k}/q_{k}}. Tenga en cuenta querk{\displaystyle \,r_{k}}representa la probabilidad de que el k-ésimo evento resulte interesante, lo que explica el nombre del algoritmo de probabilidades.

Procedimiento algorítmico

El algoritmo de probabilidades suma las probabilidades en orden inverso.

rnorte+rnorte−1+rnorte−2+⋯,{\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 ocurre en el índice s , guarda s y la suma correspondiente.

Rs=rnorte+rnorte−1+rnorte−2+⋯+rs.{\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

Qs=qnorteqnorte−1⋯qs.{\displaystyle Q_{s}=q_{n}q_{n-1}\cdots q_{s}.\,}

El resultado es

  1. s{\displaystyle \,s}el umbral de parada
  2. w=QsRs{\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 a partir del índice s (si lo hay), donde s es el umbral de parada de la salida a.

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

Teorema de las 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 a w=QsRs{\displaystyle w=Q_{s}R_{s}}
  3. SiRs≥1{\displaystyle R_{s}\geq 1}la probabilidad de ganarw{\displaystyle w}siempre es al menos 1/ e = 0,367879... , y este límite inferior es el mejor posible .

Características

El algoritmo de probabilidades calcula simultáneamente la estrategia óptima y la probabilidad de victoria óptima . Además, el número de operaciones del algoritmo de probabilidades es (sub)lineal en n. Por lo tanto, no puede existir un algoritmo más rápido para todas las secuencias, de modo que el algoritmo de probabilidades es, a su vez, óptimo como algoritmo.

Fuentes

Bruss ideó el algoritmo de probabilidades y le dio su nombre. También se le conoce como algoritmo (estrategia) de Bruss. Se pueden encontrar implementaciones gratuitas en internet.

Aplicaciones

Tres casos del problema de la secretaria donde la altura del icono indica el grado de deseabilidad:
  1. Un conjunto de exploración demasiado pequeño selecciona un candidato subóptimo antes de que se vea el mejor (*).
  2. Un conjunto ideal identifica lo mejor.
  3. Si un conjunto demasiado grande incluye al mejor candidato, se selecciona al último.

Las aplicaciones abarcan desde cuestiones médicas en ensayos clínicos , pasando por problemas de ventas, problemas administrativos , selección de cartera , estrategias de búsqueda (unidireccionales), problemas de trayectoria y el problema del estacionamiento, hasta problemas en el mantenimiento en línea y otros.

Existe, en 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 se conocen necesariamente 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 usar estimaciones secuenciales de las probabilidades. Esto es útil 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 optimalidad es entonces más compleja y requiere estudios adicionales. Las generalizaciones del algoritmo de probabilidades permiten diferentes recompensas por no detenerse y por paradas incorrectas, así como reemplazar los supuestos de independencia por otros más débiles ( Ferguson 2008 ) .

Variaciones

Bruss y Paindaveine (2000) analizaron un problema de selección del últimok{\displaystyle k}éxitos.

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

Matsui y Ano (2017) analizaron un problema de selecciónk{\displaystyle k}de los últimosℓ{\displaystyle \ell }éxitos y obtuvo un límite inferior ajustado de probabilidad de victoria. Cuando ℓ=k=1,{\displaystyle \ell =k=1,}El problema es equivalente al problema de probabilidades de Bruss. Si ℓ=k≥1,{\displaystyle \ell =k\geq 1,}El problema es equivalente al de Bruss y Paindaveine (2000) . Un problema discutido por Tamaki (2010) se obtiene al establecerℓ≥k=1.{\displaystyle \ell \geq k=1.}

Problema de opción múltiple

Se permite un jugadorr{\displaystyle r}opciones, y gana si alguna opción es el último éxito. Para el problema clásico del secretario, Gilbert y Mosteller (1966) analizaron los casos.r=2,3,4{\displaystyle r=2,3,4}El problema de las probabilidades conr=2,3{\displaystyle r=2,3}Ano, Kakinuma y Miyoshi lo analizan en 2010. Para más casos de problemas de probabilidades, véase Matsui y Ano en 2016 .

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

Específicamente, imagina que tienesr{\displaystyle r}cartas de aceptación etiquetadas desde1{\displaystyle 1}ar{\displaystyle r}.Tú tendríasr{\displaystyle r}Oficiales de solicitud, cada uno con una letra. Sigues entrevistando a los candidatos y los clasificas en una tabla que todos los oficiales de solicitud pueden ver. Ahora, oficiali{\displaystyle i}enviarían su carta de aceptación al primer candidato que sea mejor que todos los demás candidatos.1{\displaystyle 1}aai{\displaystyle a_{i}}(Las cartas de aceptación no enviadas se entregan por defecto a los últimos solicitantes, al igual que en el problema estándar de la secretaria).

Cuandor=2{\displaystyle r=2}, Ano, Kakinuma y Miyoshi 2010 demostraron que el límite inferior ajustado de la probabilidad de ganar es igual ami−1+mi−32.{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}.} Para un entero positivo generalr{\displaystyle r}Matsui y Ano (2016) demostraron que el límite inferior ajustado de la probabilidad de ganar es la probabilidad de ganar de la variante del problema de la secretaria en la que uno debe elegir a los k mejores candidatos usando solo k intentos .

Cuandor=3,4,5{\displaystyle r=3,4,5}, los límites inferiores ajustados de las probabilidades de victoria son iguales ami−1+mi−32+mi−4724{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}},mi−1+mi−32+mi−4724+mi−27611152{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}}y mi−1+mi−32+mi−4724+mi−27611152+mi−41626371474560,{\displaystyle e^{-1}+e^{-{\frac {3}{2}}}+e^{-{\frac {47}{24}}}+e^{-{\frac {2761}{1152}}}+e^{-{\frac {4162637}{1474560}}},}respectivamente.

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

Véase también

Referencias

  • Ano, K.; Kakinuma, H.; Miyoshi, N. (2010). "Teorema de probabilidades con múltiples posibilidades de selección" . Journal of Applied Probability . 47 (4): 1093– 1104. doi : 10.1239/jap/1294170522 . S2CID 17598431 . 
  • Bruss, F. Thomas (2000). "Suma las probabilidades a uno y detente" . The Annals of Probability . 28 (3). Institute of Mathematical Statistics: 1384– 1391. doi : 10.1214/aop/1019160340 . hdl : 2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/182735 . ISSN 0091-1798 . 
    • " Una nota sobre los límites del teorema de las probabilidades de parada óptima ", Anales de Probabilidad Vol. 31, 1859 – 1862, (2003).
    • " El arte de tomar la decisión correcta ", Boletín informativo de la Sociedad Matemática Europea , número 62, 14 – 20, (2005).
  • TS Ferguson : (2008, inédito)
  • Bruss, FT; Paindaveine, D. (2000). "Selección de una secuencia de últimos éxitos en ensayos independientes" (PDF) . Journal of Applied Probability . 37 (2): 389– 399. doi : 10.1239/jap/1014842544 .
  • Gilbert, J; Mosteller, F (1966). "Reconociendo el máximo de una secuencia". Journal of the American Statistical Association . 61 (313): 35– 73. doi : 10.2307/2283044 . JSTOR 2283044 . 
  • Matsui, T; Ano, K (2014). "Una nota sobre una cota inferior para el teorema de probabilidades multiplicativas de parada óptima" . Journal of Applied Probability . 51 (3): 885– 889. doi : 10.1239/jap/1409932681 .
  • Matsui, T; Ano, K (2016). "Límites inferiores para el problema de probabilidades de Bruss con paradas múltiples". Mathematics of Operations Research . 41 (2): 700– 714. arXiv : 1204.5537 . doi : 10.1287/moor.2015.0748 . S2CID 31778896 . 
  • Matsui, T; Ano, K (2017). "Comparar la razón de polinomios simétricos de impares a uno y detenerse" . Journal of Applied Probability . 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). "Suma las probabilidades multiplicativas a uno y detente" . Journal of Applied Probability . 47 (3): 761– 777. doi : 10.1239/jap/1285335408 . S2CID 32236265 . 
  • Mitsushi Tamaki: " Parada óptima en trayectorias y el problema de la votación ", 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).
  • Algoritmo de Bruss http://www.p-roesler.de/odds.html
Lecturas relacionadas
6 articulos
"El juicio de Paris" de Wagrez: Paris, vestido con librea medieval y sosteniendo la manzana de la discordia, conversa con Atenea, Afrodita y Hera.Teoría de la decisiónEl juicio mitológico de Paris requirió seleccionar entre tres alternativas incomparables (las diosas mostradas). La teoría de la decisión o teoría ...{\displaystyle X_{1},X_{2},\ldots }Parada óptimaEn matemáticas , la teoría de la parada óptima [ 1 ] [ 2 ] o parada temprana [ 3 ] se ocupa del problema de elegir el momento adecuado para realiza...secuencia aleatoriaEl concepto de secuencia aleatoria es fundamental en la teoría de la probabilidad y la estadística . Este concepto generalmente se basa en la noció...Acceso ampliadoAcceso ampliadoEl acceso ampliado o uso compasivo es el uso de un medicamento o dispositivo médico no aprobado bajo formas especiales de solicitudes de nuevos med...{\displaystyle A}Independencia (teoría de la probabilidad)La independencia es un concepto fundamental en la teoría de la probabilidad , al igual que en la estadística y la teoría de los procesos estocástic...ImparesEn teoría de la probabilidad , las probabilidades proporcionan una medida de la probabilidad de un resultado particular. Las probabilidades se util...