# How does one sample uniformly at random from an uncountably infinite set?

• 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..)

• 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 – Sasho Nikolov Dec 23 '15 at 8:40
• 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. – usul Dec 23 '15 at 15:48
• 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. – Peter Shor Dec 23 '15 at 21:36
• @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?...) – Anirbit Dec 23 '15 at 21:43
• 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)$. – Sasho Nikolov Dec 27 '15 at 11:22