Homework Problems: MAT335 - Chaos, Fractals and Dynamics, Winter 2000

Handouts:

• 25 Feb (Chaos game)
• 28 Feb (Logistic function I)
• 3 Mar (Logistic function II)
• 6 Mar (Distribution of sequences/Random sequences)
• 13 Mar (graphical analysis)

• (1) Let W = w_1 U w_2 U ... U w_k be an IFS. We want to play the Chaos Game with this IFS. To that end, we need to find the 'rules' of the game, that is, the rules that tell us how to obtain the next point in the game. So suppose we roll the die (or whatever method is used to choose the transformation) and the transformation w_i is picked. If the current game point is z_0 show that the next game point z_1 is obtained by the formula z_1 = w_i(z_0) = q_i + A(z_0-q_i). Here q_i is the fixed point of the transformation w_i and A is the matrix appearing in the w_i: w_i = A + (e,f). Note that this generalizes the rules of the Sierpinski Chaos Game (in that case, A is just the diagonal matrix with diagonal entries 1/2).


• (2) Make a sketch of the general outline of the Cantor set and the Koch curve and indicate on your sketch by a square the subsquares with the following addresses: For Cantor; 112, 212, 211(11); for Koch; 12, 321, 22(22). Here (xy) means the digits xy are repeated indefinitely, so the last addresses for each will be denoted by a point instead of a square. (See pages 310-314 of the text.)


• (3) Find the addresses of all the 'subferns' on the first branch on the left side of the Barnsley Fern (Fig. 6.24). Note that there are infinitely many such subferns, but the pattern of their addresses will become apparent.


• (4) Recall that the transformation w_4 in the IFS for the Barnsley Fern produces the main stem of the fern (see Figures 5.35, 5.48 and 6.24). So each time the IFS is iterated, a new segment of the main stem is produced (this is the image of the stem of the previous stage under the transformation w_1; look closely at Figure 6.24). Suppose the Chaos Game is played with 100,000 iterations.
  (a) Find the number of game points that will appear on each segment of the stem. (You will first need to find the addresses of these segments.)
  (b) At what level, i.e., how high up the main stem (which segment), do you expect no game points to appear? (So this will be the height of the fern with this many iterations.)
  Answer (a) and (b) both in the case with equal probabilities (i.e., p_i = 1/4 for i = 1,2,3,4), and for the probabilities p_1 = .85, p_2 = p_3 = p_4 = .05.


• (5) Consider the fractals given in Figures 5.10 - 5.16. For each one of them, give the probabilities p_i that you think would draw the fractal the most efficiently using the chaos game. You don't have to give any values for the probabilities, just list them from smallest to largest (for example; p_1 = p_2 = p_3, or p_1 < p_2 < p_3). You will have to consult Table 5.60 to determine the numbering of the w_i (and hence the numbering of the p_i). Note too that for a matrix A, the quantity (square root of |det(A)|) is the ratio of areas of final image to initial image under the transformation A, i.e., square root (|det(A)|) = [area (A(S))]/[area (S)] , so by calculating the determinants of the transformations listed in Table 5.60, you can tell which one is most contracting, etc, and this will also help you in identifying which transformation is responsible for which part of the blue print (in Figures 5.10 -5.16).
• (6) (A) How many times do you expect to have to choose a number randomly from {1,2,3} before the string 1,2,3 appears if (i) p_i = 1/3 (for each i), (ii) p_1 - .5, p_2 = .3, p_3 = .2 ?
  (B) If we play the chaos game with an IFS W = w_1 U w_2 U w_3 up to 100,000 steps, how many times will the string of transformations w_3 w_2 w_1 occur in the game where the probabilities (i) are used, and in the game where probabilities (ii) are used?
• (7) What image results if we play the chaos game for the Sierpinski triangle with probabilities p_1 = 1/2, p_2 = 1/2, p_3 = 0?
• (8) What can you say about the image produced by the chaos game for the Sierpinski triangle (p_i > 0 but otherwise arbitrary) if the string 1,2,3 never occurs in the sequence {s1_, s_2, s_3, ... }? (Note: This string has a zero chance of being realized. Still, there is such a sequence.) Hint: Think of addresses.
• (9) (A) What image results if we play the chaos game for the Sierpinski triange with the sequence {s_1, s_2, s_3, ... } = {1,2,3,1,2,3, ...} ( 1,2,3 repeating)? Here, take the initial point z_0 to be the fixed point (.5, 1) at the top of the triangle. To get an idea of what the image may be, sketch the first few points of the game. But by using addresses you will be able to say exactly what the image is.
  (B) If we repeat this game many times using the same sequence {1,2,3,1,2,3, ...} but varying the initial point z_0 throughout the entire Sierpinski triangle and combine all the images, what picture results? (This can be answered exactly using addresses.)
• (10) (A) Explain why a periodic orbit (of any period) is not ergodic.

(B) Suppose that {y_n} is a sequence of numbers between 0 and 1 that has a continuous distribution function v(x) and that v(x) > 0. Show that {y_n} is ergodic. (Hint: If P(y_i; J) is the probability that the point y_i from the sequence {y_n} is in the set J, then if P(y_i; J) > 0, such a point y_i will occur somewhere in the sequence.)
• (11) Explain why the logistic function for a = 3.3 is not mixing.
• (12) (Refer to the handout 6 March) Consider the sequence {1,2,3,1,2,3,1,2,3, ... }. Would you say this is a random sequence of 1's, 2's, and 3's ? Substantiate your answer by identifying a probability distribution p_1, p_2, p_3; p_1 + p_2 + p_3 = 1, that this sequence satisfies and "testing" the sequence for randomness.
• (13) Draw a simple diagram (like the one I did in class, which is like Figure 10.29 in the text) to show that stretch-and-fold leads to mixing.
• (14) Let g(x) = x^3. (A) What are the period 1 orbits of g?
  (B) Does g have any other periodic orbits?
• (15) Find all the period 3 orbits of T~ (this is the transformation on sequences that "shifts left" or "shifts left then conjugates" depending on whether a_1 is 0 or 1).
• (16) In our proof that the Tent transformation T has an ergodic orbit, we noted that the sequence a = a_1 a_2 a_3 ... contains the two finite sequences (i) b_1 ... b_k b*_1 ... b*_k and (ii) b_1 ... b_k b_1 ... b_k (here b*_i denotes the conjugate of b_i). Verify that (T~)^k(a) (the shift or shift-and-conjugate transformation T~ composed k times acting on the sequence a), begins with b_1 ... b_k by considering the finite sequence (i) in the case b_1 ... b_k preserves parity, and by considering the finite sequence (ii) in the case b_1 ... b_k reverses parity.
• (17) If x_0 is a number in [0,1] such that the orbit {x_0, T(x_0), T^2(x_0), ... } is periodic (of any period), then we call x_0 a periodic point of T (here T is the Tent transformation). Prove that the periodic points of T are dense in [0,1], i.e., if x is any number in [0,1] and e>0 is any (small) positive number, then there is a periodic point y of T (of some period) such that |x - y| < e.
• (18) Use the Shadowing Lemma to conclude that the observed instability of periodic orbits of the logistic function 4x(1-x) implies that the exact periodic orbits are in fact unstable. (Here, observed means the results from computer calculations, and exact means the theoretical result.)
• (19) Consider the logistic function f(x) = (3x/2)*(1-x). Use graphical analysis to show that the fixed points of f are 0 and 1/3 and that W_s(0) = {0,1}, W_s(1/3) = (0,1), W_s(-infinity) = (-infinity, 0) U (1, infinity) (here, W_s denotes the stable set). Can you find the points that are "eventually fixed"? i.e., points x such that f(x) = 0 or 1/3 (there are 4 of them including 0 and 1/3).

Back to the MAT335 homepage