Zufällig oder nicht?

Diese Frage ist vom T-Shirt des Georgia Tech Algorithms and Randomness Center inspiriert, in dem die Frage gestellt wird: " Zufällig oder nicht ?!"

Es gibt viele Beispiele, in denen Randomisierung hilfreich ist, insbesondere wenn Sie in einer widrigen Umgebung arbeiten. Es gibt auch einige Einstellungen, bei denen Randomisierung nicht hilft oder schadet. Meine Frage ist:

Was sind einige Einstellungen, wenn Randomisierung (auf eine scheinbar vernünftige Weise) tatsächlich weh tut?

Fühlen Sie sich frei, "Einstellungen" und "Schmerzen" allgemein zu definieren, sei es in Bezug auf die Komplexität des Problems, nachweisbare Garantien, Annäherungsverhältnisse oder Laufzeit (ich gehe davon aus, dass die Laufzeit die klareren Antworten liefert). Je interessanter das Beispiel, desto besser!

randomness big-picture randomized-algorithms Lev Reyzin
quelle

Abgestimmt. Diese Frage scheint mir eine Frage zur Rhetorik zu sein, da der Schwerpunkt der Frage zu sein scheint, wie man argumentieren kann, dass eine bestimmte Tatsache als „zufällige Verletzungen“ bezeichnet werden kann.

Tsuyoshi Ito

Meinetwegen. Aber lassen Sie mich Ihnen ein Beispiel geben, was ich vorhatte. Nehmen wir an, wir haben einen Lernalgorithmus, der Aktionen enthält, die er ausführen kann, und der sie in der Lernphase im Round Robin durchführt. Angenommen, es gibt eine Garantie. Angenommen, wir ziehen stattdessen in Betracht, zufällig einheitliche Maßnahmen zu ergreifen, und stellen fest, dass die Garantie verloren geht. Schwer zu argumentieren, dass dies kein Beispiel für zufälliges "Verletzen" ist. Und zögern Sie nicht, "weh" für sich selbst zu definieren! Auch wenn das Teil Ihrer Kritik sein könnte ...

Lev Reyzin

lass es spielen: vielleicht bekommen wir eine interessante diskussion. Ich kenne mindestens einen Fall, in dem die einfache randomisierte Strategie tatsächlich schlechter ist als ein vorsichtiger deterministischer Algorithmus

Suresh Venkat

Der Grund, warum mir diese Frage nicht gefällt, liegt wahrscheinlich darin, dass ich erwarte, dass die meisten Antworten nur in ihrer Interpretation der Frage „interessant“ sind. Die Frage scheint zu kreativen und rhetorischen Interpretationen anzuregen. Wenn dies nicht das ist, was Sie wollen, und Sie einen besseren Weg finden, die Frage zu formulieren, überarbeiten Sie sie bitte (aber mir fällt keiner ein).

Tsuyoshi Ito

Ich habe nicht erwartet, dass diese Frage so kontrovers ist :) Trotzdem stören mich interessante Interpretationen nicht! Ich denke, wir müssen uns in diesem Punkt nicht einigen. Übrigens, wenn die Unbestimmtheit der Frage störend ist, macht es mir nichts aus, @Suresh zu einem CW zu machen ...

Lev Reyzin

Antworten:

Hier ist ein einfaches Beispiel aus der Spieltheorie. In Spielen, in denen sowohl reine als auch gemischte Nash-Gleichgewichte existieren, sind die gemischten oft viel weniger natürlich und viel "schlechter".

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

Die Botschaft zum Mitnehmen: Randomisierung kann die Koordination beeinträchtigen.

Aaron Roth
quelle

cool - Ich mag diese Interpretation von Bällen und Behältern als 2-Spieler-Spiel. Dies ist die Art von Antwort, die ich im Sinn hatte!

Lev Reyzin

Es wird manchmal in seiner getarnten Form als "das Lastausgleichsspiel auf identischen Computern" diskutiert :-)

Aaron Roth

Hier ist ein einfaches Beispiel aus dem Bereich der verteilten Algorithmen.

Typischerweise hilft Zufälligkeit enorm. Randomisierte verteilte Algorithmen sind oft einfacher zu entwerfen und schneller.

Wenn Sie jedoch einen schnellen deterministischen verteilten Algorithmus haben, können Sie ihn mechanisch [ 1 , 2 ] in einen schnellen selbststabilisierenden Algorithmus umwandeln . Im Wesentlichen erhalten Sie kostenlos eine sehr starke Version der Fehlertoleranz (zumindest, wenn die Engpassressource die Anzahl der Kommunikationsrunden ist). Sie können Ihren Algorithmusentwurf vereinfachen, indem Sie sich auf fehlerfreie synchrone statische Netzwerke konzentrieren. Durch die Konvertierung erhalten Sie einen fehlertoleranten Algorithmus, der mit asynchronen dynamischen Netzwerken umgehen kann.

Für randomisierte verteilte Algorithmen ist im Allgemeinen keine solche Konvertierung bekannt .

Jukka Suomela
quelle

Lassen Sie mich zunächst ein Problem in Bezug auf die Zufälligkeit ansprechen:

Gibt es im Universum Zufälligkeiten oder ist alles deterministisch?

Dies ist eine philosophische Frage, die sowohl umstritten als auch in keinem Zusammenhang mit dem Kontext steht. Dennoch habe ich es als warnendes Wort benutzt, da die bevorstehende Antwort umstritten sein wird, wenn man sich zu tief mit der obigen Frage befasst.

Das Shannon-Hartley-Theorem beschreibt die Kapazität eines Kommunikationskanals bei Vorhandensein von Rauschen. Das Rauschen ändert sich mit einer bestimmten Wahrscheinlichkeit von 0 auf 1 und umgekehrt.

Wenn sich der Kanal deterministisch verhalten würde --- Das heißt, wenn wir das Rauschen so modellieren könnten, dass wir bestimmen könnten, welche Bits sich ändern würden --- Die Kapazität des Kanals wäre unendlich groß. Sehr wünschenswert!

Ich vergleiche gerne Zufälligkeit mit Reibung: Sie widersteht der Bewegung, aber ohne sie ist Bewegung unmöglich.

MS Dousti
quelle