Hacker News Reader

Comment by Xcelerate | Hacker News Reader

Pretty cool. I was actually wondering the other day if, for a given manifold, there is a general algorithm to randomly choose a point on it such that each point has an equal probability of being chosen.

View on HN

This isn't possible for some manifolds. In particular, you can't choose a point uniformly from an infinite plane. To see why, split the plane into an infinite number of equally-sized (say, one by one) squares. Each square should have an equal probability that one of its points is chosen. Call this probability s.

Now let's look at the entire plane. If you pick a point, it will surely be on the plane. That means the probability that you choose a point on the plane is equal to one.

Putting the squares together gives you the whole plane, so you'd expect that summing their overall probabilities s would give you the overall probability of the plane, which is one. But there are an infinite number of squares, and there's no real number s for which the sequence s, s + s, s + s + s, ... converges to one.

What if we restrict our attention to closed manifolds?

I guess the difficulty with framing this as an algorithmic problem is that it presupposes some way of specifying the input, and I don't know exactly how that would be done. If your input is a polygonal mesh (or higher-dimensional equivalent) then the problem is easy, but what about things like parametric surfaces?

You probably mean bounded manifolds—the plane is closed (it contains all its limit points). The most general condition is that the manifold M itself has a positive, non-infinite measure m(M) (where m is the measure function). Then you can take the probability density of a set S to be m(S)/m(M). From this perspective, the problem with the plane is that it has an infinite surface area, so you can't divide by it to get a well-defined probability density.

For parametric surfaces, here's a mathoverflow post answering your exact question: http://mathoverflow.net/questions/9991/how-can-i-sample-unif... (ultimately linking to this SIGGRAPH paper: http://www.cs.virginia.edu/~jdl/bib/globillum/arvo01_notes.p...)

"Closed manifold" typically means a compact manifold without boundary (see e.g., http://en.wikipedia.org/wiki/Closed_manifold).

Ah, thanks!

http://planetmath.org/anysigmafinitemeasureisequivalenttoapr...

Yes, but the probability measure they construct doesn't give "equal probability" in the sense that Xcelerate probably meant. Going back to the plane example, if we use the unit squares as our sequence A1, A2, ..., we'll get P(A1) = 1/2, P(A2) = 1/4, P(A3) = 1/8, and so on. This sums to 1 as you'd expect, but it's not uniform!

Note that the OP desired that "each point has an equal probability of being chosen". The infinite plane being infinite, this requirement does not formally make sense, but a natural way to interpret it is to ask for invariance under isometries (or translation-invariance). As the post that you replied to indicates, this is not possible for the Euclidean plane. The measure constructed by the lemma that you cite does not have this property.

Yes, I think the above is a fairly useless digression. Thank you for making me think more about this.

> In particular, you can't choose a point uniformly from an infinite plane.

While this is true, your reasoning is incomplete, you only arrive at the conclusion that s couldn't be positive. Why couldn't be s equal to 0? Note that a 0 probability event is not an impossible event and could still be in the event space. The problem is that there are countably infinite squares on the infinite plane so the measure of the infinite plane would add up to 0 instead of 1 by the property of the measure of countably infinite union of measurable sets.

The probability of some point to be chosen is 0 for any probability measure that has a density.

Technically true, but not useful. The same is true for, say, choosing a real number uniformly at random on the interval [0,1), but nobody thinks twice about treating that as a well-defined sampling problem.

> but nobody thinks twice about treating that as a well-defined sampling problem.

This is what I wanted to show the OP: That it's not a well-defined sampling problem.

Well, obviously. Even a slightly generous reading of the GP's question would indicate that pretending he asked about an algorithm "such that, for subregions a and b of equal volume, P[a]/P[b] approaches 1 as the subregions' volume approaches 0" would give him the answer he was intuitively searching for.

Thank you for clarifying that haha. I forgot that on HN one has to articulate all ideas as formally and rigorously as possible in order to prevent the pathological cases from becoming the centerpiece of a conversation.

This is one of those cases where 0 != 0+. If every point had zero probably then the sum of all of them adds up to zero.

What the sum of an uncountably infinite bunch of zeros is, is the subject of the Calculus. There are systems that treat dx as something strictly different from zero (but not any finite value), though.

That's why sigma additivity (property of a probability measure) only allows union/sum only of a countable number of elements of the sigma algebra:

> http://en.wikipedia.org/wiki/Sigma_additivity

well, it's a specific zero: dx.

You know that's trivially true, right? When you define "equal probability" for each point, you imply a measure, for example the Minkowski content for manifolds in R^n. Then by simply assigning probability measure(Region)/measure(Manifold), you have your algorithm (note there are problems if the number of points is not finite or your distribution is not diadric, so if you're given random bits to draw from you can only approximate the random choice in finite time).

It's not at all obvious to me how "assigning a probability measure" translates into an actual algorithm. For one thing, if you have an n-D manifold embedded in an (n+1)-D space, any set of points on the manifold will have measure zero in the enclosing region.

To give an intuitive definition, consider the volume near the n-D manifold, up to a distance d. As you get nearer the volume goes down it starts looking like ~A*2d -- in fact we define A as the limit as d goes to 0 of the volume divided by 2d. You can extend this to k-D manifolds on n-D spaces by normalizing this volume with a n-k dimensional ball.

http://en.wikipedia.org/wiki/Minkowski_content

Now you can partition this set in any way you want and apply the rule I mentioned for each partition (p=measure(Partition)/measure(Manifold)). Simply because that is precisely how one might define "equal probabilities", there exists an algorithm which partitions the manifold into simply connected compact sets of decreasing measure which converges to giving "equal probabilities": the definition implies an algorithm.

Edit: panic above clarified the requirement. I missed that that measure(Manifold) must of course exist, but I'm confident all else is self-evident.

Reply on news.ycombinator.com