La probabilidad permite diseñar y analizar algoritmos que usan elecciones aleatorias. Se puede estudiar el tiempo esperado, evitar entradas adversas, estimar resultados y resolver problemas donde una estrategia determinista sería costosa.
Un algoritmo aleatorizado utiliza números aleatorios durante su ejecución. Para una misma entrada puede seguir caminos diferentes y tener distintos tiempos de ejecución o resultados intermedios.
Si T es el tiempo de ejecución y puede tomar valores ti con probabilidades pi, su tiempo esperado es:
El tiempo esperado no significa que cada ejecución tarde exactamente E(T). Algunas corridas pueden ser más lentas o más rápidas.
Un algoritmo Monte Carlo tiene un costo acotado o controlable, pero puede producir una respuesta incorrecta con cierta probabilidad. Repitiendo el algoritmo y combinando resultados puede reducirse el error.
El diseño debe indicar explícitamente la probabilidad de error y cómo se calcula.
Un algoritmo Las Vegas siempre entrega una respuesta correcta, pero su tiempo de ejecución es aleatorio. El azar afecta el camino o el costo, no la validez de la respuesta.
La distinción ayuda a evaluar qué tipo de garantía necesita una aplicación.
El algoritmo Fisher-Yates recorre la lista y elige aleatoriamente una posición disponible para intercambiarla. Si se eligen las posiciones correctamente, cada permutación tiene la misma probabilidad.
Un barajado sesgado puede afectar juegos, muestreos y pruebas. La simulación permite comprobar si las posiciones aparecen con frecuencias parecidas.
QuickSort elige un pivote y divide los elementos menores y mayores. Elegir el pivote al azar reduce la probabilidad de caer repetidamente en divisiones muy desequilibradas:
La aleatorización protege frente a entradas especialmente desfavorables, aunque no elimina la posibilidad matemática del peor caso.
Para seleccionar una muestra uniforme de una población grande se pueden usar índices aleatorios. Si no se permite repetir elementos, hay que actualizar el conjunto disponible o emplear un algoritmo como Fisher-Yates parcial.
Una selección con probabilidades incorrectas produce sesgo y puede invalidar las conclusiones estadísticas.
En una caminata aleatoria, cada paso cambia la posición según una elección probabilística. Aunque cada paso sea simple, el comportamiento acumulado puede estudiarse con esperanza, varianza y simulación.
Este código implementa una caminata aleatoria y devuelve la posición final:
function caminata(pasos) {
let posicion = 0;
for (let i = 0; i < pasos; i++) {
posicion += Math.random() < 0.5 ? -1 : 1;
}
return posicion;
}
console.log(caminata(1000));Pulsa Ejecutar para observar una posición final distinta en cada ejecución.
Simula muchas caminatas y observa la distribución de sus posiciones finales. La línea vertical marca la posición esperada, que es 0 en una caminata equilibrada.
Algunas operaciones son costosas solo ocasionalmente. Si los costos altos aparecen con baja frecuencia, el costo promedio sobre una secuencia larga puede ser pequeño.
El análisis amortizado no siempre es una esperanza probabilística, pero ambos enfoques usan promedios para describir el comportamiento global y no una única operación.
Una función hash distribuye claves en posiciones. Las colisiones son inevitables cuando hay más claves posibles que posiciones, pero una buena distribución hace que el número de colisiones esperado sea bajo.
El análisis probabilístico ayuda a estimar el rendimiento de tablas hash.
Skip lists, filtros de Bloom y estructuras de muestreo usan decisiones aleatorias para obtener operaciones rápidas o ahorrar memoria. Algunas aceptan falsos positivos, mientras que otras garantizan la respuesta y randomizan el tiempo.
Los algoritmos aleatorizados aparecen en ordenamiento, selección, criptografía, redes, muestreo, optimización, aprendizaje automático, estructuras de datos y simulación. También son útiles para evitar comportamientos sistemáticos en sistemas distribuidos.
La probabilidad aporta herramientas para diseñar algoritmos rápidos, robustos y analizables. La clave es describir con claridad qué afecta el azar: la respuesta, el tiempo, la memoria o la distribución de los casos.