Von gutem und schlechtem Zufall

25 September 2013 by Benjamin Hiller, posted in Computer Science, Deutscher Blog

Die meisten Menschen haben eine intuitive Vorstellung von Zufall, womit in der Regel unvorhersehbare und unbeeinflussbare Ereignisse gemeint sind. Turing-Preisträger Avi Wigderson beschrieb in einem sehr inspirierenden, allgemein verständlichen Vortrag die Bedeutung des Zufalls für die moderne Informatik.

Avi Wigderson

Avi Wigderson
© Klaus Tschira Stiftung / Peter Badge

Obwohl die Natur des Zufalls gerade die Unberechenbarkeit ist, ist dieser gerade für die Entwicklung von Algorithmen, also Rechenvorschriften für den Computer, sehr nützlich. Oft sind Algorithmen, die Zufall geschickt nutzen, einfacher und effizienter als deterministische Lösungen, zum Beispiel beim Testen, ob eine Zahl eine Primzahl ist, für die Koordination der gemeinsamen Nutzung von Ressourcen, in Kryptographie und Authentifizierung oder (nicht ganz so ernst) beim Schreiben wissenschaftlicher Artikel. Manchmal ist es möglich, trotz Zufall das exakte richtige Ergebnis zu bekommen, in der Regel gibt es aber einen kleinen Fehler. Allerdings kann die Fehlerwahrscheinlichkeit oder die Größe des Fehlers durch Tricks meist beliebig verkleinert werden.

Aber warum hilft Zufall überhaupt?
Weil zufällige Objekte bestimmte Eigenschaften haben, die einzelne Objekte nicht unbedingt haben. Ein bekanntes Beispiel ist die Auswahl von Umfrageteilnehmern für die Vorhersage von Wahlergebnissen. Werden genügend Teilnehmer zufällig aus der Gesamtbevölkerung ausgewählt, so ist die Wahrscheinlichkeit sehr hoch, dass sich die Stimmen der Teilnehmer ziemlich genau so verteilen wie die der Gesamtbevölkerung. Fragt man aber die gleiche Anzahl von Teilnehmern, die sich zum Beispiel zu einem bestimmten Zeitpunkt an einem festen Ort aufhalten, so weicht deren Meinungsbild ziemlich sicher stark an von dem der Gesamtbevölkerung.

An diesem Beispiel zeigt sich auch ein wichtiges Problem: Die mathematische Analyse geht von "gutem" Zufall aus. "Guter" Zufall bedeutet einerseits, dass jeder Wahlberechtigte wirklich genau dieselbe Chance hat, an der Umfrage teilzunehmen. Anderseits soll auch die Tatsache, dass ein Wahlberechtigter teilnimmt, keinerlei Auswirkungen darauf haben, ob ein anderer Wahlberechtigter teilnimmt. Diese Ergebnisse des Auswahlprozesses müssen also unabhängig voneinander sein. Bei der Auswahl der Umfrageteilnehmer sind beide Eigenschaften in der Regel nicht streng erfüllt, da zum Beispiel die Umfragemethode (Brief, Telefon, Internet) sowie bei Telefonumfragen der Umfragezeitpunkt Auswirkungen darauf hat, wer überhaupt erreicht wird.

Ein klassisches Beispiel für einen auf den ersten Blick "guten" Zufall ist ein Münzwürf: Hier sollte die Wahrscheinlichkeit für Kopf oder Zahl jeweils genau 1/2 sein und es sollte auch keine Abhängigkeit der Münzwürfe voneinander geben. Allerdings ist ein Münzwurf streng genommen deterministisch, da die Flugbahn im Prinzip durch die Gesetze der Newtonschen Mechanik und den Anfangszustand vorgegeben ist. Um das Ergebnis vorherzusagen, sind allerdings beliebig genaue Sensoren sowie ein sehr schneller, sehr genauer Rechner erforderlich. Diese Art Zufall ist also nicht unberechenbar, sondern vermutlich nur "praktisch unberechenbar", in diesem Sinn also auch "schlechter" Zufall.

Es ist nicht klar, dass es wirklich "guten Zufall" gibt, oder wie "echte" Zufallszahlen erzeugt werden können (quantentheoretische Phänomene könnten letztlich auch deterministisch sein). Für die zufälligen Algorithmen stellt sich deshalb die Frage, ob die schönen theoretischen Eigenschaften auch in einer Welt ohne "guten" Zufall gelten. Die Forschungsergebnisse von Avi Wigderson und vielen Kollegen zeigen jedoch, dass "schlechter" Zufall in "guten" Zufall umgerechnet werden kann. Auch für den Fall einer rein deterministischen Welt hat Wigderson etwas zu berichten: Unter bestimmten komplexitätstheoretischen Annahmen kann man zumindest alle effizienten Algorithmen, die "guten" Zufall erfordern, so umbauen, dass sie trotz Determinismus wie gewünscht funktionieren. Leider bedeutet "effizient" nicht unbedingt "läuft schnell auf echten Computern" und bei dieser Konstruktion kann es durchaus passieren, dass aus einem praktisch sehr guten ein praktisch unbrauchbarer Algorithmus wird. Aber dann können wir einfach an den "guten" Zufall glauben.


Die Lecture im Archiv


7 Responses to “Von gutem und schlechtem Zufall”

  1. Martin Holzherr Reply | Permalink

    Wenn die Arbeit von Avi Wigderson bedeutet, dass es keinen strengen Unterschied zwischen deterministischen und nichtdeterminstischen Systemen gibt, so scheint mir das ein sehr wichtiges Resultat. Denn nicht wenige philosophische Streitgespräche und Standpunkte drehen sich um solche Fragen und könnten somit - falls es einen strengen Unterschied nicht gibt - als letzlich gegenstandslos qualifiziert werden.

    • Benjamin Hiller Reply | Permalink

      @Martin Holzherr: Das Resultat hat m.E. keine direkten philosophischen Konsequenzen. Insbesondere ist es keine Aussage zu Unterschieden zwischen deterministischen und nichtdeterministischen Systemen. Es ist nur eine Aussage über die relative Mächtigkeit bestimmter Klassen von Algorithmen. Es ist möglich, einen beliebigen probabilistischen Polynomialzeitalgorithmus ("effizient") ebenfalls in Polynomialzeit zu simulieren, wenn man statt echten Zufallsbits nur auf schwache Zufallsbits zugreifen kann ("schlechter Zufall"). Wenn es sogenannte Einwegfunktionen gibt, dann gibt es Pseudozufallsgeneratoren. Jeder probabilistische Polynomialzeitalgorithmus ist dann derandomisierbar, d.h. es gibt einen äquivalenten deterministischen Polynomialzeitalgorithmus (mit womöglich deutlich größerer Laufzeit). In diesem Sinn ist es auch in einer rein deterministischen Welt möglich, in Polynomialzeit dieselben Ergebnisse wie in einer Welt mit echtem Zufall zu erzielen.

      Siehe z.B. https://en.wikipedia.org/wiki/One-way_function für einen Einstieg in die Thematik (die deutsche Fassung ist leider nicht so ausführlich).

  2. Dr. Webbaer Reply | Permalink

    Die Forschungsergebnisse von Avi Wigderson und vielen Kollegen zeigen jedoch, dass "schlechter" Zufall in "guten" Zufall umgerechnet werden kann.

    Das dürfte eigentlich nicht gehen bzw. wäre erläuterungsfähig.

    MFG
    Dr. W

    • Benjamin Hiller Reply | Permalink

      Technisch bedeutet "guter" Zufall: gleichverteilte und voneinander unabhängige Zufallsbits. "Schlechter Zufall" heißt nicht gleichverteilte (also "1" ist z.B. wahrscheinlicher als "0", aber die genaue Wahrscheinlichkeit ist nicht bekannt), aber vor allem nicht unabhängige Zufallsbits. Fehlende Unabhängkeit kann z.B. sein, dass nur die Bitmuster "00", "01" und "11" auftreten können: Ist das erste Bit "1", ist es das zweite sicher auch. Es gibt nun mathematische Techniken, wie man aus (vielen) "schlechten" (bzw. fachlich "weak randomness") Zufallsbits (weniger) "gute" Zufallsbits erzeugen kann.

  3. Dr. Webbaer Reply | Permalink

    Da es nicht möglich ist SW-seitig/logisch echte Zufallsgeneratoren zu entwickeln, greift der Rechner für die "Schnittstelle zur Physik" zu, was bspw. die Raumtemperatur oder eine andere Eigenschaft der Welt meinen kann.
    Leistet diese Schnittstelle in diesem Sinne minder, kaputte Sensoren beispielsweise, gleichbleibende externe Werte, kann das ein Algorithmus nicht kompensieren.

    MFG
    Dr. W

    • Benjamin Hiller Reply | Permalink

      Das Interessante an den Forschungsergebnissen ist, dass auch "guter" Zufall konstruiert werden kann, wenn die "Schnittstelle zur Physik" nicht gut genug ist, also zum Beispiel aus der Raumtemperatur oder Zeitdauern zwischen Tastenanschlägen abgeleitete Zufallsbits nicht gleichverteilt und nicht unabhängig sind. Wichtig ist nur, dass der "schlechte" Zufall (Fachterminus: weak randomness) ein Minimum an Zufälligkeit enthält, z.B. dass ein einzelnes Ereignis nicht zu wahrscheinlich ist. Allerdings, und das ist ein sehr starkes Ergebnis, muss man für die "Korrektur" weder die genauen Wahrscheinlichkeiten noch irgendetwas über die Korrelation wissen. Tritt die von Ihnen genannte "Minderleistung" auf, so ist in der Tat die Annahme verletzt, dass überhaupt etwas zufälliges vorliegt.

      Es ist richtig, dass Software allein niemals echten Zufall erzeugen kann. Aber es gibt bekannte Pseudozufallsgeneratoren, die so gute Pseudozufallsbits erzeugen, dass man sie nicht effizient von echten Zufallsbits unterscheiden kann (die Existenz von Einwegfunktionen bzw. P ungleich NP vorausgesetzt). In diesem Sinn sind diese Pseudozufallsbits praktisch genau so gut wie echte Zufallsbits.

      • Dr. Webbaer Reply | Permalink

        @ Herr Hiller:
        Auf jeden Fall eine interessante Sache.
        Bisher hat der Schreiber dieser Zeilen so verstanden, dass "schlechter Zufall" zu "gutem Zufall" komprimiert (im Sinne des Wortes) werden kann.
        Das würde denn so gebucht werden, auch wenn "nicht wirklich" überraschend.

        MFG
        Dr. W

Leave a Reply


nine + = 10