El principio de decisiones diferidas es una técnica utilizada en el análisis de algoritmos aleatorios .
Definición
Un algoritmo aleatorio hace un conjunto de elecciones aleatorias. Estas elecciones aleatorias pueden estar estrechamente relacionadas, lo que dificulta su análisis. En muchos de estos casos se utiliza el principio de decisiones diferidas . La idea detrás del principio es que todo el conjunto de elecciones aleatorias no se hace de antemano, sino que se fija solo a medida que se revelan al algoritmo.
Aplicaciones
El juego de solitario Clock
El principio se utiliza para evaluar y determinar la probabilidad de "ganar" de una baraja de cartas . La idea es dejar que se desarrollen las elecciones aleatorias, hasta que la iteración termine en 52, donde si la cuarta carta se extrae de un grupo etiquetado como "K", el juego termina. [ cita requerida ]
Referencias
Fuentes
- M. Mitzenmacher y E. Upfal . Probabilidad y computación: algoritmos aleatorios y análisis probabilístico. Cambridge University Press, Nueva York (NY), 2005. Sección 1.3, página 9.