Let $0\le p_1 \le p_2 < \dots \le p_{n-1} < p_n \le 1$. Let
- $X_1^1,X^2_1,X^3_1,\dots\sim B(1,p_1)$;
- $X^1_2,X^2_2,X^3_2, \dots \sim B(1,p_2)$;
- $\dots$
- $X^1_n,X^2_n,X^3_n, \dots \sim B(1,p_n)$;
be a family of independent random variables, where $B(1,p)$ is a Bernoulli of parameter $p$.
For all $t\in \mathbb{N}$ and for all $j \in \{1,\dots,n\}$ define the frequencies corresponding to the $j$-th Bernoulli process as: $$f^t_j=\frac{1}{t} \sum_{s=1}^t X^s_j.$$
Can we provide a good lower bound depending on $t$ and $n$ (a plus if the lower bound is valid not only asymptotically in $t$) on the probability of the event $$\{f^t_n \ge \max_{j< n}f^t_j\}?$$
It is clear (since the distributions of the $f^t_j$ approach to the distribution of a Dirac in $p_j$ as $t \to \infty$) that the probability of this event approaches one as $t \to \infty$ but at which rate?
You can obtain a precise bound using Hoeffding's inequality. By Hoeffding's inequality, $\mathbb{P}(f_n^t \leq p_n-\epsilon)\leq \exp(-2t\epsilon^2)$. Also, \begin{align*} \mathbb{P}(\max_{j<n} f_j^t \geq p_n-\epsilon) &\leq (n-1)\mathbb{P}(f_{n-1}^t \geq p_n-\epsilon)\\ &=(n-1)\mathbb{P}(f_{n-1}^t \geq p_{n-1}+(p_n-p_{n-1}-\epsilon)) \\ &\leq (n-1)\exp(-2t(p_n-p_{n-1}-\epsilon)^2). \end{align*} Choose $\epsilon=(p_n-p_{n-1})/2$, to obtain that \begin{align*} &\mathbb{P}(f_n^t \leq \max_{j<n}f_j^t) \leq \mathbb{P}(f_n^t \leq p_n-\epsilon) + \mathbb{P}(f_n^t \geq p_n-\epsilon\text{ and } \max_{j<n} f_j^t \geq p_n-\epsilon) \\ &\leq \exp(-2t\epsilon^2) + (n-1)\exp(-t(p_n-p_{n-1})^2/2) \\ &\leq n\exp(-2t\epsilon^2). \end{align*}