Preemptively Guessing the Center

An online algorithm is typically unaware of the length of the input request sequence that it is called upon. Consequently, it cannot determine whether it has already processed most of its input or whether the bulk of work is still ahead. In this paper, we are interested in whether some sort of orientation within the request sequence is nevertheless possible. Our objective is to preemptively guess the center of a request sequence of unknown length n: While processing the input, the online algorithm maintains a guess for the central position n/2 and is only allowed to update its guess to the position of the current element under investigation. We show that there is a randomized algorithm that in expectation places the guess at a distance of 0.172n from the central position n/2, and we prove that this is best possible. We also give upper and lower bounds for a natural extension to weighted sequences. This problem has an application to preemptively partitioning integer sequences and is connected to the online bidding problem.