Faire Entscheidungen

Ehrhard Behrends

1. Einleitung

Mal angenommen, zwei Freunde sind völlig unentschlossen, was sie mit dem Abend anfangen sollen: Konzert oder Theater?. Eine Münze zu werfen scheidet aus, denn sie wollen selbst aktiv an der Entscheidung mitwirken, und beide sollen gleichberechtigt beteiligt sein. Sie haben die folgende Idee: Auf Kommando heben beide jeweils eine Hand, wobei ”zufällig” null, eins,..,fünf Finger ausgestreckt werden (der Einfachheit halber wird der Daumen zum Finger erklärt). Es soll dann die Summe gebildet werden; ist sie gerade, geht es ins Konzert, andernfalls ist Theater angesagt.

Erfüllt das Verfahren die Erwartungen? Mathematisch übersetzt ist das doch die Frage, ob X+Y mod 2 gleichverteilt ist, wenn X, Y unabhängige, in {0,…, 5} gleichverteilte Zufallsvariable sind. (Für den Augenblick wollen wir annehmen, daß diese Umschreibung gerechtfertigt ist, wir kommen in Kapitel 4 darauf zurück.)

Die Antwort ist leicht gegeben, man muß nur alle Möglichkeiten, 0 bis 5 Finger zu heben, systematisch zusammenstellen, allen die gleiche Wahrscheinlichkeit (also 1/36) zuordnen und dann sortieren, welche zu einer geraden bzw. ungeraden Summe führen. Da es jeweils 18 Möglichkeiten gibt, sind beide Wahrscheinlichkeiten gleich 0.5, die Freunde können also mit dem Verfahren zufrieden sein.

Bei einer anderen Gelegenheit wollen die beiden auf ähnliche Weise eine faire Entscheidung zwischen drei Alternativen treffen, und das klappt genauso, wenn man nun modulo 3 rechnet. Weitere Verallgemeinerungen bieten sich an, wir formulieren gleich diejenige Fragestellung, von der wir hier ausgehen werden. Gegeben seien natürliche Zahlen k, n und a sowie Wahrscheinlichkeitsmaße P_{1},…, P_{k} auf {0,…, n − 1}. Wir stellen uns die P_{1},… als Verteilungen unabhängiger Zufallsvariablen X_{1},… vor, d. h. P (X_{κ} = ν) = P_{κ}({ν}), und dann fragen wir nach der Verteilung von (X_{1} + ⋯ + X_{k}) mod a, also nach den Zahlen Q({α}) := P ((X_{1} + ⋯ + X_{k}) mod a = α) für α = 0,…, a − 1. In der einleitend gegebenen Interpretation heißt das: k Freunde wollen eine faire Entscheidung zwischen a Alternativen treffen, und sie machen das so, daß sich der κ-te Teilnehmer gemäß P_{κ} für eine Zahl zwischen 0 und n−1 entscheidet, dann werden diese k Zahlen addiert und modulo a ausgewertet.

Es gibt in diesem Zusammenhang einige Fragen, die wir nachstehend behandeln wollen (die Übersetzungen in Probleme zur Freunde-treffen-Ent-scheidungen-Situation sind naheliegend). Problem 1: Angenommen, alle P_{κ} sind die Gleichverteilung auf {0,…, n−1}. Für welche k, a ist dann Q die Gleichverteilung auf {0,…, a − 1}? Problem 2: Kann Q auch dann die Gleichverteilung sein, wenn die P_{κ} nicht gleichverteilt sind? Wie sieht das insbesondere im Fall P_{1} = ⋯ = P_{k} aus? Problem 3: Es sei k = 2, und P_{1} sei vorgegeben. Ist es dann möglich, ein P_{2} so zu finden, daß Q die Gleichverteilung ist? Sind auch mehrere Lösungen denkbar?

Problem 1 kann übrigens – wie im oben besprochenen Spezialfall n = 6, k = a = 2 – in ein kombinatorisches Problem umformuliert werden. Allerdings sehen die dann entstehenden Ausdrücke nur für kleine k, a halbwegs übersichtlich aus, allgemeine Aussagen scheinen so nicht zu gewinnen zu sein. Deswegen werden die Probleme hier ganz anders behandelt, es soll nämlich die Gelegenheit genutzt werden, anhand dieser elementaren Fragestellung einige Ideen der harmonischen Analysis kennenzulernen und anzuwenden. Das wird in Kapitel 2 ausgeführt. Dort wird gleich eine etwas allgemeinere Situation diskutiert, nämlich das Problem der Auswahl im Fall endlicher kommutativer Gruppen (bisher war nur von der ℤ_{n} die Rede). Mit Hilfe der Fouriertransformation können alle aufgeworfenen Probleme vollständig gelöst werden. In Kapitel 3 dann geht es um beliebige endliche Gruppen, dabei werden Darstellungen und deren Fouriertransformation wichtig. Da wir die Theorie nicht voll entwickeln können, beweisen wir die Ergebnisse unter der – im Einzelfall oft leicht nachprüfbaren Voraussetzung – daß es ”genügend viele” Darstellungen gibt. So zeigt sich, daß die unterschiedlichen Phänomene in den Fällen kommutativer bzw. nicht-kommutativer Gruppen durch das unterschiedliche Verhalten von komplexen Zahlen bzw. komplexen Matrizen verursacht werden. Die Arbeit schließt in Kapitel 5 mit einigen Ergänzungen.

Die zum Verständnis benötigte Mathematik ist elementar, außer grundlegenden Kenntnissen über komplexe Zahlen und Matrizen wird nichts vom Leser erwartet.

2. Der Fall endlicher kommutativer Gruppen

Zunächst geben wir eine natürliche Verallgemeinerung der vorstehenden Überlegungen an: Sei G eine endliche, additiv geschriebene abelsche Gruppe. Wir stellen uns das folgende Problem: Von k ”Mitspielern” soll ein Element g aus G so ausgewählt werden, daß alle g die gleiche Wahrscheinlichkeit haben. Das soll so geschehen, daß k Wahrscheinlichkeitsmaße P_{1},…, P_{k} auf G bestimmt werden, und dann werden k Elemente g_{1},…, g_{k} unabhängig so gefunden, daß jeweils g_{κ} wie P_{κ} verteilt ist; anschließend wird g = g_{1} + ⋯ + g_{k} betrachtet. Bezeichne mit Q wieder die zugehörige Summen-Wahrscheinlichkeit, also Q({g}) :=”Wahrscheinlichkeit, daß bei diesem Verfahren g ausgewählt wird” (eine Formel für Q folgt gleich). Wir wollen dann wissen, unter welchen Bedingungen an die P_{κ} man zu Q = U(=Gleichverteilung) kommt.

Dazu rechnen wir zunächst Q aus. Wir beschränken uns auf den Fall von zwei Wahrscheinlichkeitsmaßen P, P̃, eine Formel für k Maße folgt daraus durch Iteration.

Die Wahrscheinlichkeit, daß ein g_{0} speziell als g + g̃ entsteht, ist – Unabhängigkeit der Auswahl vorausgesetzt – P ({g})P̃({g̃}). Nun sind noch die Wahrscheinlichkeiten aller dieser Darstellungsmöglichkeiten zu addieren. Jedes g kann auftreten, und g̃ ist dann gleich g_{0} − g; insgesamt erhalten wir so Q({g_{0}}) = ∑_{g} P ({g})P̃({g_{0} − g}). Statt Q werden wir P ∗ P̃ schrebien und von der Faltung der Wahrscheinlichkeitsmaße P, P̃ sprechen.

Es geht also um Faltungsgleichungen, insbesondere um die Bestimmung von P_{1},…, P_{k} mit P_{1} ∗ ⋯ ∗ P_{k} = U. Und das wollen wir mit Methoden der harmonischen Analysis behandeln, durch die – im hier betrachteten kommutativen Fall – alles in Fragen über komplexe Zahlen transformiert wird.

Zunächst eine Definition: Eine Abbildung χ : G → Γ := {z | z ∈ ℂ, |z| = 1} heißt ein Charakter, wenn stets χ(g + g′) = χ(g)χ(g′) gilt. Wir benötigen die folgenden Eigenschaften von Charakteren:

Lemma 2.1

(i) χ sei ein Charakter, χ sei nicht die Konstante 1. Dann ist ∑_{g} χ(g) = 0.

(ii) Sind χ_{1}, χ_{2} verschiedene Charaktere, so ist ∑_{g} χ_{1}(g)/χ_{2}(g) = 0. (iii) χ_{1},…, χ_{l} seien paarweise verschiedene Charaktere. Dann sind sie

linear unabhängig im ℂ−Vektorraum der Abbildungen von G nach ℂ. Insbesonder kann es höchstens card(G) verschiedene Charaktere geben.

Beweis: (i) Wähle g_{0} mit χ(g_{0}) ≠ 1. Da {g + g_{0} | g ∈ G} mit G übereinstimmt, ist ∑_{g} χ(g) = ∑_{g} χ(g + g_{0}) = χ(g_{0}) ∑_{g} χ(g), also ∑_{g} χ(g) = 0.

(ii) Beachte, daß χ_{1}/χ_{2} Charakter ist. Wende dann (i) an.

(iii) a_{1},…, a_{l} ∈ ℂ seien gegeben, so daß ∑_{λ=1...,l} a_{λ}χ_{λ}(g) = 0 für alle g. Wir teilen die Gleichung durch χ_{λ_{0}}(g) und summieren über g. (ii) ergibt 0 = ∑_{λ} a_{λ}(∑_{g} χ_{λ}(g)/χ_{λ_{0}}(g)) = a_{λ_{0}}card(G). □

Es gibt also stets höchsten card(G) Charaktere. Man kann zeigen, daß diese Zahl immer erreicht wird (für dieses und andere Ergebnisse der harmonischen Analysis vgl. [1],[4],[5]). Der Beweis würde hier zu weit führen, daher werden wir diese Tatsache immer als (eigentlich überflüssige) Extra-Voraussetzung aufnehmen. Bei konkret gegebenem G ist sie in der Regel leicht nachprüfbar. Für die Gruppe ℤ_{n} := ℤ/nℤ, die zur Motivation aus Kapitel 1 gehört, sind offensichtlich χ_{j} : ℤ_{n} → Γ, χ_{j}(l) := exp(2πjl/n)(j = 0,…,n − 1) paarweise verschiedene Charaktere.

Mit Charakteren können Faltungsgleichungen in Skalargleichungen umgeformt werden. Sei dazu P ein Wahrscheinlichkeitsmaß auf G. Wir definieren – für Charaktere χ – die komplexe Zahl P̂(χ) als ∑_{g} P ({g})χ(g) (Achtung: in manchen Büchern wird hier χ̄(g) statt χ(g) eingesetzt).

P̂ ist eine auf der Menge Ĝ der Charaktere definierte komplexwertige Abbildung, die die Fouriertransformation von P genannt wird.

Lemma 2.2 Wir setzen voraus, daß es card(G) paarweise verschiedene Charaktere auf G gibt.

(i) Sind P_{1}, P_{2} Wahrscheinlichkeitsmaße auf G mit P̂_{1} = P̂_{2}, so gilt P_{1} = P_{2}.

(ii) Für Wahrscheinlichkeitsmaße P_{1}, P_{2} ist { \atop P_{1} ∗ P_{2}} = P̂_{1}P̂_{2}.

(iii) Für die Gleichverteilung U gilt Û = δ, wobei δ durch δ(χ) := 1 bzw. := 0 für χ = 1 bzw. χ ≠ 1 erklärt ist.

Beweis: (i) Die lineare Hülle der χ ist nach Voraussetzung und Lemma 2.1(iii) n-dimensional und enthält folglich alle Funktionen von G nach ℂ. Wähle bei vorgegebenem g_{0} eine Linearkombination der Charaktere so, daß die Indikatorfunktion von {g_{0}} entsteht; es soll also ∑_{j} a_{j}χ_{j}(g) = 1 bzw. = 0 sein, wenn g = g_{0} bzw. g ≠ g_{0} ist. Multipliziert man dann die nach Voraussetzung bestehenden Gleichungen ∑_{g} P_{1}({g})χ_{j}(g) = ∑_{g} P_{2}({g})χ_{j}(g) mit a_{j} und summiert auf, so folgt P_{1}({g_{0}}) = ∑_{g} P_{1}({g})(∑_{j} a_{j}χ_{j}(g)) = ∑_{g} P_{2}({g})(∑_{j} a_{j}χ_{j}(g)) = P_{2}({g_{0}}).

(ii) Sei χ ein beliebiger Charakter.

({ \atop P_{1} ∗ P_{2}})(χ) = ∑_{g_{0}}(P_{1} ∗ P_{2})(\{g_{0}\})χ(g_{0})
= ∑_{g_{0}} ∑_{g} P_{1}({g})P_{2}({g_{0} − g})χ(g_{0})
= ∑_{g_{0}} ∑_{g} P_{1}({g})P_{2}({g_{0} − g})χ(g)χ(g_{0} − g)
= (∑_{g} P_{1}({g})χ(g))(∑_{g_{0}} P_{2}({g_{0} − g})χ(g_{0} − g))
= (∑_{g} P_{1}({g})χ(g))(∑_{g_{0}} P_{2}({g_{0}})χ(g_{0}))
= P̂_{1}(χ)P̂_{2}(χ).

(iii) Das folgt sofort aus Lemma 2.1(i). □

Nach diesen Vorbereitungen sind alle Fragen leicht zu beantworten:

Satz 2.3 P und P_{1},…, P_{k} seien Wahrscheinlichkeitsmaße auf einer endlichen kommutativen Gruppe G, für die wir die Existenz von n := card(G) verschiedenen Charakteren voraussetzen.

(i) Ist das k-fache Faltungsprodukt von P mit sich gleich der Gleichverteilung U, so ist notwendig P = U.

(ii) P_{1} ∗ ⋯ ∗ P_{k} = U gilt genau dann, wenn es für jeden von 1 verschiedenen Charakter χ ein κ mit P̂_{κ}(χ) = 0 gibt. Das ist insbesondere dann erfüllt, wenn irgendein P_{κ} gleich U ist.

(iii) Zu P_{1} gibt es ein von U verschiedenes P_{2} mit P_{1} ∗ P_{2} = U genau dann, wenn für ein geeignetes χ ≠ 1 die Fouriertransformation P̂_{1}(χ) verschwindet.

Beweis: (i) Das folgt unter Verwendung von Lemma 2.2 aus der Tatsache, daß sich für komplexe Zahlen z aus z^{k} = 0 stets z = 0 schließen läßt.

(ii) Wieder wird die Aussage auf einfache Eigenschaften von Zahlen zurückgeführt, auch diesmal ist nur wichtig, daß ℂ nullteilerfrei ist.

(iii) Eine Richtung ist klar: Sind alle P̂_{1}(χ) ≠ 0, so gilt nur für P_{2} = U, daß P_{1} ∗ P_{2} = U. Sei nun χ_{0} ≠ 1 ein Charakter mit P̂_{1}(χ_{0}) = 0. P̂_{1} verschwindet dann auch auf (χ_{0})^{−1} = \overline{χ_{0}}, da die P_{1}(\{g\}) reell sind.

Ein Maß P_{2} soll durch P_{2}(\{g\}) := 1/n + ϵ(χ_{0} + \overline{χ_{0}})(g) erklärt werden, dabei wählen wir ϵ > 0 so, daß diese Zahlen nichtnegativ sind.

Wegen Lemma 2.1(i) ist P_{2} wirklich ein Wahrscheinlichkeitsmaß, und der zweite Teil dieses Lemmas garantiert, daß P̂_{2}(χ) = 0 für χ ≠ χ_{0}, \overline{χ_{0}}, 1. Andererseits gilt P̂_{2}(χ_{0}) ≠ 0, also ist P_{2} ≠ U, P̂_{1}P̂_{2} = δ, und so ein P_{2} sollte konstruiert werden. □

Für das Ausgangsproblem, zunächst im Fall n = a formuliert, heißt das:

• Soll eine faire Entscheidung zwischen n Alternativen von k Personen dadurch herbeigeführt werden, daß alle gemäß einer festen Verteilung P ein Element in {0,…, n−1} wählen und dann die Summe modulo n bilden, so führt dieses Verfahren zur Gleichverteilung auf {0,…, n−1} genau dann, wenn P selbst die Gleichverteilung war.

• Sind unterschiedliche Verteilungen P_{1},…, P_{k} zugelassen, so wird das Verfahren alle n Alternativen mit gleicher Wahrscheinlichkeit genau dann liefern, wenn es zu jeder von 1 verschiedenen n−ten Einheitswurzel ξ_{j} := exp(2πij/n), j = 1,…, n−1, ein κ mit ∑_{l=0,...,n−1} P_{κ}({l})(ξ_{j})^{l} = 0 gibt.

• Sind zwei Personen beteiligt und entscheidet sich die erste für P_{1}, so kann die zweite durch die Wahl P_{2} = U immer erreichen, daß das Verfahren insgesamt fair wird. Andere Wahlen für P_{2} sind genau dann möglich, wenn ∑_{l=0,...,n−1} P_{1}({l})(ξ_{j})^{l} = 0 für ein j ∈ {1,…, n − 1}.

[Ein Beispiel für n = 6: Ordnet P_{1} den Zahlen 0,…, 5 die Wahrscheinlichkeiten 0, 0.2, 0.3, 0, 0.2, 0.3 zu, so verschwindet die Fouriertransformation für j = 1, 3, 5, und folglich existieren von U verschiedene P_{2} mit P_{1} ∗ P_{2} = U (z. B. das P_{2}, das 0,…, 5 auf 1/3, 0, 1/3, 0, 1/3, 0 abbildet, es entspricht der Konstruktion aus dem Beweis mit ϵ = 1/12, χ = ”der zu j = 3 gehörige Charakter”). Ist dagegen P_{1} z. B. die Punktmasse auf 0, so gibt es außer P_{2} = U keinen Kandidaten.]

Es fehlt noch eine Ergänzung für den Fall a ≠ n. Beachtet man, daß (X_{1} + ⋯ + X_{k}) mod a = ((X_{1} mod a) + ⋯ + (X_{k} mod a)) mod a, so hat man nur die vorstehenden Überlegungen auf die X_{κ} mod a anzuwenden. Offensichtlich ist auch, daß für ein auf {0,…, n − 1} gleichverteiltes X die Variable X mod a auf {0,…, a − 1} genau dann gleichverteilt ist, wenn a die Zahl n teilt. Sind also alle P_{κ} die Gleichverteilung, so ist a|n notwendig und hinreichend dafür, daß alle Alternativen bei der Auswahl die gleichen Chancen haben. (Deswegen klappte es mit a = 2 und a = 3 am Anfang, da war nämlich n = 6.)

Hier haben wir uns um die elementar zugänglichen Aspekte im Zusammenhang mit der Gleichverteilung und Faltungen gekümmert. Es sollte jedoch erwähnt werden, daß man eine naheliegende Verallgemeinerung für beliebige kompakte kommutative Gruppen G betrachten kann. Der Kandidat für die Gleichverteilung ist da das Haarsche Maß U, das eindeutig bestimmte Wahrscheinlichkeitsmaß mit U(A) = U(A + x) (alle x ∈ G, A ⊂ G Borelmenge). Auch hier läßt sich eine Faltung P_{1} ∗ P_{2} von Wahrscheinlichkeitsmaßen P_{1}, P_{2} definieren, und P_{1} ∗P_{2} entspricht wieder der Verteilung von g_{1} + g_{2}, wenn g_{1}, g_{2} gemäß P_{1} bzw. P_{2} ausgewählt wurden.

Fragen des Typs ”P_{1} ∗ P_{2} = U?” können wieder mit Hilfe von Charakteren χ behandelt werden, das sind stetige Abbildungen von G nach Γ mit χ(g_{1} + g_{2}) = χ(g_{1})χ(g_{2}). Die Ergebnisse sind fast wörtlich so wie im hier besprochenen endlichen Fall, insbesondere liefert P ∗⋯∗P nur dann U, wenn P selbst schon U war. Die Beweise verlangen auch keine neuen Ideen; der technische Aufwand ist allerdings erheblich höher, da Integrale statt Summen zu betrachten sind und die auftretenden Funktionenräume unendlich-dimensional werden.

Als Beispiel für eine Interpretation unter dem Aspekt ”Entscheidungen” stelle man sich k Personen vor, die sich mit Hilfe eines fairen Zufallsverfahrens auf eine Zeigerstellung (etwa eine Himmelsrichtung) einigen wollen. Jeder sucht sich eine aus, und am Ende wird die Hintereinanderausführung betrachtet. Das führt auf G = Γ, und U ist hier das normalisierte Borel-Lebesgue-Maß. Für diese Gruppe sind die Charaktere wieder leicht zu berechnen – es sind genau die Abbildungen z ↦ z^{m} mit m ∈ ℤ –, und folglich kann man Probleme im Zusammenhang mit Entscheidungen genauso explizit lösen wie eben im Fall der ℤ_{n}.

3. Der Fall beliebiger endlicher Gruppen

Erwartungsgemäß wird alles schwieriger, wenn wir nun auch nichtkommutative endliche Gruppen zulassen. Es soll herausgearbeitet werden, daß für die hier interessierenden Aspekte die neu auftretenden Probleme durch das unterschiedliche Verhalten von Zahlen und Matrizen verursacht werden.

Ab hier sei (G, ∘) eine beliebige endliche Gruppe. Wieder können wir versuchen, gleichverteilt in G dadurch etwas auszusuchen, daß g_{1},…, g_{k} gemäß P_{1},…, P_{k} gewählt werden und dann g_{1} ∘ ⋯ ∘ g_{k} betrachtet wird.

Konkretes Beispiel: Eine ”zufällige” Sitzordnung beim Skat soll durch zwei Spielleiter festgelegt werden, die sich nach persönlichen Zufallsmechanismen für jeweils eine Permutation von 1, 2, 3 entscheiden; dann wird die Hintereinanderausführung dieser Permutationen gebildet.

Klar, daß die oben gestellten Fragen hier genauso sinnvoll aufgeworfen werden können, wie sieht es aber mit den Antworten aus?

Wieder sei U die Gleichverteilung auf G, wieder ist leicht zu berechnen, wie für Wahrscheinlichkeitsmaße P_{1}, P_{2} die Verteilung der Summe aussieht, wenn wir wie üblich Unabhängigkeit der Auswahl voraussetzen. Das zugehörige Maß wird auch hier mit P_{1} ∗ P_{2} bezeichnet, und man bestimmt seine Werte durch die Formel P_{1} ∗P_{2}({g_{0}}) = ∑_{g_{1}∘g_{2}=g_{0}} P_{1}({g_{1}})P_{2}({g_{2}}) = ∑_{g} P_{1}({g_{0} ∘ g^{−1}})P_{2}({g}).

Leider kann man nun nicht Faltungsgleichungen unter Verwendung von Charakteren in Skalargleichungen überführen, denn man kann nicht garantieren, daß es auf G ”genügend viele” Charaktere gibt. (Das ist auch nicht zu erwarten, denn ein Charakter kann nicht zwischen den – möglicherweise verschiedenen - Elementen g_{1} ∘ g_{2} und g_{2} ∘ g_{1} unterscheiden.) Es hilft aber eine neue Idee weiter:

Eine d-dimensionale Darstellung M von G ist eine Abbildung, die jedem g ∈ G eine unitäre d×d-Matrix M_{g} zuordnet, so daß stets M_{g_{1}∘g_{2}} = M_{g_{1}}M_{g_{2}} gilt (Matrizenprodukt). Schreibt man M_{g} = (f_{s,t}(g))_{s,t=1,...,d}, so heißen die f_{s,t} : G → ℂ die Koeffizientenfunktionen zu M.

Wieder wird es wichtig sein, daß ”genügend viele” Darstellungen existieren. Das ist immer erfüllt (vgl. die angegebene Literatur zur harmonischen Analysis), wir wollen es aber als Extra-Voraussetzung formulieren und im konkreten Einzelfall nachprüfen, um den Lesern einen langen technischen Exkurs zu ersparen. Wir werden voraussetzen, daß es Darstellungen M^{1},…, M^{m} mit den folgenden Eigenschaften gibt^{1}:

• Mit d_{μ}=”die Dimension von M^{μ}” gilt d_{1}^{2} + ⋯ + d_{m}^{2} = n := card(G).

• M^{1} ist die triviale Darstellung (d_{1} = 1, f_{1,1}(g) = 1 für alle g).

• Bezeichnet (f_{s,t}^{μ})_{s,t=1,...,d_{μ}} die Koordinatenfunktionen von M^{μ}, so sollen diese n Funktionen paarweise orthogonal im folgenden Sinn sein: 1/n ∑_{g} f_{s,t}^{μ}f_{s′t′}^{μ′}(g) ist immer Null, außer im Fall s = s′, t = t′, μ = μ′; dann soll die Summe 1/d_{μ} sein.

Wir definieren auch hier eine Fouriertransformation für Wahrscheinlichkeitsmaße P: Das ist diejenige Abbildung, die einer Darstellung M die Matrix P̂(M) := ∑_{g} P ({g})M_{g} zuordnet.

Lemma 3.1 Für Wahrscheinlichkeitsmaße P_{1}, P_{2} gilt:

(i) Aus P̂_{1}(M^{μ}) = P̂_{2}(M^{μ}) für μ = 1,…, m folgt P_{1} = P_{2}. (ii) Für alle Darstellungen M ist { \atop P_{1} ∗ P_{2}}(M) = P̂_{1}(M)P̂_{2}(M). (iii) Û(M^{1}) = 1, alle anderen Û(M^{μ}) verschwinden.

Beweis: Das geht genauso wie in Kapitel 2. Es ist nur wichtig, daß – als Folgerung aus den Orthogonalitätsrelationen – jede komplexwertige Funktion auf G Linearkombination der f_{st}^{μ} ist. □

Für die hier interessierenden Faltungsgleichungen ergibt sich sofort:

Satz 3.2 Genau dann ist P_{1} ∗ ⋯ ∗ P_{k} die Gleichverteilung, wenn alle Matrizenprodukte [P̂_{1}(M^{μ})] ⋯ [P̂_{k}(M^{μ})] für μ = 2,…, m die Nullmatrix sind.

Anders als für Zahlen kann man aber für Matrizen A, B aus AB = 0 nicht schließen, daß A = 0 oder B = 0, und deswegen ist nicht klar, ob wir ähnliche Folgerungen ziehen können wie im kommutativen Fall, ob es also zum Beispiel ein Analogon zu Satz 2.3(i) gibt. Positive Ergebnisse kann man erzwingen, indem man durch Forderungen an P garantiert, daß [P̂(M)]^{k} = 0 nur für P̂(M) = 0 gilt.

Das ist zum Beispiel dann der Fall, wenn P symmetrisch ist, d. h. wenn P ({g}) = P ({g^{−1}}) für alle g ist. Denn da alle M_{g} unitär sind, ist M_{(g^{−1})} = (M_{g})^{∗}(=die zu M_{g} adjungierte Matrix). Im Falle symmetrischer P ist dann (P̂(M))^{∗} = ∑_{g} P ({g})M_{g}^{∗} = ∑_{g} P ({g})M_{(g^{−1})} = ∑_{g} P ({g^{−1}})M_{(g^{−1})} = P̂(M), d. h. die hier interessierenden P̂(M^{μ}) sind selbstadjungiert, und für derartige Matrizen A darf man wirklich aus A^{k} = 0 auf A = 0 schließen. Das zeigt:

1Das ist die angemessene Verallgemeinerung der Reichhaltigkeitsforderung im kommutativen Fall; dort hatten wir ”viele” Charaktere, d. h. eindimensionale Darstellungen postuliert.

Korollar 3.3 Die üblichen Voraussetzungen seien erfüllt, zusätzlich sei P ein symmetrisches Wahrscheinlichkeitsmaß auf G. Ist dann P ∗ ⋯ ∗ P (kfaches Faltungsprodukt) gleich U, so folgt P = U.

Damit ist der allgemeine Fall noch nicht entschieden. Die folgenden Beispiele zeigen aber, daß für nichtkommutative G alles Mögliche passieren kann.

Satz 3.4 Es gibt nichtkommutative Gruppen G_{1}, G_{2} mit genügend vielen Darstellungen im oben präzisierten Sinn, so daß

(i) Auf G_{1} gibt es ein Wahrscheinlichkeitsmaß P ≠ U mit P ∗ P = U. (ii) In G_{2} folgt aus P ∗ P = U stets P = U.

Beweis: (i) Sei G_{1} := S_{3}, die Gruppe der Permutationen von drei Elementen. Die sechs Elemente von G_{1} kürzen wir wie folgt ab: 0 := ({1 \atop 1} {2 \atop 2} {3 \atop 3}) , 1 := ({1 \atop 3} {2 \atop 1} {3 \atop 2}) , 2 := ({1 \atop 2} {2 \atop 3} {3 \atop 1}) , 3 := ({1 \atop 1} {2 \atop 3} {3 \atop 2}) , 4 := ({1 \atop 3} {2 \atop 2} {3 \atop 1}) , 5 := ({1 \atop 2} {2 \atop 1} {3 \atop 3}) .

Wir geben explizit die geforderten Darstellungen an: Die ersten beiden sind eindimensional, die dritte ist zweidimensional. Hier die Werte der Funktionen f_{s,t}^{μ} (dabei steht w für \sqrt{3/4}):

\begin{matrix}g : & 0 & 1 & 2 & 3 & 4 & 5 \\ f_{11}^{1} & 1 & 1 & 1 & 1 & 1 & 1 \\ f_{11}^{2} & 1 & 1 & 1 & −1 & −1 & −1 \\ f_{11}^{3} & 1 & −0.5 & −0.5 & −1 & 0.5 & 0.5 \\ f_{12}^{3} & 0 & −w & w & 0 & −w & w \\ f_{21}^{3} & 0 & w & −w & 0 & −w & w \\ f_{22}^{3} & 1 & −0.5 & −0.5 & 1 & −0.5 & −0.5 \end{matrix}

Wir definieren noch P durch 2P ({0}) = 2P ({4}) = P ({2}) = P ({5}) = 1/3. Eine kanonische Rechnung zeigt, daß die f_{st}^{μ} zu Darstellungen gehören, daß die Orthogonalitätsrelationen erfüllt sind und daß P ∗ P = U. (Zur Kontrolle berechnen wir P̂(M^{3}) = (1/12) ({3 \atop −2w} {6w \atop −3}), und das ist wirklich eine nilpotente nichttriviale Matrix.)

(ii) G_{2} sei die Quaternionengruppe. Die besteht aus den acht Elementen ±1, ±i, ±j, ±k, für die die Gruppenstruktur durch i^{2} = j^{2} = k^{2} = −1, ij = k, jk = i, ki = j, ji = −k, kj = −i, ik = −j erklärt ist (die Rechenregeln für ±1 und ± sollen so sein, wie man es von komplexen Zahlen gewohnt ist; z. B. ist k(−i) = −ki = −j).

Auf G_{2} gibt es neben dem trivialen Charakter χ_{1} noch drei weitere Charaktere, die hier mit χ_{i}, χ_{j}, χ_{k} bezeichnet werden. Sie sind durch χ_{i} : ±1, ±i ↦ 1, ±j, ±k ↦ −1, χ_{j} : ±1, ±j ↦ 1, ±k, ±i ↦ −1, χ_{k} : ±1, ±k ↦ 1, ±i, ±j ↦ −1 definiert. Und dann gibt es noch eine zweidimensionale Darstellung M. Die ist durch

±1 ↦ ±E, ±i ↦ ±I, ±j ↦ ±J, ±k ↦ ±K

erklärt, wobei E, I, J, K die folgenden Matrizen bezeichnen:

E = ({1 \atop 0} {0 \atop 1}) , I = \frac{\sqrt{2}}{2} ({i \atop i} {i \atop −i}) , J = ({0 \atop −1} {1 \atop 0}) , K = \frac{\sqrt{2}}{2} ({−i \atop i} {i \atop i}) .

(Das ”i” in diesen Matrizen ist die übliche imaginäre Einheit, die auf den ersten Blick mit dem i ∈ G_{2} nichts zu tun hat. Es besteht aber ein Zusammenhang: Die Quaternionengruppe erzeugt die Quaternionen, die ℂ umfassen.)

Damit ist, auch wenn wir die elementaren Rechnungen hier nicht ausführen werden, die Existenz genügend vieler Darstellungen nachgewiesen.

Sei nun P ein Wahrscheinlichkeitsmaß auf G_{2} mit P ∗P = U; es ist P = U zu zeigen. Dazu setzen wir τ_{α} := P ({α}) + P ({−α}) für α = 1, i, j, k. Da P ein Wahrscheinlichkeitsmaß ist und da nach Satz 3.2 die (P̂(χ_{α}))^{2} und folglich die P̂(χ_{α}) für α = i, j, k verschwinden, folgt τ_{1} + τ_{i} + τ_{j} + τ_{k} = 1, τ_{1} + τ_{i} − τ_{j} − τ_{k} = 0, τ_{1} − τ_{i} + τ_{j} − τ_{k} = 0, τ_{1} − τ_{i} − τ_{j} + τ_{k} = 0, und dieses Gleichungssystem hat als eindeutig bestimmte Lösung τ_{1} = τ_{i} = τ_{j} = τ_{k} = 1/4. Wir schreiben daher – mit geeigneten δ_{1}, δ_{i}, δ_{j}, δ_{k} – P ({α}) = 1/8 + δ_{α}, P ({−α}) = 1/8 − δ_{α}.

Werte nun die Identität P ∗ P = U bei 1 aus:

1/8 = (1/8 + δ_{1})^{2} + (1/8 − δ_{1})^{2} + 2 ∑_{α=i,j,k}(1/8 + δ_{α})(−1/8 − δ_{α}),

also 0 = (δ_{1})^{2} − (δ_{i})^{2} − (δ_{j})^{2} − (δ_{k})^{2}. Analog ergibt die Auswertung bei i, j, k die weiteren Gleichungen 0 = δ_{1}δ_{i} = δ_{1}δ_{j} = δ_{1}δ_{k}. Diese Beziehungen implizieren δ_{1} = δ_{i} = δ_{j} = δ_{k} = 0, und das war zu zeigen. □

Die genaue Antwort auf die Frage, ob sich eine Gruppe wie in (i) oder wie in (ii) des vorigen Satzes verhält, wurde in [2] gegeben (s. a. [6]): Für ein nichtkommutatives kompaktes G kann man genau dann stets von P ∗P = U auf P = U schließen, wenn G ein Produkt aus der Quaternionengruppe und einer Gruppe des Typs {0, 1}^{I}, (I irgendeine Menge) ist. Die hier bereitgestellten elementaren Methoden reichen aber bei weitem nicht aus, um diesen Charakterisierungssatz zu beweisen.

4. Ergänzungen

Die vorstehenden Kapitel haben uns von einem konkreten Entscheidungsfindungs-Problem bis in die harmonische Analysis nichtkommutativer Gruppen geführt. Die am Anfang aufgeworfenen Fragen konnten vollständig geklärt werden, sogar dann, wenn man die zur Motivation gehörige Gruppe ℤ_{n} durch ein beliebiges kommutatives endliches (oder sogar kompaktes) G ersetzt. Im nichtkommutativen Fall liegen nach der allgemeinen Charakterisierung aus [2] sofort einige Fragen nahe, z. B.: Wann impliziert U = P ∗ ⋯ ∗ P (kfaches Faltungsprodukt), daß P = U? Welche Zusatzeigenschaften an P garantieren, daß P = U aus P ∗ P = U folgt?

Auch im kommutaiven Fall, selbst für die ℤ_{n}, ergeben sich durch Variation der Ausgangssituation schnell noch offene Probleme. Wir denken wieder an die Freunde vom Anfang, die gemeinsam dadurch eine Entscheidung zwischen n Alternativen treffen wollen, daß jeder etwas aus {0,…, n − 1} auswählt und dann die Summe modulo n als gemeinsame Entscheidung akzeptiert wird. Diesmal wird aber gewünscht, daß die Ergebnisse entsprechend einem vorher vereinbarten Wahrscheinlichkeitsmaß P_{0} gefunden werden. In unserer Terminologie heißt das: Diskutiere P_{1} ∗ P_{2} = P_{0} bei vorgelegtem P_{0}. Findet man z. B. zu jedem P_{0} ein P mit P ∗ P = P_{0} (das entspricht dem Fall, daß beide Freunde das gleiche Entscheidungsverfahren verwenden)? Für kleine n kann man das noch leicht diskutieren. Sei etwa n = 2. P_{0} sei gegeben, und wir fragen nach Zahlen p, q ≥ 0 (unseren Kandidaten für P ({0}), P ({1})) mit p + q = 1, p^{2} + q^{2} = P_{0}({0}), 2pq = P_{0}({1}). Die ersten beiden Bedingungen implizieren die dritte (denn P_{0} ist ein Wahrscheinlichkeitsmaß), und die Lösung kann geometrisch leicht gefunden werden: Es geht um die Schnittpunkte der Geraden p + q = 1 mit dem Kreis p^{2} + q^{2} = P_{0}({0}). Es zeigt sich etwa, daß es Lösungen genau dann gibt, wenn P ({0}) ≥ 1/2 ist.

Für beliebige n scheint keine einfache Charakterisierung der P_{0}, zu denen es P mit P ∗ P = P_{0} gibt, möglich zu sein. Nur soviel läßt sich sagen: P ∗P = P_{0} gilt genau dann, wenn (P̂(χ_{j})^{2} = P̂_{0}(χ_{j}) für j = 1,…, n−1. Das macht klar, daß das Problem mit den Wurzeln der P̂_{0}(χ_{j}) zusammenhängt, und man sieht auch, warum der oben diskutierte Fall P_{0} = U zu einem einfach zu behandelnden Problem führt (da sind nämlich alle diese Zahlen Null).

Noch verwickelter ist in diesem Zusammenhang die folgende Fragestellung, die im Fall P_{0} = U in Kapitel 2 vollständig diskutiert wurde: Gibt es zu P_{1}, P_{0} ein P_{2} mit P_{1} ∗ P_{2} = P_{0}? Eine Umformulierung mit Hilfe von Charakteren führt auf P̂_{1}(χ)P̂_{2}(χ) = P̂_{0}(χ), und das impliziert die notwendige Bedingung |P̂_{1}(χ)| ≤ |P̂_{0}(χ)| für alle χ (da |P̂(χ)| ≤ 1). Daher werden die Zahlen α_{j} := P̂_{0}(χ_{j})/P̂_{1}(χ_{j}) eine Rolle spielen (wir wollen der Einfachheit halber annehmen, daß alle P̂_{1}(χ_{j}) ≠ 0 sind), und dann steht man vor dem Problem zu entscheiden, ob die α_{j} als P̂(χ_{j}) für ein geeignetes Wahrscheinlichkeitsmaß P realisiert werden können. Das ist der schwierige Teil, nur für kleine n bieten sich Charakterisierungen an.

Sei z. B. n = 3. Für welche α_{1}, α_{2} gibt es p_{0}, p_{1}, p_{2} ≥ 0 (die Kandidaten für die Wahrscheinlichkeiten von 0, 1, 2) mit p_{0} +p_{1} +p_{2} = 1, p_{0} +p_{1}ξ + p_{2}ξ̄ = α_{1}, p_{0} + p_{1}ξ̄+ p_{2}ξ = α_{2} (mit ξ := exp(2πi/3))? Es muß α_{1} = \overline{α_{2}} sein, und α_{1} muß in der konvexen Hülle C von 1, ξ, ξ̄ liegen. Für das Ausgangsproblem heißt das: Genau dann ist P_{1} ∗ P_{2} = P_{0} für ein geeignetes P_{2}, wenn P̂_{0}(χ_{1})/P̂_{1}(χ_{1}) in C liegt.

Wir kommen noch einmal auf den Beginn der Arbeit zurück: Faire Entscheidungen durch Fingerheben^{2}. Nachträglich wird klar, warum der Daumen als Finger wichtig war. Läßt man ihn nämlich weg, so geht man von n = 6 zu n = 5 über, und dann sind die Summen modulo 2 nicht meht gleichverteilt. Es sind noch zwei weitere Punkte zu besprechen. Zum einen ist es nicht so, daß man 0 oder 1,…, 5 Finger (der Daumen zählt wieder mit) gleichverteilt hebt, wenn man sich einbildet, das zu tun. Ungerade Zahlen haben eine höhere Wahrscheinlichkeit als gerade, wohl deswegen, weil 1, 3, 5 Finger leichter zu strecken sind als 2 oder 4. Damit taucht ”Summe gerade” öfter auf als ”Summe ungerade”, auch wenn beide Teilnehmer um eine gleichverteilte Entscheidung bemüht sind.

2Das ist übrigens, glaubt man [3], Seite 69, ein gängiges Entscheidungsverfahren unter Kindern.

Und ganz schwierig wird es, wenn man dieser Frage unabhängig von der Physiologie der Finger auf den Grund gehen möchte: Kann ein Mensch überhaupt zufällig reagieren, kann er etwa ohne Hilfsmittel eine faire Münze simulieren? Mir sind nur ziemlich gekünstelte Lösungen eingefallen, jeder ist herzlich eingeladen, sich eigene Verfahren auszudenken.

Literaturhinweise

[1] P. Diaconis. Group representations in probability and statistics. IMS - Lecture Notes-Monograph Series 11 (1988).

[2] P. Diaconis, M. Shashshahani. On square roots of the uniform distribution on compact groups. Proc. of the AMS 98 (1986),341-348 .

[3] I. Ekeland. The broken dice. University of Chicago Press (1993).

[4] E. Hewitt, K. A. Ross. Abstract harmonic analysis I,II. Springer Verlag, Berlin-Heidelberg-New York (1963).

[5] W. Schempp, B. Dreseler. Einführung in die harmonische Analyse. Teubner-Verlag, Stuttgart (1980).

[6] G. Turnwald. Roots of Haar measure and topological hamiltonian groups. Springer Verlag, Lecture Notes in Mathematics 1379 (1989),364-375.

I. Mathematisches Institut, Freie Universität Berlin, Arnimallee 2–6, D-14 195 Berlin, Germany; e-mail: behrends@math.fu-berlin.de