1
$\begingroup$
  • I want to know if there are any examples of polynomial time algorithms which can sample uniformly at random from a given uncountably infinite set? (assuming it is possible)

  • Does it help if the sample space of events is actually a Lie group on which a Haar measure is known? Does knowing the Haar measure explicitly as a function help one get such an algorithm? (..because the Haar measure is "uniform" in the sense that it is invariant under the group actions..)

$\endgroup$
  • 7
    $\begingroup$ How do you represent an element of an uncountable set? What is the model of computation? Even sampling from the uniform distribution on $[0,1]$ is problematic since you need to come up with a way to represent real numbers $\endgroup$ – Sasho Nikolov Dec 23 '15 at 8:40
  • 1
    $\begingroup$ I suppose you can often get "arbitrary precision", for instance to sample from $\{0,1\}^{\mathbb{N}}$, just start taking random bits until satisfied (the random variable lies in the compact set specified by the prefix of length $n$ you have sampled so far, and this set has measure $2^{-n}$). Maybe you can generalize this to your case. $\endgroup$ – usul Dec 23 '15 at 15:48
  • 1
    $\begingroup$ I believe you can only do it (with arbitrary precision, as @usul says) if the Lie group is compact. Since the list of compact Lie groups is quite short, you only need to figure out three or four cases. On a side note, why are you asking in cstheory.SE and not math.SE, where you are much more likely to get an answer to this question? If nobody gives a satisfactory answer within a few days, you should repost this question on math.SE. $\endgroup$ – Peter Shor Dec 23 '15 at 21:36
  • $\begingroup$ @PeterShor Thanks for the suggestions! Could you kindly elaborate on your comment? (...When talking to a probability theorist they would tend to use the phrase that say for a given uncountable infinite set they "know how to sample uniformly at random". I wonder if such an assertion by a probability theorist is equivalent to having a polynomial time algorithm or are they meaning something different? How does one represent an uniform probability distribution on say a Lie group?...) $\endgroup$ – Anirbit Dec 23 '15 at 21:43
  • 1
    $\begingroup$ A probability theorist might not mean anything algorithmic, but instead that they know how to construct a uniform probability measure on this set. Or they might mean something in the vain of what @usul suggests. You can think of his suggestion as either an oracle giving the first $n$ bits of a uniform random sample from $[0,1)$, or as sampling from a discrete distribution which is close in the Wasserstein metric to the uniform distribution on $[0,1)$. $\endgroup$ – Sasho Nikolov Dec 27 '15 at 11:22

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.