» » » » » » Coin-tossing


Coin_tossingCoin flipping or coin tossing is the practice of throwing a coin in the air to resolve a dispute between two parties or otherwise choose between two alternatives.

Coin flipping is a method that trusts the decision to pure luck, since there is no possibility for strategy, and any attempt to alter the odds (such as, most obviously, using a fake coin with both sides the same) is considered cheating. It is generally assumed that the outcome is unpredictable, with equal probabilities for the two outcomes (the fair coin), although careful analysis has shown that is not quite the case.

History of coin flipping

The historical origin of coin flipping is the interpretation of a chance outcome as the expression of divine will. A well-known example of such divination (although not involving a coin) is the episode in which the prophet Jonah was chosen by lot to be cast out of the boat, only to be swallowed by a giant fish (Book of Jonah, Chapter 1).

Coin flipping as a game was known to the Romans as “navia aut caput” (ship or head), as some coins had a ship on one side and the head of the emperor on the other. In England, this game was referred to as cross and pile.

Number-theoretic version of “flipping”

There is no fair way to use a coin flip to settle a dispute between two parties over distance — for example, two parties on the phone. The flipping party could easily lie about the outcome of the toss. Instead, the following algorithm can be used:

  1. Party A chooses two large primes, either both congruent to 1, or both congruent to 3, mod 4, called p and q, and produces N = pq; then N is communicated to party B, but p and q are not. It follows N will be congruent to 1 mod 4. The primes should be chosen large enough that factoring of N is not computationally feasible. The exact size will depend on how much time party B is to be given to make the choice in the next step, and on party B’s expected resources.
  2. Party B calls either “1” or “3”, a claim as to the mod 4 status of p and q. For example, if p and q are congruent to 1 mod 4, and B called “3”, B loses the toss.
  3. Party A produces the primes, making the outcome of the toss obvious; party B can easily multiply them to check that A is being truthful.

Counterintuitive properties

If the successive tosses of a coin are recorded as a string of “H” and “T”, then for any trial of tosses, it is twice as likely that the triplet TTH will occur before THT than after it. It is three times as likely that THH will precede HHT.

Image http://en.wikipedia.org/wiki/File:Coin_tossing.JPG

Licensed under the GNU Free Documentation License. It uses materials from the Wikipedia.

Leave a Reply

Your email address will not be published. Required fields are marked *