User talk:Gerhardvalentin/Gnedin

"English":

And the goat bleats forever

A new solution to a problem that has attracted "Die Zeit"-readers for 20 years

Christoph Drösser

Alas, the goat problem! It has bothered the readers of this newspaper for two decades. In the first edition 30/91, the first article appeared on this seemingly simple brain teaser and triggered a flood of letters, even of mathematics professors. Up to this date, the mathematical problem is heating tempers.

For those who have joined later, once more the original formulation of the problem: "You take part in a game show on television, where you have to choose one of three closed doors. Behind one door the price is waiting, a car, and behind the other two doors are goats. You point to a door, say, number 1. It remains closed for now. The host knows which door is hiding the car. With the words “I'll show you something”, he opens another door, for example, number 3, and a bleating goat is looking at the audience.
The host is asking you now: "Do you stick to number 1, or do you select number 2?"  -  Yes, what will you do now?

Many intuitively say: It does not matter whether you change your mind, there remain two doors, behind one is the car, the probability of winning is 50 percent in each case.

But that's not true, because the original probability of door 1 was one third, whereas doors 2 and 3 together accounted for two thirds. Since after the host’s action door 3 now definitely fails, the car will be behind door 2 with a probability of two-thirds. So you should switch!

The Monty Hall problem research however was never about the solution in itself, but was always on the question: How can you formulate the matter so that it looses its paradox and the solution will be evident to everyone? The mathematician Sasha Gnedin of the University of Utrecht is now making a new attempt that will be readable in the magazine Mathematical Intelligencer. In his opinion it is a mistake to regard the matter as a game of chance, which one must approach with the methods of probability theory. Because the game never has any point where mere chance becomes relevant: The producer hides the car behind one of three doors, and the host selects a door to be opened (if he ever has a choice). People have preferences - for example, what if the host is too lazy to walk and prefers to open his closest door?

"In chess, no one will have the idea to let a coin toss decide on the next move", says Sasha Gnedin. It's more about finding the best move in a game, as on both sides there are sitting humans who play to win. So it is better to make use of that kind of mathematical theory which treats such strategic problems: and that is game theory.

In contrast to chess, which has final variations, but is unmanageable, the Monty Hall problem, as a game, can be totally described very easily. It consists of exactly four moves: In the first, the car is hidden. In the second, the guest selects a door. In the third the host opens a door, presenting a goat, and in the fourth the guest of the show will decide whether he sticks or switches his choice. In total there are 24 possible variants of game history.

For such a clear straightforward game, the candidate can easily choose a strategy that covers all eventualities - even before he ever enters the TV studio. He can choose from twelve strategies: In the beginning, he chooses one of three doors. And in each case two doors will be left to be opened by the host, and for each of these cases, he can consider whether he will stick or will switch his choice.

Gnedin is arguing now: The three strategies to "select door x and then switch in any case, after the host has opened a door showing a goat" is better than the others, it "dominates" them, as this is called in game theory.

In the classical version of the story, which argues with probabilities, only the two strategies are compared, where the candidate has chosen door 1. Then the strategy A: "Choose a door and stick to it, no matter what the host does," will win for example when the car is behind door 1. The strategy B: "Choose a door and switch in every case," wins if the car is behind door 2 or 3. Consider that the second strategy only is superior under the assumption that the car is hidden behind door 1 in less than 50 percent of the cases. Maybe the team of producers indeed could have a preference for door 1?

Gnedin’s idea was to compare strategy A with other strategies of staying or switching, such as the strategy C:  "Choose door 2 and switch in any case".  This strategy wins if the car is behind door 1, but even if it is behind door 3. It dominates strategy A in the sense that it always wins if A wins, but even in one more case. Gnedin thus has shown that the three strategies in which the contestant chooses a door and then switches, absolutely dominate the nine other strategies - without any assumptions about probabilities.

This consideration admittedly does not show which door should be chosen at first by the guest. If he believes that the car has been placed randomly, he should make his choice at random. However, if he has the suspicion that the car is not hidden with the same probability behind each of the three doors, then he should choose the most unlikely one – because by switching in the next step he will maximize his chances.

German:

Und ewig meckert die Ziege

Eine neue Lösung für ein Problem, das seit 20 Jahren die ZEIT-Leser erregt

Von Christoph Drösser

Ach, das Ziegenproblem! Es beschäftigt die Leser dieser Zeitung seit zwei Jahrzehnten. In der Ausgabe 30/91 erschien der erste Artikel zu dieser scheinbar so einfachen Denksportaufgabe und löste eine Flut von Zuschriften aus, auch von Mathematikprofessoren. Bis heute erhitzt das mathematische Problem die Gemüter.

Für alle, die sich später zugeschaltet haben, hier die Originalformulierung des Problems: »Sie nehmen an einer Spielshow im Fernsehen teil, bei der Sie eine von drei verschlossenen Türen auswählen sollen. Hinter einer Tür wartet der Preis, ein Auto, hinter den beiden anderen stehen Ziegen. Sie zeigen auf eine Tür, sagen wir, Nummer 1. Sie bleibt vorerst geschlossen. Der Moderator weiß, hinter welcher Tür sich das Auto befindet; mit den Worten >Ich zeige Ihnen mal was< öffnet er eine andere Tür, zum Beispiel Nummer 3, und eine meckernde Ziege schaut ins Publikum. Er fragt: „Bleiben Sie bei Nummer 1, oder wählen Sie Nummer 2?“ - Ja, was tun Sie jetzt?

Viele sagen intuitiv: Es ist egal, ob man seine Meinung wechselt -es bleiben zwei Türen, hinter einer steht das Auto, die Gewinnwahrscheinlichkeit betragt jeweils 50 Prozent.

Aber das stimmt nicht, denn die ursprüngliche Wahrscheinlichkeit für Tür 1 war ein Drittel, auf Tür 2 und 3 entfielen zwei Drittel. Da Tür 3 nach der Aktion des Moderators definitiv ausfällt, steht das Auto mit einer Wahrscheinlichkeit von zwei Dritteln hinter Tür 2. Also sollte man wechseln!

In der Ziegenproblemforschung ging es allerdings nie um die Lösung an sich sondern stets um die Frage: Wie kann man die Sache so formulieren, dass sie ihre Paradoxie verliert und jedem die Lösung einleuchtet? Der Mathematiker Sascha Gnedin von der Universität Utrecht unternimmt nun einen neuen Versuch, der in der Zeitschrift Mathematical Intelligencer zu lesen sein wird. Seiner Meinung nach ist es ein Fehler, die Sache als Glücksspiel anzusehen, dem man mit den Methoden der Wahrscheinlichkeitsrechnung zu Leibe rücken muss. Denn in dem Spiel kommt an keiner Stelle der Zufall zum Zuge: Die Redaktion versteckt das Auto hinter einer der drei Türen, der Moderator sucht sich (falls er überhaupt die Wahl hat) eine Tür aus, die er öffnet. Menschen haben Vorlieben - was zum Beispiel, wenn der Moderator gehfaul ist und am liebsten die Tür öffnet, der er am nächsten steht?

»Im Schach kommt man auch nicht auf die Idee, über den nächsten Zug mit einem Münzwurf zu entscheiden«, sagt Sascha Gnedin. Vielmehr geht es darum, den optimalen Zug in einem Spiel zu finden, in dem auf beiden Seiten Menschen sitzen, die gewinnen wollen. Also solle man sich der mathematischen Theorie bedienen, die solche strategischen Probleme behandelt: der Spieltheorie. Im Gegensatz zum Schach, dessen Spielvariationen endlich, aber unüberschaubar sind, lässt sich das Ziegenproblem als Spiel sehr leicht vollständig beschreiben. Es besteht aus genau vier Zügen: Im ersten wird das Auto versteckt, im zweiten wählt der Kandidat eine Tür, im dritten öffnet der Moderator eine Ziegentür, und im vierten entscheidet sich der Showgast, ob er bei seiner Wahl bleibt oder wechselt. Insgesamt gibt es 24 mögliche Spielverläufe.

Für ein derart überschaubares Spiel kann sich der Kandidat leicht eine Strategie wählen, die alle denkbaren Fälle abdeckt - schon bevor er überhaupt das Fernsehstudio betritt. Zwölf Strategien hat er zur Auswahl: Am Anfang wählt er eine der drei Türen. Dann bleiben jeweils zwei Türen, die der Moderator öffnen konnte, und für jeden dieser Fälle kann er sich überlegen, ob er bei seiner Wahl bleibt oder wechselt.

Gnedin argumentiert nun: Die drei Strategien »Wähle Tür x und wechsle auf jeden Fall, nachdem der Moderator eine Ziegentür geöffnet hat« sind besser als die anderen, sie »dominieren« sie, wie der spieltheoretische Ausdruck heißt.

In der klassischen Version der Geschichte, die mit Wahrscheinlichkeiten argumentiert, werden nur die beiden Strategien verglichen, bei denen der Kandidat Tür 1 gewählt hat. Dann gewinnt etwa die Strategie A: »Wähle Tür 1 und bleibe dabei, egal was der Moderator tut«, wenn das Auto hinter Tür 1 steht. Die Strategie B: »Wähle Tür 1 und wechsle auf jeden Fall« gewinnt bei Tür 2 und 3. Überlegen ist die zweite Strategie nur unter der Annahme, dass das Auto in weniger als 50 Prozent der Fälle hinter Tür l verborgen ist. Aber vielleicht hat das Spielteam ja eine Vorliebe für Tür 1?

Gnedins Idee war es nun, Strategie A auch mit anderen Wechselstrategien zu vergleichen, etwa mit der Strategie C: »Wähle Tür 2 und wechsle auf jeden Fall«. Diese Strategie gewinnt, wenn das Auto hinter Tür 1 steht, aber auch, wenn es hinter Tür 3 steht. Sie dominiert Strategie A in dem Sinne, dass sie immer gewinnt, wenn A gewinnt, aber auch noch in einem weiteren Fall. Gnedin hat somit gezeigt: Die drei Strategien, bei denen der Kandidat eine Tür wählt und dann unbedingt wechselt, dominieren die neun anderen Strategien - ohne Annahmen über irgendwelche Wahrscheinlichkeiten.

Welche Tür der Kandidat nun als erste wählen soll, sagt diese Überlegung freilich nicht. Glaubt er, dass das Auto zufällig platziert worden ist, sollte er seine Wahl auch zufällig treffen. Hegt er jedoch den Verdacht, dass das Auto nicht mit der gleichen Wahrscheinlichkeit hinter jeder der drei Türen steckt, dann sollte er die unwahrscheinlichste wählen - weil er im nächsten Schritt ja wechselt, maximiert er so seine Chancen.