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

3 Answers 3

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

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.

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.