{'fraction_non_alphanumeric': 0.05616526791478373, 'fraction_numerical': 0.007746933505487412, 'mean_word_length': 4.081967213114754, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sharp bounds for winning probabilities in the competitive rank selection problem

In this problem two players A and B observe sequentially n uniquely rankable options. All arrival orders of ranks are supposed to be equally likely (probability = 1/n! each) and A and B have to select one option each. The decision must be based on relative ranks only (no-information game) and A has the priority of choice. Let p(n, k) be the probability that player A will choose a better rank than player B, given that neither A nor B has stopped (selected an option) before step k. We call p(n, k) the winning probability of A at step k in a n-options game. Note that p(n, n) is not defined, because if A has not yet stopped on {1, 2, · · · , n − 1} then A must select option n and thus B must have stopped earlier. Enns and Ferenstein [2], who studied this problem as ‘the horse game’, pointed out already that the p(n, k) are not monotone. Therefore the proof of the existence of limn→∞ p(n, k(n)) is not easy (this question will be studied in a more technical paper; see also Enns et al. [3]). The corresponding question for the full information game has been completed by Chen et al. [1]. Another interesting question is: what is the range of p(n, k) for different n and k? Numerical evidence (already obtained by Enns and Ferenstein) suggest that 1/2 is a lower bound and 3/4 is an upper bound. We now present an elementary probabilistic proof that these values are indeed the sharp uniform bounds. (We formulate our results in terms of q(n, k) = 1− p(n, k).)