Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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! :)

share|improve this question
1  
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
    
See en.wikipedia.org/wiki/Mode_%28statistics%29. –  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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.