Randomisation in the josephus problem

Abstract

The Josephus problem is a well-studied elimination problem consisting of determining the position of the survivor after repeated applications of a deterministic rule removing one person at a time from a given group. A natural probabilistic variant of this process is introduced in this paper. More precisely, in this variant, the survivor is determined after performing a succession of Bernoulli trials with parameter p designating each time at which person is removed. When the number of participants tends to infinity, the main result characterises the limit distribution of the position of the survivor with an increasing degree of precision as the parameter approaches the unbiased case p = 1/2. Then, the convergence rate to the position of the survivor is obtained in the form of a central limit theorem. A number of other variants of the suggested probabilistic elimination process are also considered. They each admit a specific limit behaviour which, in most cases, is stated in the form of an open problem.