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<T\,\,$ iff $\,\, X_i< T\,\,\forall \,\,i.$ Hence $\mathbb{P}(M<T)=\left[\mathbb{P}(X_i<T)\right]^n=\left[1-(1-p)^T\right]^n.$
$$\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)}.$$