Randomiser ou pas?

Cette question est inspirée du t-shirt du Georgia Tech Algorithms and Randomness Center , qui demande "Randomize or not ?!"

Il existe de nombreux exemples où la randomisation est utile, en particulier lors d'opérations dans des environnements contradictoires. Il existe également certains paramètres dans lesquels la randomisation n'aide ni ne blesse. Ma question est:

Quels sont certains paramètres lorsque la randomisation (d'une manière apparemment raisonnable) fait vraiment mal?

N'hésitez pas à définir les «paramètres» et les «blessures» de manière large, que ce soit en termes de complexité du problème, de garanties prouvables, de taux d'approximation ou de durée d'exécution (je m'attends à ce que la durée d'exécution soit la réponse la plus évidente). Plus l'exemple est intéressant, mieux c'est!

Voici un exemple simple de la théorie des jeux. Dans les jeux où les équilibres de Nash purs et mixtes existent, les mixtes sont souvent beaucoup moins naturels, et bien "pires".

$\log(n)/\log\log(n)$

Le message à retenir: la randomisation peut nuire à la coordination.

Voici un exemple simple du domaine des algorithmes distribués.

Typiquement, le caractère aléatoire aide énormément. Les algorithmes distribués randomisés sont souvent plus faciles à concevoir et ils sont plus rapides.

Cependant, si vous disposez d'un algorithme distribué déterministe rapide, vous pouvez le convertir mécaniquement [ 1 , 2 ] en un algorithme auto-stabilisant rapide . En substance, vous obtiendrez gratuitement une version très forte de tolérance aux pannes (au moins si la ressource goulot d'étranglement est le nombre de tours de communication). Vous pouvez simplifier la conception de votre algorithme en vous concentrant sur des réseaux statiques synchrones sans défaut, et la conversion vous donnera un algorithme tolérant aux pannes qui peut gérer des réseaux dynamiques asynchrones.

Une telle conversion n'est pas connue pour les algorithmes distribués randomisés en général.

Permettez-moi d'abord de soulever un problème concernant le caractère aléatoire:

Existe-t-il un caractère aléatoire dans l'univers ou tout est-il déterministe?

Il s'agit d'une question philosophique qui est à la fois controversée et sans rapport avec le contexte ici. Pourtant, je l'ai utilisé comme mot d'avertissement, car la réponse à venir sera controversée si l'on approfondit trop la question ci-dessus.

Le théorème de Shannon – Hartley décrit la capacité d'un canal de communication en présence de bruit. Le bruit passe de 0 à 1 et vice versa, avec une probabilité prédéfinie.

Si le canal se comportait de manière déterministe --- Autrement dit, si nous pouvions modéliser le bruit de manière à pouvoir déterminer quels bits changeraient --- La capacité du canal serait infiniment grande. Très souhaitable!

J'aime analogiser l'aléatoire au frottement: il résiste au mouvement, mais le mouvement est impossible sans lui.