Survival Probabilities of Counting-Out Games on a Line
摘要
Suppose there are n people in a line at positions \(1, 2, \ldots , n\) . Each position is either vulnerable or safe, and in each round of the counting-out game, one person in a vulnerable position is selected uniformly at random to be eliminated. When the person at position i is eliminated, the remaining people are shifted to fill in position i by moving each person in a position k such that \(k>i\) to position \(k-1\) . The game continues until only one person remains, who is the survivor. The person who starts at position k is called person k. The survival probability, denoted \(p_n(k)\) , is the probability that person k will be the survivor in a game starting with n people. By mathematical induction, a formula for the survival probability is derived for any arrangement of vulnerable and safe positions. Specific arrangements of vulnerable and safe positions are provided which produce sequences of survival probabilities that asymptotically approximate linear, exponential, and square root functions of k.