English: Probability mass function of the length of the longest cycle of a random permutation of length 100. Cycle lengths ≤ 50 are green, cycle lengths > 50 are red.

to share – to copy, distribute and transmit the work

to remix – to adapt the work

Under the following conditions:

attribution – You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).

share alike – If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one.

https://creativecommons.org/licenses/by-sa/3.0
CC BY-SA 3.0
Creative Commons Attribution-Share Alike 3.0
truetrue

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled GNU Free Documentation License.http://www.gnu.org/copyleft/fdl.htmlGFDLGNU Free Documentation Licensetruetrue

You may select the license of your choice.

File history

Click on a date/time to view the file as it appeared at that time.

{{Information |Description ={{en|1=Probability mass function of the length of the longest cycle of a random permutation of length 100. Cycle lengths ≤ 50 are green, cycle lengths > 50 are red.}} |Source ={{own}} |Author =[[User:Qua...

File usage

The following pages on the English Wikipedia link to this file (pages on other projects are not listed):

This file contains additional information, probably added from the digital camera or scanner used to create or digitize it.
If the file has been modified from its original state, some details may not fully reflect the modified file.

Short title

Gnuplot

Image title

Produced by GNUPLOT 4.6 patchlevel 5

Width

650

Height

470

RELATED RESEARCH TOPICS

1.
100 prisoners problem
–
The 100 prisoners problem is a mathematical problem in probability theory and combinatorics. In this problem,100 numbered prisoners, to survive, must find their own numbers in one of 100 drawers, the rules state that each prisoner may open only 50 drawers, and cannot communicate with other prisoners. At first glance the situation appears hopeless—but a clever strategy offers the prisoners a chance of survival. Danish computer scientist Peter Bro Miltersen first proposed the problem in 2003, the 100 prisoners problem has different renditions in the literature. The following version is by Philippe Flajolet and Robert Sedgewick, The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a room contains a cupboard with 100 drawers. The director randomly puts one prisoners number in each closed drawer, the prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order, the drawers are closed again afterwards. If, during this search, every prisoner finds his number in one of the drawers, if just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy—but may not communicate once the first prisoner enters to look in the drawers, what is the prisoners best strategy. If every prisoner selects 50 drawers at random, the probability that a single prisoner finds his number is 50%, therefore, the probability that all prisoners find their numbers is the product of the single probabilities, which is 100 ≈0.0000000000000000000000000000008, a vanishingly small number. Surprisingly, there is a strategy that provides a probability of more than 30%. The key to success is that the prisoners do not have to decide beforehand which drawers to open, Each prisoner can use the information gained from the contents of previously opened drawers to help decide which drawer to open next. Another important observation is that way the success of one prisoner is not independent of the success of the other prisoners. To describe the strategy, not only the prisoners, but also the drawers are numbered from 1 to 100, the strategy is now as follows, Each prisoner first opens the drawer with his own number. If this drawer contains his number he is done and was successful, otherwise, the drawer contains the number of another prisoner and he next opens the drawer with this number. The prisoner repeats steps 2 and 3 until he finds his own number or has opened 50 drawers and this approach ensures that every time a prisoner opens a drawer, he either finds his own number or the number of another prisoner he has not yet encountered. The reason this is a strategy is illustrated with the following example using eight prisoners and drawers. The prison director has distributed the numbers into the drawers in the following fashion The prisoners now act as follows, Prisoner 1 first opens drawer 1