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

CC BY-SA 3.0
2015-12-23T08:40:02.630Z
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
CC BY-SA 3.0
2015-12-23T15:48:28.557Z
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
CC BY-SA 3.0
2015-12-23T21:36:54.420Z
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](https://en.wikipedia.org/wiki/Compact_group#Compact_Lie_groups), 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 
CC BY-SA 3.0
2015-12-23T21:43:23.243Z
@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?...)
Student
CC BY-SA 3.0
2015-12-23T21:44:12.370Z
@usul Could you kindly give a reference which may be demonstrates what you are saying?
Student
CC BY-SA 3.0
2015-12-24T01:06:52.513Z
Hi Anirbit, sorry I don't know of a reference, just thinking out loud. Imagine that there is a random infinite binary string, but you have only uncovered the prefix 01101 so far. Then you have narrowed down your random string to all strings starting with 01101, which is only a $2^{-5}$ fraction of all binary strings. To get more precision, uncover more bits.
usul
CC BY-SA 3.0
2015-12-26T17:03:07.510Z
@SashoNikolov What does a probability theorist mean when he/she says, "I know how to sample uniformly at random from this given uncountably infinite set?"
Student
CC BY-SA 3.0
2015-12-27T11:22:08.347Z
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](https://en.wikipedia.org/wiki/Wasserstein_metric) to the uniform distribution on $[0,1)$.
Sasho Nikolov
CC BY-SA 3.0
2016-01-04T22:04:20.483Z
@SashoNikolov By the second option you mean coming up with some probability distribution on some other finite set which could be close in Wasserstein metric to the uniform distribution on the uncountably infinite set? Any examples/reference you know of doing this? Do you have any example of how one constructs an uniform probability distribution in the probability theorists' sense? (..apart from may be "trivial" examples like specifying that the PDF is identically 11 for say an uniform distribution on a line..)
Student
<randomness><polynomial-time><pseudorandomness><pseudorandom-generators><sample-complexity>
How does one sample uniformly at random from an uncountably infinite set?
Student
# How does one sample uniformly at random from an uncountably infinite set?

(Asked by: username_0 on 2015-12-23)

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

**Tags:** randomness, polynomial-time, pseudorandomness, pseudorandom-generators, sample-complexity
> **Comments:**
> **username_1**: 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  
> **username_2**: 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.  
> **username_3**: 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](https://en.wikipedia.org/wiki/Compact_group#Compact_Lie_groups), 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.  
> **username_0**: @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?...)  
> **username_0**: @usul Could you kindly give a reference which may be demonstrates what you are saying?  
> **username_2**: Hi Anirbit, sorry I don't know of a reference, just thinking out loud. Imagine that there is a random infinite binary string, but you have only uncovered the prefix 01101 so far. Then you have narrowed down your random string to all strings starting with 01101, which is only a $2^{-5}$ fraction of all binary strings. To get more precision, uncover more bits.  
> **username_0**: @SashoNikolov What does a probability theorist mean when he/she says, "I know how to sample uniformly at random from this given uncountably infinite set?"  
> **username_1**: 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](https://en.wikipedia.org/wiki/Wasserstein_metric) to the uniform distribution on $[0,1)$.  
> **username_0**: @SashoNikolov By the second option you mean coming up with some probability distribution on some other finite set which could be close in Wasserstein metric to the uniform distribution on the uncountably infinite set? Any examples/reference you know of doing this? Do you have any example of how one constructs an uniform probability distribution in the probability theorists' sense? (..apart from may be "trivial" examples like specifying that the PDF is identically 11 for say an uniform distribution on a line..)  

---

## 0 answers

