Expected Survival Time of a Probabilistic Counting-Out Game on a Line

Abstract

Our research studies the expected survival time in a novel problem posted on a question-and-answer website. There are $n$ people in a line at positions $1,2,\dots ,n$. For each round, we randomly select a person at position $k$, where $k$ is odd, to leave the line, and shift the person at each position $i>k$ to position $i-1$. We continue to select people until there is only one person left, who then becomes the winner.

We are interested in which initial position has the largest expected number of turns to stay in the line before being selected, which we refer to as “expected survival time.” In this paper, we use a recursive approach to solve for exact values of the expected survival time. We have proved the exact formula of the expected survival time of the first and the last position as well. We will also present our work on the expected survival time of the other positions, $2,3,4,\dots$ from an asymptotic perspective.