The Mathematics of High Scores

Abstract

Many video games maintain a list of high scores. This paper investigates mathematical questions inspired by lists of high scores. First, we make the distinction between those high scores which were records when they were earned---the highest score attained, and those scores which are merely among the top five, ten, or twenty. We consider Yn, the number of high scores which were formerly records after n games have been played, showing that Yn has a stationary distribution, and deducing the probabilities P(Yn = k), for k ? 1. We next turn to a dynamic analysis and model the changes in Yn using a Markov chain, and use this to prove that the expectancy of the next change in Yn is infinite. Finally, we turn to a relaxed version of the problem and consider Zn, the number of changes in the list of high scores after n games. Although the expected waiting time for the next record is infinite, the waiting times are only finite when we seek only the next change in the list. Using a generating function analysis, we find a closed form for the expected waiting times for a change in Zn.