7 ms·

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 poin

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.

wolfgke 12y ago
The probability of some point to be chosen is 0 for any probability measure that has a density.
- teraflop 12y ago
  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.
  - wolfgke 12y ago
    > 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.
- colanderman 12y ago
  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.
  - Xcelerate 12y ago
    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.
- Retric 12y ago
  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.
  - bandrami 12y ago
    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.
  - wolfgke 12y ago
    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 http://en.wikipedia.org/wiki/Sigma_additivity
- bandrami 12y ago
  well, it's a specific zero: dx.
darkmighty 12y ago
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).
- teraflop 12y ago
  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.
  - darkmighty 12y ago
    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 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.
panic 12y ago
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.
- teraflop 12y ago
  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?
  - panic 12y ago
    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-uniformly-from-a-surface 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.pdf http://www.cs.virginia.edu/~jdl/bib/globillum/arvo01_notes.p...)
    - ihm 12y ago
deleted 12y ago
[deleted]

wolfgke 12y ago

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

teraflop 12y ago
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.
- wolfgke 12y ago
  > 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.
colanderman 12y ago
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.
- Xcelerate 12y ago
  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.
Retric 12y ago
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.
- bandrami 12y ago
  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.
- wolfgke 12y ago
  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 http://en.wikipedia.org/wiki/Sigma_additivity
bandrami 12y ago
well, it's a specific zero: dx.

darkmighty 12y ago

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

teraflop 12y ago
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.
- darkmighty 12y ago
  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 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.

panic 12y ago

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.

teraflop 12y ago
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?
- panic 12y ago
  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-uniformly-from-a-surface 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.pdf http://www.cs.virginia.edu/~jdl/bib/globillum/arvo01_notes.p...)
  - ihm 12y ago

deleted 12y ago

[deleted]