Esta pregunta está inspirada en la camiseta de Georgia Tech Algorithms and Randomness Center , que pregunta "¿Aleatorizar o no?"
Hay muchos ejemplos en los que la aleatorización ayuda, especialmente cuando se opera en entornos adversos. También hay algunas configuraciones donde la aleatorización no ayuda ni perjudica. Mi pregunta es:
¿Cuáles son algunas configuraciones cuando la aleatorización (de alguna manera aparentemente razonable) realmente duele?
Siéntase libre de definir "ajustes" y "daños" en términos generales, ya sea en términos de complejidad del problema, garantías comprobables, relaciones de aproximación o tiempo de ejecución (espero que el tiempo de ejecución sea donde radiquen las respuestas más obvias). ¡Cuanto más interesante sea el ejemplo, mejor!
fuente
Respuestas:
Aquí hay un ejemplo simple de la teoría de juegos. En los juegos en los que existen equilibrios de Nash puros y mixtos, los mixtos son a menudo mucho menos naturales y mucho "peores".
El mensaje final: la aleatorización puede dañar la coordinación.
fuente
Aquí hay un ejemplo simple del campo de algoritmos distribuidos.
Por lo general, la aleatoriedad ayuda enormemente. Los algoritmos distribuidos aleatorios suelen ser más fáciles de diseñar y más rápidos.
Sin embargo, si tiene un algoritmo distribuido determinista rápido , puede convertirlo mecánicamente [ 1 , 2 ] en un algoritmo autoestabilizador rápido . En esencia, obtendrá una versión muy fuerte de tolerancia a fallas de forma gratuita (al menos si el recurso de cuello de botella es la cantidad de rondas de comunicación). Puede simplificar el diseño de su algoritmo centrándose en redes estáticas sincrónicas sin fallas, y la conversión le dará un algoritmo tolerante a fallas que puede manejar redes dinámicas asíncronas.
No se conoce dicha conversión para algoritmos distribuidos aleatorios en general.
fuente
Permítanme primero plantear un problema relacionado con la aleatoriedad:
Esta es una pregunta filosófica que es controvertida y no está relacionada con el contexto aquí. Sin embargo, lo usé como advertencia, ya que la próxima respuesta será controvertida si uno profundiza demasiado en la pregunta anterior.
El teorema de Shannon-Hartley describe la capacidad de un canal de comunicación en presencia de ruido. El ruido cambia de 0s a 1s y viceversa, con alguna probabilidad preespecificada.
Si el canal se comportó de manera determinista, es decir, si pudiéramos modelar el ruido de manera que pudiéramos determinar qué bits cambiarían, la capacidad del canal sería infinitamente grande. Muy deseable!
Me gusta analogizar la aleatoriedad con la fricción: es resistir el movimiento, pero el movimiento es imposible sin él.
fuente