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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Survival Probabilities of Counting-Out Games on a Line

  • Bryce Thalheimer,
  • John C. Wierman

摘要

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.