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

  • 1
    $\begingroup$ crossposted on MO: mathoverflow.net/questions/129091/… $\endgroup$ – Suresh Venkat Apr 30 '13 at 6:56
  • $\begingroup$ Usually, when you have a cyclical variable, it's a good idea to map it to the unit circle in the plane. You can take the average to get a point inside the circle. Projecting it to the circle will give a decent estimate for $a$, and you can use $2$-dimensional estimates similar to Chebyshev's inequality. $\endgroup$ – Douglas Zare Aug 8 '14 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.