<p>Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button.</p>

<p>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$).</p>

<p>Our goal is to learn (recover) the value of $a$, given as many samples from the oracle as you wish.</p>

<p>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.</p>

<p>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$.</p>

<p>Thank you very much! :)</p>

CC BY-SA 3.0
2013-04-30T06:56:45.530Z
crossposted on MO: http://mathoverflow.net/questions/129091/a-sampling-and-learning-question
Suresh Venkat
CC BY-SA 3.0
2014-08-08T08:51:11.323Z
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.
Douglas Zare
<lg.learning><pr.probability>
A sampling and learning question
Richard
# A sampling and learning question

(Asked by: username_0 on 2013-04-29)

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

**Tags:** lg.learning, pr.probability

> **Comments:**
> **username_1**: crossposted on MO: http://mathoverflow.net/questions/129091/a-sampling-and-learning-question  
> **username_2**: 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.  

---

## 0 answers

