# 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.
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.