20
$\begingroup$

What would be the best way to sample from Cantor distribution? It only has cdf and we can't invert it.

$\endgroup$
  • 4
    $\begingroup$ Actually, someone asked it on Mathematics : math.stackexchange.com/questions/1115907/… $\endgroup$ – RUser4512 Aug 12 '16 at 15:25
  • $\begingroup$ Here are some interesting follow-up questions: what is the standard deviation? What is the moment-generating function? How do they compare to their counterparts for the Uniform$(0,1)$ distribution? :-) $\endgroup$ – whuber Aug 12 '16 at 16:20
  • 5
    $\begingroup$ I like the infinite loop you guys have created by referencing the math.stackexchange post, which links back here :p $\endgroup$ – Tasos Papastylianou Aug 13 '16 at 2:12
24
$\begingroup$

Easy: sample from a Uniform$(0,1)$ distribution and recode from binary to ternary, interpreting each "1" as a "2". (This is the inverse probability transform approach: it does indeed invert the CDF!)

Figure

Here is an R implementation, written in a way that ought to port readily to almost any computing environment.

binary.to.ternary <- function(x) {
  y <- 0
  x <- round(2^52 * x)
  for (i in 1:52) {
    y <- y + 2*(x %% 2)
    y <- y/3
    x <- floor(x/2)
  }
  y
}

n <- 1000
x <- runif(n)
y <- binary.to.ternary(x)
plot(ecdf(y), pch=".")
| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ Earlier this year I started a slightly fuller implementation at github.com/Henrygb/CantorDist.R with functions rCantor(), qCantor(), pCantor() and a less meaningful dCantor() $\endgroup$ – Henry Aug 12 '16 at 19:06
  • 1
    $\begingroup$ @Henry What would dcantor implement? As Tim notes, this distribution has no density. It does not have any discrete atoms, either. It's the archetypal example of a continuous but not absolutely continuous distribution. (I like the implementation of qcantor, BTW--it's likely fast by virtue of its exploitation of matrix multiplication.) $\endgroup$ – whuber Aug 12 '16 at 19:08
  • 1
    $\begingroup$ We must keep in mind that we're only dealing with a finite approximation to the actual distribution. Let's say we had 10 ternary digit precision numbers (in practice they'll be longer), and we generated 0.0222020002 to "represent" a variable whose digits extend further. While the same comment applies to any real-valued r.v. with a continuous rv all the "represented" values the finite length approximation could stand for are also "in the set". In the actual Cantor distribution, almost all the "continuations" of that ten-digit sequence are not in the set. ...ctd $\endgroup$ – Glen_b Aug 13 '16 at 3:48
  • 2
    $\begingroup$ @whuber I clearly acknowledged that every method of generating random numbers is finite precision in my second sentence. That you chose to repeat it and the emphasis that you gave it suggests you missed my actual point there; when I represent a continuous variate to finite precision, the real values that such a finite approximation could represent are "in the set" we want to generate from. When I represent a variable such as this to finite precision, the real values such a finite approximation could represent are almost all not in the set. It's rather a different case. ... ctd $\endgroup$ – Glen_b Aug 13 '16 at 22:44
  • 2
    $\begingroup$ ctd ... no criticism of your post was implied; it was a point that readers might overlook, and may want to consider, particularly if they're trying to infer properties of the Cantor set by simulating from it. $\endgroup$ – Glen_b Aug 13 '16 at 22:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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