Hacker News new | ask | show | jobs
by klyrs 1634 days ago
The point here is that you'll almost certainly end up inside the Sierpinski triangle within a logarithmic number of steps.

Let's do the 1-dimensional version, the Cantor set.

  init_x = (anything)
  while 1:
    draw(x)
    if flip_coin() == HEADS:
       x = (x+1)/2
    else:
       x = x/2
Supposing we start with a large negative number N, and our coin is secretly TAILS on both sides, our sequence will be

  N, N/2, N/4, N/8, N/16...
So we'll rapidly converge on the point 0, but never quite make it into the interval [0, 1] because N is negative. But, if we draw our point with a diameter of say, 1/128, it will rapidly become visually indistinguishable from zero.

If the coin is fair, then something really cool happens -- if we hit a HEADS and x was already in the interval [-1, 0] then our result will be in the interval [0, 1/2] -- which is inside the interval [0, 1] where the problem is easier to think about. Approaching the problem in this way requires a bunch of case analysis, but the gist is that an attractor will quickly suck any point into the fractal -- if you get really unlucky, it will only get very close to the fractal in question.