we get that if holds, with probability at least $1-\delta$, it holds that $$\overline{X}_t \ge \overline{Y}_t\,,$$ which implies that we have identified the distribution with the highest mean correctly. Equation  determines the number of samples that is required to make the right decision with high probability. Notice that this number scales like $1/g^2$, which implies that the identification is more difficult (more samples are required) when there is a small gap between the two distributions.

In our image matching problem, given a query image, we want to find an image that is closest in terms of an approximate cosine distance. The BoW procedure processes the features one by one, increasing the score of each candidate image by some number. We can view the candidate images as different distributions and the new scores as the new samples. At each round, we have a new estimate for the similarity of each candidate image to the query image. The problem is to stop sampling and return the true match as quick as possible.

It might seem natural to use the stopping condition  for this problem. However, we found out that these theoretical results are very conservative in practice and often require the processing 