Geometric tail bound from a uniform escape probability
ID: geometric-tail-bound-from-a-uniform-escape-probability
Suppose a nonnegative stopping time and constants , satisfy on . Take to be a positive integer in discrete time. ThenOn the surviving event, conditional survival is at most . The tower property of conditional expectation therefore givesInduction proves the geometric bound. Partitioning the tail integral into intervals of length then gives ; in discrete time, group the tail sum into successive integer indices instead. This proves finite expected hitting times when every surviving state has a uniform positive chance of escaping within a fixed time. It works in discrete or continuous time without assuming independence of successive survival events.
New to topics? Read the docs here!