Two-slip game

from Wikipedia, the free encyclopedia

The two-slip game or two-envelope problem examines the question of which strategy can be used to find the larger of two numbers if one of these two numbers is unknown and one only knows that both numbers are different from each other .

One would intuitively assume that the probability of correctly determining the larger number under these conditions is 50 percent. In fact, it has been shown that with a suitable strategy, the probability of success can be increased to a value greater than 50 percent. Without further constraints, if the two numbers are well selected, the deviation tends to approach zero and is meaningless in practice.

Problem

The problem was described in 1987 by Thomas M. Cover as follows:

“Player 1 writes any two different numbers on pieces of paper. Player 2 randomly chooses one of them, both slips of paper being equally likely, and looks at the number. Player 2 must now decide whether the chosen number is the larger. It does not seem possible to guess better than with a probability of 1/2. "

A more general formulation by Franz Thomas Bruss from 1998 reads:

“You have to choose between two alternatives and you hardly know which one could be cheaper. Then you can flip a coin right away, right? No: it can be done better. "

Such situations always arise in daily life when one has to decide for or against an alternative without knowing whether a better opportunity might not come. Examples of this are a special offer in the supermarket, the search for a new apartment or job, a partner for life, etc. Another practical example is the sale of a house with two interested parties, whereby if the offer is rejected, you cannot return to the interested party.

Solution strategy

Example implementation in Python 
#!/usr/bin/env python
import random

wiederholungen = 1000000
zahlenbereich = 1000
treffer1 = 0
treffer2 = 0

for i in range(wiederholungen):
  # Zwei zufaellige, aber unter-
  # schiedliche Zahlen erzeugen
  while True:
    x = random.randrange(zahlenbereich)
    y = random.randrange(zahlenbereich)
    if x != y:
      break

  # Algorithmus 1
  # (Zufaellige Wahl von z)
  z = random.randrange(zahlenbereich)
  if x <= z and x < y:
    treffer1 = treffer1 + 1
  elif x > z and x > y:
    treffer1 = treffer1 + 1

  # Algorithmus 2
  # (Feste Wahl von z)
  z = zahlenbereich / 2
  if x <= z and x < y:
    treffer2 = treffer2 + 1
  elif x > z and x > y:
    treffer2 = treffer2 + 1

# Ausgabe
print(treffer1)
print(treffer2)

Choose an estimate for the expected numbers. If the known number is greater than this, accept it. Otherwise, choose the unknown number.

analysis

There are three cases:

  1. If the estimated value is smaller than both numbers, the known number is always chosen. The probability of success is therefore 50 percent and corresponds to random guessing.
  2. If the estimated value is greater than both numbers, the unknown number is always chosen. The probability of success is still 50 percent.
  3. If the estimated value lies between the two numbers, the above solution strategy leads deterministically to the choice of the larger number. The probability of success increases to 100 percent.

Let P (T) be the probability of landing a "hit", i.e. to choose an estimated value between the values ​​of both slips of paper, then the success probability P (E) is calculated as:

Regardless of the choice of the estimated value, the probability of success is at least 50 percent. In no case does the strategy fare worse than random guessing. If the hit probability is really greater than zero, the probability of success is also really greater than 50 percent. It is less obvious that this is always the case with a suitable choice of the estimated value.

Choice of appraisal

A hit probability that is really greater than zero can be guaranteed even if nothing is known about the distribution of the numbers on the slips of paper. The estimated value may not be determined by the player; instead, it is drawn from a suitable probability distribution in a random experiment . All distributions whose probability density does not vanish over the entire range of real numbers are suitable for this , such as the normal distribution .

If the slips are limited to a range of values ​​known to the player, a probability distribution is sufficient, the density of which does not disappear in this range. In practice this is often the case. In the case of the aforementioned house sale, it is possible to reliably estimate the market price upwards and downwards.

If the player knows exactly the probability distribution of the numbers on the slips of paper, he can determine a fixed estimate that maximizes the probability of a hit.

Assumptions and Limitations

Which of the two pieces of paper is revealed first must be decided randomly, equally likely and regardless of the choice of the estimated value. Otherwise the assumption is violated that the (un) known number is always chosen, which corresponds to a random selection.

The numbers on both pieces of paper must be different from each other. Otherwise a larger number does not exist and cannot be chosen. The probability of success is then basically zero and cannot be improved by the solution strategy described. In practice, this restriction is irrelevant, since any alternative can be selected if the alternatives are the same.

Implementation in Python

The adjacent figure shows an exemplary implementation of the solution strategy in the Python programming language . The two numbers are chosen as natural numbers from the number range from 0 to 1000 and it is ensured that they are different from each other. The first algorithm implements the above solution strategy for a randomly chosen estimated value from the stated range of numbers, the second algorithm uses a modified strategy and selects the estimated value constantly in the middle of the observed interval. The hits achieved by the respective algorithms are added up and output at the end. For a sufficiently large number of repetitions, the numerical hit probabilities are approx. 66.7 percent for the first and approx. 75.0 percent for the second algorithm.

Related topics

The two-slip game is somewhat similar to the exchange paradox . While the surprise in the two-slip game is that there is a sensible exchange strategy, the exchange paradox comes to the paradoxical solution that one should always exchange. The exchange paradox is resolved by uncovering the contradiction in the conclusion, and would be resolved if it didn't matter which envelope one took; The two-slip game also shows that there are indeed sensible exchange strategies that differ from the "always exchange" strategy.

Other related topics where one can make the optimal decision of the remaining problem from a piece of information are:

Web links