|Random Bulgarian Solitaire|
|Other Names: Stochastic |
|Inventor: Serguei Popov, 2003|
Random Bulgarian Solitaire was invented by the Brazilian statician Serguei Popov in 2003. He teaches at the Instituto de Matemática e Estatástica of Sao Paulo University. It is a generalized variant of Deterministic Bulgarian Solitaire.
The game has almost the same rules as Bulgarian Solitaire. However, one card is removed from each pile with a fixed probability p.
- If p = 0, the piles are left intact.
- If p = 1, the game is Deterministic Bulgarian Solitaire.
- The general case with 0 < p < 1 is known as Random Bulgarian Solitaire or Stochastic Bulgarian Solitaire. This is a finite irreducible Markov chain.
- If N is a triangular number (that is N = 1 + 2 + 3 + ... + k, for some k), then it is known that Deterministic Bulgarian Solitaire will reach a stable configuration in which the size of the piles is 1, 2, 3, ... k. This state is reached in k² - k moves or fewer. If N is not triangular, no stable configuration exists and a limit cycle is reached.
- Popov showed that Stochastic Bulgarian Solitaire spends "most" of its time in a "roughly" triangular distribution.
- Popov, S.
- Random Bulgarian Solitaire. Sao Paulo (Brazil) February 1, 2004.
- Popov, S.
- Random Bulgarian Solitaire. In: Random Structures & Algorithms 2005; 27 (3): 310-330.