A sampling and learning question

Question

Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button.

We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to some distribution $\chi$ over $\mathbb{Z}_n$ (say, $\chi$ looks like normal distribution over $\{-(n-1)/2, ..., (n-1)/2}\}$, so the mean is $0$).

Our goal is to learn (recover) the value of $a$, given as many samples from the oracle as you wish.

I know that if the random variables are over the real $\mathbb{R}$, we can take many samples and then compute the sample mean, and then we can upper-bound the probability of failure using Chebyshev's inequality.

However, this approach doesn't seem to work since we are working in $\mathbb{Z}_{n}$, I wonder whether anyone can suggest me an approach to remove $a$.

Thank you very much! :)

Answer 1

The oracle produces i.i.d. samples from a fixed one of $n$ distributions $P_b$ corresponding to the $n$ possible values of $b$. The maximum likelihood estimator of $b$ is then the value that minimizes the Kullback-Leibler divergence $\text{KL}\left(P_b\big\vert\big\vert Q\right)$, where $Q$ is the empirical distribution of samples produced by the oracle. Of course, depending on the setting maximum likelihood might not be an appropriate approach.

Answer 2

As you can take „as many samples from the oracle as you wish”, you are in a very comfortable situation. You can compute a sample mean to an arbitrary high precision. As the precision will never be perfect in practice, the last thing to do is to perform rounding to the nearest integer.
More sophisticated approaches are not needed if you can have an arbitrarily large sample.

Answer 3

If the problem is a normal-like distribution with finite variance (i.e. not the uniform distribution over $\mathbb{Z}_n$), then treated as a discrete distribution, the probability mass function will attain a unique maximum at 0. Adding $a$ to the random variable $e$ will simply shift probability mass from $j \in \mathbb{Z}_n$ to $j + a \in \mathbb{z}_n$. Thus, the new probability mass function will attain its maximum at $0 + a \mod n = a$.

Now, since you are just searching to find the maximizer of the PMF among $n$ outcomes, you can just use Hoeffding's inequality for convergence of the empirical probability of some outcome $x$ to its actual probability, combined with a union bound to get a guarantee for all $n$ outcomes. For each outcome, maintain confidence bounds on the potential region of the actual probability of the outcome. Stop once one of them emerges as the winner with your desired level of probability.