Print Page - Tricky Mandelbrot Problem

Title: Tricky Mandelbrot Problem
Post by: Perkdawg on April 11, 2017, 03:57:29 AM

Hi everyone,
Here is the basic rule of the question:
Take two random points in a structure and measure the distance between them. (straight lines only) What is the average value of the distance?

This problem is actually relatively well studied when it comes to finite structures. For example, a circle with a radius 1 has an average distance of 128/45π. For finite structures, the value can be estimated quite easily through clever programming. The tricky part is finding the exact value.

Where I'm getting stuck is when I try to apply this problem to fractals. Fractals—being inherently infinite—make finding the exact value very difficult. (If not impossible) Another problem is that computing random numbers is inherently non-random, (hence the pseudorandom) so even the estimates will be a little off. I coded a little tester and got an approximate answer of ~.69. (Bailout value was 2) Anyone have any suggestions on how to solve the problem or at least get a more accurate estimate?

Title: Re: Tricky Mandelbrot Problem
Post by: claude on April 11, 2017, 05:13:43 AM

I tried a couple of 1D examples:

Unit length line segment: d = 1/3

see https://math.stackexchange.com/questions/195245/average-distance-between-random-points-on-a-line though I calculated it in a different way (double integration with left and right parts)

Cantor middle-third fractal: d = 1/2

I found the fractal's distance like this:

Call the unknown distance d.
Then there's a P=1/2 chance that both points are in the same half of the fractal, in which case the average distance is d/3 by simple scaling.
There's also a P=1/2 chance that both points are in opposite halves, in which case the average distance is d/3 + 2/3 (distance within the half, plus distance between halves)
So d = (1/2)(d/3) + (1/2)(d/3 + 2/3) which gives d = d/3 + 1/3 so 3 d = d + 1 so 2 d = 1 and d = 1/2

As a sanity check, the fractal has "holes" so some "near" points are missing, which means the expected distance should be greater than for a "whole" line segment, as there are still "far" points.

For the Mandelbrot set however, I doubt you can get better than a statistical/Monte-Carlo method - as its implicitly defined via iteration.

See also attempts to calculate the area of the Mandelbrot set. As far as I'm aware it's not known if the boundary of the set has positive area, assuming it doesn't then you could possibly compute something based on the interior of hyperbolic components (I can't remember if it's been proven or otherwise that these are the only components in the quadratic Mandelbrot set).

Title: Re: Tricky Mandelbrot Problem
Post by: Tglad on April 11, 2017, 05:55:44 AM

For a lot of fractal shapes the average distance will be infinite, e.g. a Koch curve, Minkowski sausage.
I suspect it is the same for the mandelbrot set, the filaments follow a rough curve and get extremely thin, so I would guess that they will tend the average length up to infinity.

Claude, the Cantor middle-third fractal (1D Cantor dust) is nowhere dense is it not? In which case you can never travel from one point in the set to any other.

I think the average distance would be finite for the Menger carpet / Sierpinski triangle, but could be greater than the length of a side. The Manger carpet probably has average length of a little over 2/3 of its width. 1/3 to travel vertically, 1/3 horizontally and a bit more because occasionally you have to navigate around a hole.

I wonder what it is for Brownian noise... I suspect it would also be infinite.

Title: Re: Tricky Mandelbrot Problem
Post by: claude on April 11, 2017, 06:14:35 AM

Quote from: Tglad on April 11, 2017, 05:55:44 AM

For a lot of fractal shapes the average distance will be infinite

True if you take distance to be along the shortest wiggly path within the shape. But I assumed it was straight line distance not necessarily within the structure, and I get values from my numerical code that roughly match the 0.69 quoted above (0.6754 is my current estimate, will post more in about an hour by which time I'll have another datum..)

Title: Re: Tricky Mandelbrot Problem
Post by: Tglad on April 11, 2017, 06:36:11 AM

Oh, I see. That sounds a lot more possible to get analytic results... though still tricky I imagine.

Title: Re: Tricky Mandelbrot Problem
Post by: claude on April 11, 2017, 07:44:47 AM

some numbers

Code:

# size  distance
8       0.674814978431537815
9       0.675380757066682991
10      0.675481626317913308
11      0.675421703068835644

generated by stupid brute force code (the mandelbrot generation is super fast, the distance code takes 100s of times longer):

Code:

#include <stdio.h>
#include <mandelbrot-graphics.h>

int main(int argc, char **argv) {
  complex double c = -0.75 + I * 0.0;
  double r = 1.5;
  m_pixel_t black = m_pixel_rgba(0, 0, 0, 1);
  m_pixel_t white = m_pixel_rgba(1, 1, 1, 1);
  double er = 600;
  int maxiters = 1000000;
  for (int b = 8; b < 16; ++b)
  {
    int w = 1 << b;
    int h = 1 << b;
    m_image *image = m_image_new(w, h);
    if (image) {
      m_d_transform *transform = m_d_transform_rectangular(w, h, c, r);
      if (transform) {
        complex double c0 = 0;
        complex double dc0 = 1;
        m_d_transform_forward(transform, &c0, &dc0);
        double px = cabs(dc0);
        m_d_colour_t *colour = m_d_colour_minimal(black, white, white);
        if (colour) {
          m_d_render_scanline(image, transform, er, maxiters, colour);
          char filename[100];
          snprintf(filename, 100, "%d.png", b);
          m_image_save_png(image, filename);
          double s = 0;
          double n = 0;
          #pragma omp parallel for reduction(+:s) reduction(+:n) schedule(static, 1)
          for (int y1 = 0; y1 < h; ++y1)
          {
            double s0 = 0;
            double s1 = 0;
            for (int x1 = 0; x1 < w; ++x1)
              if (white != m_image_peek(image, x1, y1))
                for (int y2 = 0; y2 < h; ++y2)
                  for (int x2 = 0; x2 < w; ++x2)
                    if (white != m_image_peek(image, x2, y2))
                    {
                      s0 += 1.0;
                      s1 += hypot(x1 - x2, y1 - y2);
                    }
            s1 *= px;
            n = n + s0;
            s = s + s1;
          }
          s /= n;
          printf("%d	%.18f
", b, s);
          fflush(stdout);
          m_d_colour_delete(colour);
        }
        m_d_transform_delete(transform);
      }
      m_image_delete(image);
    }
  }
  return 0;
}

attached is the final image, the center of every non-white pixel is interior to the Mandelbrot set.

EDIT to add: this paper is interesting on the general "rule" mentioned in the original post: https://wwwmath.uni-muenster.de/reine/u/burgstal/d18.pdf

another EDIT: some numbers taking into account the boundary as well as the interior - the filaments are very thin so these greatly overestimate the thickness. see also second image

Code:

8       0.767666868213363052
9       0.747378308995076845
10      0.732747389502671487
11      0.720950714462732734

Title: Re: Tricky Mandelbrot Problem
Post by: Perkdawg on April 11, 2017, 09:45:03 PM

Good work claude and thanks for the help Tglad.
So at this point, we can conclude the answer is probably somewhere between .67 and .69, which is actually strangely close to e/4. (this, however is most likely a coincidence) Considering that not even the area of the mandelbrot has been calculated to an exact value, I can guess that the same is true with this question. It's unfortunate yet also intriguing because the actual value could be an even ratio or some odd conglomerate of known mathematical constants, yet it would be exceptionally difficult—if not impossible—to find using known mathematical concepts. I'll keep fiddling, and I will post in this thread if I discover anything of interest. Thanks again for the help!

Title: Re: Tricky Mandelbrot Problem
Post by: lkmitch on April 12, 2017, 06:52:30 PM

The numerical estimate of the mean distance will depend on the number of iterations and the number of points used. When I estimated the area of the Mandelbrot set (1.506484), I used a limit approach. I estimated the area using combinations of iteration count and number of points and estimated the limit as both went to infinity. Perhaps a similar approach would work here.

Welcome to Fractal Forums

Fractal Math, Chaos Theory & Research => General Discussion => Topic started by: Perkdawg on April 11, 2017, 03:57:29 AM