Problem
Given a discrete random variable $\xi$ with codomain $\Xi \subset \mathbb{N}$, $\left| \Xi \right| < \infty$ and unknown distribution $\mathbb{P}$, and an infinite sequence $\left( \xi_i: i \in \mathbb{N} \right)$ of samples with the same distribution $\mathbb{P}$, I would like to estimate the mode of the distribution, namely a number $x \in \Xi$, such that $$ \mathbb{P}\left( x \right) = \max\limits_{x' \in \Xi} \mathbb{P}\left( x' \right), $$ after a finite number of steps of Monte Carlo.
Sketches of the solution
We can reformulate the problem $$ \mathbb{P}\left( x \right) = \max\limits_{x' \in \Xi} \mathbb{P}\left( x' \right) $$ as $$ \mathbb{P}\left( x \right) \ge \mathbb{P}\left( x' \right), \quad \forall x' \neq x. $$ If we substitute the probabilities with histograms $$ h^n\left( x \right) = \frac{1}{n} \cdot \sum\limits_{i = 1}^n \left[ \xi_i = x \right], \quad n \in \mathbb{N}, $$ we can talk about the probability of $$ h^n\left( x \right) \ge h^n\left( x' \right), \quad \forall x' \neq x. $$ Thus, if I use Monte Carlo, I would like to set the accuracy $p$ for $$ \mathbb{P}\left( \forall x' \neq x: h^n\left( x \right) \ge h^n\left( x' \right) \implies \forall x' \neq x: \mathbb{P}\left( x \right) \ge \mathbb{P}\left( x' \right) \right) \geq p. $$
Issue
If the histograms were independent, there would not be any problems in estimating $$ \mathbb{P}\left( \forall x' \neq x: h^n\left( x \right) \ge h^n\left( x' \right) \implies \forall x' \neq x: \mathbb{P}\left( x \right) \ge \mathbb{P}\left( x' \right) \right) = \prod\limits_{x' \neq x} \mathbb{P}\left( h^n\left( x \right) \ge h^n\left( x' \right) \implies \mathbb{P}\left( x \right) \ge \mathbb{P}\left( x' \right) \right) \geq p. $$ The problem is that they are connected with a relation $$ \sum\limits_{x \in \Xi} h^n\left( x \right) = 1. $$ Here is the example: let us consider two samples ($n = 2$), three values ($\left|\Xi\right| = 3$) and assume the uniform distribution of possible configurations of the histogram. Then, $h^2\left( x_1 \right) \geq h^2\left( x_2 \right)$ and $h^2\left( x_1 \right) \geq h^2\left( x_3 \right)$ may occur in the cases
| $h^2\left( x_1 \right)$ | $h^2\left( x_2 \right)$ | $h^2\left( x_3 \right)$ |
|---|---|---|
| 2 | 0 | 0 |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
We can see that there are only $3$ cases when both inequalities hold, while there are $9$ possibilities in total. This means that the probability $$ \mathbb{P}\left( h^2\left( x_1 \right) \geq h^2\left( x_2 \right), h^2\left( x_1 \right) \geq h^2\left( x_3 \right) \right) = \frac{1}{3}. $$ If we treat the values as independent, we have $$ \mathbb{P}\left( h^2\left( x_1 \right) \geq h^2\left( x_2 \right) \right) \cdot \mathbb{P}\left( h^2\left( x_1 \right) \geq h^2\left( x_3 \right) \right) = \frac{6}{9} \cdot \frac{6}{9} = \frac{36}{81} > \frac{1}{3}. $$
Question
Using Monte Carlo, given a generator, are there known methods of estimating mode with a predefined accuracy?