Waiting Times for Ties in Random Competitions
arXiv:2105.01310
Abstract
Multiple teams participate in a random competition. In each round the winner receives one point. We study the times until ties occur among teams. We construct martingales and supermartingales that enable us to prove the results regarding these stopping times. The problems studied in this paper are motivated by their applications to databases and their storage engines that are based on augmented balanced search trees. The ties in the competitions are related to the necessary rebalancing operations that have to be executed on the database.
References in corpus (8)
- The KPZ fixed point
- Random walks in cones
- Intervals in the greedy Tamari posets
- Counting quadrant walks via Tutte's invariant method
- Late points for random walks in two dimensions
- Martin boundary of a killed random walk on a quadrant
- Convex minorants of random walks and Lévy processes
- On harmonic Functions of killed Random Walks in two dimensional convex Cones