Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose I have some nicely defined "fractal" subset of (to make life simpler) Euclidean space $\mathbb{E}^n,$ of some arbitrary Hausdorff dimension $s,$ such that the corresponding Hausdorff measure $H_s$ has positive mass. The first question is whether it makes sense to talk of a "uniform sample" (or Poisson point process) with respect to $H_s$ (since it is only an outer measure), and second question is: if it makes sense, have people figured out how to generate uniform $H_s$ variates (in simple cases, like the von Koch snowflake, or the more interesting cases, like limit sets of Kleinian groups)?

share|improve this question
    
What do you mean "only an outer measure"? Isn't it a measure on the borel sets? Also, does "variate" here just mean an algorithm to produce uniform random variables? If so, it is easy in the case of the snowflake. –  Ori Gurel-Gurevich Sep 17 '11 at 19:12
    
What Ori said. Use a Borel set. All the usual "nicely fractal" sets in Euclidean space are Borel sets. Indeed, they are compact or at least sigma-compact. –  Gerald Edgar Sep 17 '11 at 19:16
    
I am a babe in the woods of measure theory... As for variates, yes, an algorithm. In particular, what is the "easy method" for the snowflake? And how do you go about proving that some algorithm gives uniform points (for snowflake or dynamically defined sets)? –  Igor Rivin Sep 17 '11 at 19:20
    
Other people have answered, but still: To pick a uniform point on one side (out of three) of the snowflake, you just have to pick 1 of the 4 parts of the curve, then 1 of 4 parts of that part, etc. It is really no different than picking a uniform point on $[0,1]$, by iteratively choosing halves of the interval. –  Ori Gurel-Gurevich Sep 19 '11 at 18:44
    
@Ori: I sort of guessed that, but why is that true? What is the general version of the construction? Presumably, it's some iterated function system thing, but if I knew all there was to know about such, I would not be asking the question... –  Igor Rivin Sep 19 '11 at 19:25
add comment

3 Answers

There is a standard map from the interval $[0,1]$ onto the snowflake curve, that maps Lebesgue measure into (constant multiple of) Hausdorff measure. So take a sample in $[0,1]$ and map it to the snowflake.

This works for all of the standard "self-similar" IFS constructions of fractals, when the IFS satisfies the open set condition. There is a standard "parameter space" or "code space" with a well-understood measure on it that maps onto the fractal, and the image measure is (constant multiple of) Hausdorff measure, and also (constant multiple of) packing measure.

share|improve this answer
    
@Gerald: thanks, but saying that the construction is "standard" does not tell me what it is. Would you happen to have any references you would particularly recommend? –  Igor Rivin Sep 17 '11 at 20:20
    
Ken Falconer's books are a great place to start. –  BSteinhurst Sep 19 '11 at 14:21
    
@BSteinhurst: thanks, I have started looking at one of them already... –  Igor Rivin Sep 19 '11 at 15:21
    
I could also plug my own book, Measure, Topology, and Fractal Geometry –  Gerald Edgar Sep 19 '11 at 18:31
    
@Gerald: I don't think there is anything morally wrong about suggesting your own book (especially if it is the best book on the subject :)) –  Igor Rivin Sep 19 '11 at 19:26
add comment

Given $A$ a loc. compact space and $\mu$ a loc. finite measure on $A$, there exists a unique Poisson point process $\eta$ with control measure $\mu$. (see for instance th.3.2.1 in "stochastic geometry", by Schneider & Weil, if there are no atoms, but it holds in full generality) .

If $A$ is your fractal and $\mu$ Hausdorff measure, then $\eta$ is what you are looking for, isn't it?

For the construction, everything depends on how you define your fractal set. The difficulty is exactly the same as drawing a uniform random point in a subset that has finite Hausdorff measure.

share|improve this answer
    
Firstly, thanks for the reference! As for "nicely defined", the canonical example is a limit set of a kleinian group, but again, the snowflake is a nice simple example... –  Igor Rivin Sep 19 '11 at 15:19
add comment

If one interprets "nicely defined" correctly, the answer is "yes, duh!".

One possible interpretation is to be the attractor of a Horseshoe map. Then the dynamics on this attractor can be conjugated to symbolic dynamics and it is clear what "drawing a random point" means, and how to generate them numerically. Of course, one also needs to check that the invariant measure has maximal Hausdorff dimension.

In order to illustrate this, let me give the simplest example. Consider the map $f(x) = x^2 - c$ for $c > 4$. It is well known, that there exists an invariant set $\Sigma = f^{-1}(\Sigma)$ with Hausdorff dimension $\in (0,1)$. $\Sigma$ can be described as $$ \Sigma = \{x:\quad \exists C>0 \forall n\geq 1, |f^n(x)|\leq C\} $$ so the set of points with bounded orbit. If you define for $x\in \Sigma$ the sequence $$ x_n = \begin{cases} 1 & f^n(x) > 0, \\\ - 1,& f^n(x) < 0 \end{cases} $$ Then standard results imply that the Bernouilli measure on $\{-1,1\}^{\mathbb{N}}$ is conjugate to the measure of maximal Hausdorff dimension, which is ergodic with respect to $(\Sigma, f)$. Hence, picking a random point just amounts to choosing a random string of $\pm 1$.

share|improve this answer
    
Thanks! I will try to digest... –  Igor Rivin Sep 19 '11 at 15:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.