Zwei Umschläge

          Die Lösung steht im unteren Teil der Seite.

Hier kommt eine Variante des Two Envelopes Paradox (auf Deutsch manchmal mit Umtauschparadoxon übersetzt). Allen Versionen dieses Problems (das in Wahrheit kein Paradoxon ist) liegt zugrunde, dass Spieler  A  zwei verschiedene Geldbeträge in zwei (danach verschlossene) gleiche Umschläge steckt, Spieler  B  einen der beiden Umschläge öffnet und dann entscheiden kann, ob er den darin enthaltenen Betrag behält oder statt dessen den Inhalt des anderen Umschlags wählt (ohne ihn gesehen zu haben).

Im Kongress-Magazin des ICM 2018 wurde eine spezielle Variante des Two Envelopes Paradox diskutiert, in der nur  A  ein wirklicher "Spieler" ist (also auswählen darf, welche Beträge er in die Umschläge füllt), während  B  eine Strategie für "Behalten oder Tauschen" durch einen Zufallsalgorithmus vorgegeben wird, der auch  A  bekannt ist. Da dieses Problem seinen Fokus auf das Verhalten von  A  legt, entspricht es nicht dem klassischen Two Envelopes Paradox, in welchem es vor allem auf die optimale Strategie des Spielers  B  ankommt.  -  Hier soll nun das Problem vom ICM "umgedreht" werden:  A  spielt eine passivere Rolle,  B  kann entscheiden.

Nun zunächst zu den Randbedingungen, wie sie im ICM-Magazin beschrieben wurden. Die beiden Umschläge enthalten die ganzzahligen Beträge  i  und  j ,  o.E.  i < j ,  mit  i, j ∈ {0, 1, ..., n}, n ∈ N .  n  ist fest gewählt und beiden Spielern vorab bekannt.  -  Die Strategie für  B  wird  -  wie üblich beim Two Envelopes Paradox  -  durch eine Schwelle  x  bestimmt. Er tauscht die Umschläge genau dann, wenn er im ersten Umschlag einen Betrag  ≤ x  findet.

Bis hierhin folgen wir dem ICM-Problem. Dort geht es so weiter:  B  wählt  x  zufällig und mit gleicher Wahrscheinlichkeit aus den halbzahligen Werten  1/2, 3/2, ..., n - 1/2  aus.  A  kennt diese (Zufalls-)Strategie.  B  erzielt den höheren Betrag  j  mit Wahrscheinlichkeit  p > 1/2 .  Für  A  gibt es eine optimale Strategie zur Minimierung von  p ,  nämlich  j = i+1 .  Soweit zum ICM-Problem (hier in verkürzter Form). Wir werden im Folgenden einem anderen Ansatz folgen.

Die Zufälligkeit soll jetzt mit der Wahl von (i,j) durch  A  ins Spiel kommen.  A  wählt mit gleicher Wahrscheinlichkeit ein Paar (i,j) aus den  n(n+1)/2  Möglichkeiten aus.  B  dagegen ist frei in der Wahl von  x ∈ {1/2, 3/2, ..., n - 1/2}.


Aufgabe 1

Die Wahrscheinlichkeit  p ,  den höheren Betrag  j  zu erzielen, wurde bereits bei der ICM-Variante eingeführt. Berechnen Sie  p  in Abhängigkeit von  x .


Aufgabe 2

Berechnen Sie die optimale Schwelle  x_opt ,  mit der  B  für  p  aus Aufgabe 1 den maximalen Wert  p_max  erzielt.  -  Bei der Gelegenheit können Sie auch noch  p_min  berechnen.


Aufgabe 3

Berechnen Sie den Erwartungswert  E  für die Auszahlung an  B  in Abhängigkeit von  x .


Aufgabe 4

Berechnen Sie die optimale Schwelle  x'_opt ,  mit der  B  für den Ertrag  E  aus Aufgabe 3 den maximalen Wert  E_max  erzielt.  -  Bei der Gelegenheit können Sie auch noch  E_min  berechnen.


Aufgabe 5

Zeigen Sie, dass es für große  n  bei der Wahl der Schwelle "nicht so genau darauf ankommt": Wenn nämlich  B  in den Aufgaben 2 und 4 statt der optimalen Schwelle eine Schwelle  x_opt ± h  bzw.  x'_opt ± h  mit festem  h ∈ N  wählt (was natürlich nur für genügend große  n  einen Sinn ergibt), so ändern sich die Grenzwerte (mit wachsendem  n ) in den Aufgaben 2 und 4 nicht.

Lösung

Zur Vereinfachung soll im Folgenden (i,j) sowohl für das Zahlenpaar als auch für das offene reelle Intervall stehen können.

⌈x⌉ steht für ganzzahliges Aufrunden, ⌊x⌋ für ganzzahliges Abrunden.


Aufgabe 1

Berechnen Sie die Wahrscheinlichkeit  p ,  den höheren Betrag  j  zu erzielen, in Abhängigkeit von  x .

Es gibt  n(n+1)/2  Möglichkeiten für die Paare (i,j). Für  i  gibt es  ⌈x⌉ (= x + 1/2)  und für  j  gibt es  n+1-⌈x⌉  Möglichkeiten. Insgesamt überdecken also  ⌈x⌉(n+1-⌈x⌉) Intervalle (i,j) ein vorgegebenes  x .

Wir wollen mit  q  die Wahrscheinlichkeit bezeichnen, dass  x  zwischen  i  und  j  liegt. In diesem Fall erzielt  B  den höheren Betrag  j  mit Wahrscheinlichkeit  1 ,  in allen anderen Fällen mit Wahrscheinlichkeit  1/2 .  Also gilt:

p = q +(1-q)/2 = 1/2 + q/2   mit   q = 2⌈x⌉(n+1-⌈x⌉)/(n²+n)

p = 1/2 + ⌈x⌉(n-⌊x⌋)/(n²+n)

Beispiel :  n = 10, x = 7,5  ⇒  p ≈ 0,7182


Aufgabe 2

Berechnen Sie die optimale Schwelle  x_opt ,  mit der  B  für  p  aus Aufgabe 1 den maximalen Wert  p_max  erzielt.  -  Bei der Gelegenheit können Sie auch noch  p_min  berechnen.

Für  B  ist es offenbar günstig, wenn  x  durch möglichst viele Intervalle (i,j) überdeckt wird. Man kann also vermuten, dass  x_opt  möglichst mittig im Intervall  (0,n)  liegen muss, um  p  zu maximieren.

Es genügt, statt  p  die Funktion  y = ⌈x⌉(n-⌊x⌋) = (x+1/2)(n+1/2-x) zu betrachten. Diese Funktion beschreibt eine konkave Parabel mit den Nullstellen  -1/2  und  n+1/2 .  Das Maximum der Parabel liegt mittig dazwischen, also bei  n/2 .  Da  x  halbzahlig sein soll, erhalten wir:

x_opt = n/2   für  n  ungerade
x_opt1 =(n-1)/2   oder   x_opt2 =(n+1)/2   für  n  gerade

Die anfängliche Vermutung erweist sich somit als richtig.

y(x_opt) = (n+1)²/4    für  n  ungerade
y(x_opt) = n(n+2)/4    für  n  gerade

Daraus ergibt sich

p_max = 3/4 + 1/(4n)   für  n  ungerade

p_max = 3/4 + 1/(4(n+1))   für  n  gerade

Mit wachsendem  n  hat  p_max  den Grenzwert  3/4 .  B  erzielt den höheren Betrag in mehr als  75 %  aller Spiele.

Wegen der parabolischen Abhängigkeit erhält man  p_min  für  x = 1/2  und  x = n - 1/2 .

p_min = 1/2 + 1/(n+1)


Aufgabe 3

Berechnen Sie den Erwartungswert  E  für die Auszahlung an  B  in Abhängigkeit von  x .

Wir wählen den folgenden Lösungsweg: Zunächst rechnen wir die durchschnittliche Auszahlung für den Fall der vollständigen Zufälligkeit aus; d.h.  B  setzt sich keine Schwelle  x  und entscheidet sich rein zufällig für einen der beiden Umschläge. (Es wird uns nicht überraschen, dass dieser Durchschnitt gleich  n/2  ist.) Danach schauen wir uns diejenigen Fälle an, in denen  B  durch die Setzung der Schwelle eine höhere Auszahlung erzielt, was dann auch zu einem höheren Gesamtdurchschnitt führt.

Bei reiner Zufälligkeit für die Wahl der Umschläge hat  B  im Mittel (i+j)/2  für die Auszahlung zu erwarten. Betrachtet man zunächst nur die Paare (i,j) mit  j-i = m ,  mit festem  m ∈ {1,...,n},  so ist die durchschnittliche Auszahlung  i+m/2 .  Es gibt  n-m+1  solcher Paare; damit erhält man:

Durchschnittliche Auszahlung bei Zufallsauswahl :
Σ_i=0..n-m(i+m/2)/(n-m+1) = ((n-m+1)(n-m)/2 +(n-m+1)m/2)/(n-m+1) = n/2

Dieser Durchschnittswert ist unabhängig von  m .  B  hat also gewissermaßen eine mittlere Auszahlung von  n/2  "sicher", wenn er alles dem Zufall überlässt.

Nun zu den zusätzlichen Erträgen, die sich durch die Setzung der Schwelle  x  ergeben. Hierfür sind die Paare (i,j) mit  i < x < j  zu betrachten. Der Ertrag ist dann  j ;  dies ist (j-i)/2  mehr als bei den eben verwendeten (i+j)/2 .  Wir summieren alle diese zusätzlichen Erträge auf :

Σ_j=⌈x⌉..n Σ_i=0..⌊x⌋(j-i)/2 = Σ_j=⌈x⌉..n (j ⌈x⌉/2 - ⌈x⌉ ⌊x⌋/4) = (⌈x⌉/4)·((n+1)n - ⌈x⌉ ⌊x⌋ - n ⌊x⌋ + ⌊x⌋²) = (n+1)⌈x⌉(n - ⌊x⌋)/4

Für  E  muss über alle (n+1)n/2  Paare (i,j) gemittelt werden:

E = n/2 + ⌈x⌉(n - ⌊x⌋)/2n

Beispiel :  n = 10, x = 7,5  ⇒  E = 6,2


Aufgabe 4

Berechnen Sie die optimale Schwelle  x'_opt ,  mit der  B  für den Ertrag  E  aus Aufgabe 3 den maximalen Wert  E_max  erzielt.  -  Bei der Gelegenheit können Sie auch noch  E_min  berechnen.

Wie in Aufgabe 2 genügt es, statt  E  die Funktion  y = (x+1/2)(n+1/2-x) zu betrachten. Das Maximum liegt also bei:

x'_opt = n/2   für  n  ungerade
x'_opt1 =(n-1)/2   oder   x'_opt2 =(n+1)/2   für  n  gerade

Das ist das gleiche Ergebnis wie bei Aufgabe 2:  x'_opt = x_opt .  Daraus ergibt sich  y_opt  wie in Aufgabe 2 und  E_max = n/2 +(n+1)²/(8n) für  n  ungerade und  E_max = n/2 + n(n+2)/(8n) für  n  gerade. Das lässt sich vereinfachen:

E_max = 5n/8 + 1/4 + 1/(8n)   für  n  ungerade

E_max = 5n/8 + 1/4   für  n  gerade

Die von  B  angewendete Strategie lässt ihn also ca.  25 %  mehr erhalten, als wenn er rein zufällig einen Umschlag wählt.

Wegen der parabolischen Abhängigkeit erhält man  E_min  für  x = 1/2  und  x = n - 1/2 .

E_min = (n+1)/2


Aufgabe 5

Wenn  B  eine Schwelle  x_opt ± h  mit festem  h ∈ N  wählt  (was natürlich nur für genügend große  n  einen Sinn ergibt), so ändern sich die Grenzwerte (mit wachsendem  n ) in den Aufgaben 2 und 4 nicht.

In den Aufgaben 2 und 4 wurde die Funktion  y  definiert.

y(x_opt ± h) = (n+1)²/4 - h²   ⇒   p = p_max - h²/(n²+n)  und  E = E_max - h²/(2n)   für  n  ungerade

y(x_opt1 ± h) = y(x_opt2 ∓ h) = n(n+2)/4 ± h - h²   ⇒   p = p_max - (h² ∓ h)/(n²+n)  und  E = E_max - (h² ∓ h)/(2n)   für  n  gerade

Mit wachsendem  n  strebt dieses  p  wieder gegen  3/4 ,  und  E  liegt auch hier mehr als  25 %  höher als bei zufälliger Wahl des Umschlags.

Publiziert 2020-06-18          Stand 2019-01-07

voriges Problem   |   Liste aller Probleme mit Lösungen   |    nächstes Problem