# Tail bound on the maximum of i.i.d. geometric random variables

Let $$X_1,\ldots,X_n\sim \mathit{Geo}(p)$$ be independent random variables, and let $$M=\max\{X_1,\ldots,X_n\}$$ denote their maximum.

Given a parameter $$\delta\in(0,1)$$, I'm looking for a bound $$T(n,p,\delta)$$ of the form $$\Pr[M > T(n,p,\delta)]\le \delta.$$

A simple solution can be derived using the union bound. If we demand $$(1-p)^T = \Pr [X_i> T] \le \delta/n,$$ we have $$T=\frac{\ln(\delta/n)}{\ln(1-p)}$$, and a union bound over all $$X_i$$'s show that this holds.

However, I think that this is a rather loose bound, and some simulations I did seem to agree.

• How can we get a tighter bound (ideally, a close-form bound that is possible to work with)?

$$M=\underset{1\le i\le n}{\max} X_i.$$ This means $$M iff $$\,\, X_i< T\,\,\forall \,\,i.$$ Hence $$\mathbb{P}(M
$$\text{You need }\left[1-(1-p)^T\right]^n=1-\delta$$ $$\iff 1-(1-\delta)^{1/n}=(1-p)^T\iff \,\,T=\dfrac{\log\left(1-(1-\delta)^{1/n}\right)}{\log(1-p)}.$$