Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support

Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $\{1,2,...,n\}$ with probability mass function $i \mapsto p_i$. How many samples of $\mathcal{D}$ are needed to learn the mode of $\mathcal{D}$, i.e. the $j$ such that $p_j=\max\{p_i\}$, (with error probability $\delta$)? Is there any known lower bound? Any idea, comment, or reference will be very helpful.

• I know that $\Theta(\frac{1}{d_H^2} \log\frac{1}{\delta})$ samples are required regarding Hellinger distance of $\mathcal{D}=(p,1-p)$ and $\mathcal{D}'=(1-p,p)$ in the case of $n=2$.
• I proved an upper bound $O(\frac{1}{\varepsilon^2} \log \frac{n}{\delta})$ with standard Hoeffding bound, where $\varepsilon$ is the difference between the largest and the second largest among $p_i$'s.

Update: I proved a lower bound $\Omega(\frac{1}{\gamma}\log\frac{1}{\delta})$ by reducing the problem to some $n=2$ case, where $\gamma=\min_i\left(1-2\sqrt{\frac{pp_i}{(p+p_i)^2}}\right)$ with $p$ being the mode. But, I still want to reduce the gap between upper and lower bounds.

A followup question: Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $A\cup B:=\{a_1,...,a_n\}\cup\{b_1,...,b_m\}$ with probability mass function $a_i \mapsto p_i$ and $b_i \mapsto q_i$. How many samples of $\mathcal{D}$ are required to make sure the most frequent sample is in $A$ (with error probability $\delta$)? For sanity, it is guaranteed that $A$ contains the mode of $\mathcal{D}$.

• Following Clement's answer, I could prove an upper bound of $O(\frac{1}{\varepsilon^2}\log\frac{1}{\delta})$, where $\varepsilon=\max\{p_i\}-\max\{q_i\}$. However, a nice lower bound eluded me, mainly because reducing to a Bernoulli case does not seem to work in this case.

Asked by user66625 (33 )
May 19, 2022 at 12:31