Notices
Results 1 to 12 of 12

Thread: Chaos Game

  1. #1 Chaos Game 
    Forum Freshman
    Join Date
    Jun 2006
    Posts
    5
    I'm new to this forum so hi to everybody.
    I would like to ask a question refering to the chaos game.
    It's a proven fact that all 'fractals' (maybe its not the right word to use) that can be created by an IFS model can also be created with a chaos game. It goes this way:
    Let's suppuse that the IFS model consist of the functions F1,F2,...,Fi.
    We select a random dot (p1), and then we select a random number between 1,2..i, let this number be 'r'. After that we 'use' the function Fr on our selected dot, and we get another dot (p2), then we select another random function and 'use' it on the dot p2 and so on.. and the dots will actually 'create' our fractal with the possibility of one. I'd like to get a mathematical proof on this. I've searched a lot on the internet and haven't found a correct proof on this.. So please help me..
    Please note that if possible I need a correct mathematical proof.
    And yeah I know my english sucks, so if someone actually knows the answer but doesn't understand my writings let me know
    thx in advance...


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    This seems like a trivial equivalence to me.

    Do you know anything about Monte Carlo methods? If not that might be a place to look for your answer.


    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  4. #3  
    Forum Freshman
    Join Date
    Jun 2006
    Posts
    5
    Well it's not trivial for me and certainly (spelling?!) i can't write it's trivial if my teacher asks about it in my exam . But no i haven't heard about the Monte Carlo methods you mentioned, maybe its my fault. But are those for proving things like this? Isn't there an easier proof? Anyway I'll look into it, thx for your reply!
    Reply With Quote  
     

  5. #4  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    There's a bit on this at

    www.cut-the-know.org/ctk/ifs.shtml

    The Barnsley reference there looks like a place to start, what I could see with google's search it looks like it has the relevant theorems and at least contains references to proofs.

    I don't see how this would be at all trivial without a bunch of machinery already built up, though I can't say I've seen a proof of this. I also don't see how monte carlo methods will help apart from some probability theory they have in common, but I might be missing something. I might be missing alot actually.

    How 'deep' is this course? I would expect if this is a proof you need to know and aren't at the point where you could have found it yourself, then it would have been covered in class. Definitely look it up, but you might want to ask your prof if it's something you need to worry about. Your prof certainly knows this stuff better than me and can probably suggest better sources as well.
    Reply With Quote  
     

  6. #5  
    Forum Radioactive Isotope mitchellmckain's Avatar
    Join Date
    Oct 2005
    Location
    Salt Lake City, UTAH, USA
    Posts
    3,112
    Yeah this is obviously one of the differences between the mathematician and the physicist. When something seems obvious to the physicist that often means that the mathematician suspects that there should be a proof and endeavors to make it, and the proof need not be easy. The physicist is more likely to forge ahead and let the mathematician back him up in this way. Of course if the mathematician should have trouble making a proof work, that might be reason for the physicist to consider whether his assumption might be wrong. Though for the physicist the final arbiter is not the mathematical proof but experimental confirmation, and so he may simply add a note to his work that mathematicians have yet to find an adequate proof of this particular point.

    Now if the mathematician were to prove the negative, THAT would be a different matter indeed! (cringe)

    Oh and my comment on Monte Carlo methods was only due to the fact that this was the only thing in my university work that sounded even remotely related to the question. I would take shmoe's advice over mine if I were you.
    See my physics of spaceflight simulator at http://www.relspace.astahost.com

    I now have a blog too: http://astahost.blogspot.com/
    Reply With Quote  
     

  7. #6  
    Forum Freshman
    Join Date
    Jun 2006
    Posts
    5
    I agree with mitchellmckain about the 'mathematician vs. physicist' thing. And yes I've seen a lot of java applets which simulate my problem and I've also seen that it works, but that is not a correct proof.
    According to my lecture the thing that I have to prove is that the two objects (one generated with IFS and the other with the chaos game) can get arbitrarily close to each other in the Hausdorff distance when doing more and more iterations. How to do this I don't know...
    I've searched through google a lot but no luck so far. Anyway thanks for the replies!
    Reply With Quote  
     

  8. #7  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by Pulse
    According to my lecture the thing that I have to prove is that the two objects (one generated with IFS and the other with the chaos game) can get arbitrarily close to each other in the Hausdorff distance when doing more and more iterations. How to do this I don't know...
    You chaos game produces a sequence p1, p2, p3, ... do you mean to show that the sequence of sets {p1}, {p1,p2}, {p1,p2,p3},.. converges to your fractal in the hausdorff metric? This won't be true if p1 is not in this set to begin with. You're going to have to somehow drop earlier points if you want convergence in the hausdorff metric, maybe consider the sequence of sets {pn,...p(2n)} say, or something else.

    Take a look at that Barnsley reference. It, and other snippets I found in google, use something called Elton's theorem, from an '87 paper "An ergodic theorem for iterated maps", Ergodic Theory Dynam. Systems, vol 7, pg 481-488. I haven't read it, but you might try there as well. The precise mathematical version they use for "the image the chaos game produces is the same as the IFS" is different than you're trying to do, but I would expect them to be related, if not actually equivalent (given a 'correct version' of sets to converge in the hausdorff metric), but I don't know for sure offhand.
    Reply With Quote  
     

  9. #8  
    Forum Freshman
    Join Date
    Jun 2006
    Posts
    5
    You chaos game produces a sequence p1, p2, p3, ... do you mean to show that the sequence of sets {p1}, {p1,p2}, {p1,p2,p3},.. converges to your fractal in the hausdorff metric?
    Yes thats what I wanted to say.

    This won't be true if p1 is not in this set to begin with.
    That is not exactly true because the IFS model consists of contractive functions (dunno if that's the word in english, it means that d(F(x),F(y))<=r*d(x,y), where r<1) and because of that the limes of the IFS will be the same no matter what set you start with.

    Anyway I found Falcon's Fractal Geometry book, which I'm going to get somehow and maybe find the answer there. And I made my exam today and wasn't asked about it luckily but it's still and interesting topic IMO.
    Reply With Quote  
     

  10. #9  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by Pulse
    That is not exactly true because the IFS model consists of contractive functions (dunno if that's the word in english, it means that d(F(x),F(y))<=r*d(x,y), where r<1) and because of that the limes of the IFS will be the same no matter what set you start with..
    Contractive is the right word. If A is your fractal, and d(,) the hausdorff metric then d({p1,p2,...pn},A)>=d({p1},A), no? If this is greater then 0 (whenever p1 is not in A), the sequence of sets like this from the chaos game won't converge. This goes with a practical simulation as well, the first few points aren't representative of your image, so you would want to toss more and more of the earlier ones for better approximations of A.
    Reply With Quote  
     

  11. #10  
    Forum Freshman
    Join Date
    Jun 2006
    Posts
    5
    If A is your fractal, and d(,) the hausdorff metric then d({p1,p2,...pn},A)>=d({p1},A), no? If this is greater then 0 (whenever p1 is not in A), the sequence of sets like this from the chaos game won't converge.
    Why would d({p1,p2,...pn},A)>=d({p1},A)? And d({p1},A) is always greater then 0 since p1 is only a dot. If a dot is in a set that doesnt mean that their Hausdorff metric is 0. Any metric of two objects can only be 0 if they're equal.
    Reply With Quote  
     

  12. #11  
    Forum Sophomore
    Join Date
    Jul 2005
    Posts
    121
    Quote Originally Posted by Pulse
    Why would d({p1,p2,...pn},A)>=d({p1},A)?And d({p1},A) is always greater then 0 since p1 is only a dot. If a dot is in a set that doesnt mean that their Hausdorff metric is 0. Any metric of two objects can only be 0 if they're equal.
    Sorry, I stupidly ended up using the same notation to mean two different things.

    Call K the distance from p1 to the set A. Then we have d({p1,p2,...,pn},A)>=K, and K>0 if p1 is not in A (where d(,) still the Hausdorff metric).
    Reply With Quote  
     

  13. #12  
    Suspended
    Join Date
    Nov 2013
    Location
    South Carolina
    Posts
    14
    Really? That was great! How does happened? Give me more evidence dude!
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •