1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ Try the mode of the results $b$. $\endgroup$
    – Did
    Apr 29, 2013 at 13:15
  • $\begingroup$ Sorry, what do you mean? Can you elaborate a bit more? Thanks. :) $\endgroup$
    – Richard
    Apr 29, 2013 at 13:32
  • $\begingroup$ See en.wikipedia.org/wiki/Mode_%28statistics%29. $\endgroup$
    – Did
    Apr 29, 2013 at 22:09
  • $\begingroup$ Is $\chi$ the normal distribution or is $\chi$ just "some distribution"? $\endgroup$ Aug 23, 2013 at 22:06

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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