Statistical analysis of the Deterministic Pancake Problem.

摘要

The Deterministic Pancake Problem, also known as Reverse Card Shuffle and Topswaps, has the Fibonacci series for an upper bound and Ω(n2) for its lower bound. Improving either of these bounds has proven extremely difficult. This thesis presents various statistical approaches and techniques that facilitate estimating what the bound actually is. Probability distribution functions are analyzed and values for the cases of n that are too high to be computed by computer are extrapolated. While no proofs are offered, the tables, charts, and equations that this thesis presents allow for some additional insight that may facilitate subsequent proofs.