# A sampling and learning 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! :)

-
Try the mode of the results $b$. –  Did Apr 29 '13 at 13:15
Sorry, what do you mean? Can you elaborate a bit more? Thanks. :) –  Richard Apr 29 '13 at 13:32
–  Did Apr 29 '13 at 22:09
Is $\chi$ the normal distribution or is $\chi$ just "some distribution"? –  Kelly Davis Aug 23 '13 at 22:06
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.