• (1a): Let {y₀, y₁, y₂, . . . } be a sequence constructed by the following procedure:
  • Choose y₀ to be any integer.
  • Roll a 1-2-3 die; let this number be z₁. (A 1-2-3 die is a six-sided cube with a 1 on two sides, a 2 on two sides, and a 3 on two sides.) Then y₁ = y₀ + z₁.
  • Roll the die again; let this number be z₂. Then y₂ = y₁ + z₂.
  • Repeat this procedure to obtain y₃, y₄, . . . .
  (This is an example of a random (or stochastic) sequence.)
  Suppose y₀=0. What are the possible values of y₁, y₂, and y₃? Compute the probabilities of each possible value too. Can you predict the value of any y_n? Explain.
(1b): Let {x₀, x₁, x₂, . . . } be a sequence constructed by the following procedure:
• Choose x₀ to be any integer.
• Then for each n = 1, 2, 3, . . . , let x_n = 3x_n-1 + 2.
(This is an example of a deterministic sequence.)
Suppose x₀ = 1. Show that x_n, for any n = 1, 2, 3, . . . is determined uniquely by the value of x₀ by finding a formula for x_n: x_n = h(n).

Recall that a periodic point x of period k is stable if |(f ^k)'(x)| < 1, and is unstable if |(f ^k)'(x)| > 1.

Suppose that x is a periodic point of f(x) of period k, and that {x, x₁, x₂, . . . , x _k-1, x, x₁, . . . } is the orbit of x.

• (2a): Use the Chain Rule to show that (f ^k)'(x) = f '(x)*f '(x₁)*f '(x₂)* . . . *f '(x _k-1) (the star, *, denotes multiplication).
• (2b): Prove that if x_i is any point in the orbit of x, then (f ^k)'(x_i) = (f ^k)'(x) (so it doesn't matter which point you pick in the orbit to determine stability). (Hint: Use part (a).)
• (2c): Recall that if x is a periodic point of f of period k, then x is a periodic point of f of period 2k, 3k, . . . (x may also be a periodic point of f of period k/2, or k/3, or k/4, etc). Can the stability of x as a periodic point of period k be different than the stability of x as a periodic point of some other period?

Recall from the handout, Experiments with the Logistic Function, that the (stable) period 1 orbit of the logistic function split into a (stable) period 2 orbit at a = 3, then this period 2 orbit split into a (stable) period 4 orbit at a = 3.5, and that this period 4 orbit split into a (stable) period 8 orbit at around a = 3.56. (I put stable in parenthesis because the other periodic orbits are still there but they are now unstable so the time series experiment doesn't see them, eg., when the period 4 orbit appears the period 2 orbit is still there but it has become unstable, etc - you can check using the applet Bifurcation that those unstable orbits are indeed there by looking at the graphs of f ², f ⁴ and f ⁸).

On page 4 of the Experiments with Logistic handout we see a period 8 orbit for a = 3.56 (note that the parameter r on that handout is the parameter a we have been using in these notes). On the handout is indicated the ordering of the points in the orbit (in particular, the orbit is {0.889, 0.349, 0.809, 0.551, 0.881, 0.373, 0.833, 0.494, etc}). Explain this ordering by going back to the period 2 orbit and how this gave the ordering for the period 4 orbit that appeared which in turn gave the ordering for the period 8 orbit. You will use the applet Bifurcation to analyse the graphs of f ², f ⁴, and f ⁸. (In other words, why isn't the period 8 orbit ordered like {0.349, 0.373, 0.551, 0.494, 0.889, 0.833, 0.809, 0.881 etc } for example?)

Use graphical iteration to study the orbits of the following functions (i.e., find any fixed points and determine their stability and stable sets);

• g_a(x) = x³ + ax for a = -2, 0 and 2. Here are plots of the graphs: a = -2, a = 0, a = 2.
  
• f(x) = (1/2)x² + 2x - 2. How many points of period 1 does f(x) have (i.e., fixed points)? How many points of prime period 2 does f(x) have? How many points of prime period 3 does f(x) have? What is the stability of these periodic points and what are their stable sets? (Be careful; the stable sets of some points here are more complicated than they may first appear, and the stable sets of some unstable points here may be larger than just the point themselves (the stable set W_s(x)of a point x is the set of points whose orbit approach x, so x is always in W_s(x), and if x is a stable point then some neighborhood of x is in W_s(x), but if x is an unstable point (so nearby points move away from x) there may still be points in W_s(x) other than x - these points come from 'far away' from x).
  Here are plots of the graphs: f(x), f ²(x), f ³(x), and all functions at once.
  For reference, a line of slope -1 has been added to the plot of f(x) and f ³(x) passing through the fixed point near x = -3.
  If you are unsure of the stability of a periodic point, try calculating some orbits.

• (5a*): Sketch the graph of a function f(x) that has the period 4 orbit {-1,1,2,3} and such that this orbit is unstable.
• (5b*): Sketch the graph of a function g(x) that has the period 4 orbit {-1,1,2,3} and such that this orbit is stable.

Make sure you verify that your orbits are stable and unstable (see question (2)).
(See the notes, Graphical Analysis, page 3.)
Use graphical iteration to verify that {-1,1,2,3} is indeed an orbit of your function.

Suppose a point x is a periodic point of a function f(x) with period k. What other periods could x possibly have? (Hint: Consider the prime factorization of k.) Conclude that if k is a prime number, then k is the prime period of x (recall that the prime period of x is the smallest integer m such that x has period m). Don't forget that 1 is not a prime number! .....

Sketch the graph of a function f(x) that has a fixed point p and such that

• (7a): f '(p) = +1 and p is a stable fixed point of f.
• (7b): f '(p) = +1 and p is an unstable fixed point of f.
• (7c): f '(p) = -1 and p is a stable fixed point of f.
• (7d): f '(p) = -1 and p is an unstable fixed point of f.
• (7e): f '(p) = +1 and p is neither stable nor unstable.
• (7f): f '(p) = -1 and p is neither stable nor unstable.

Verify your answer by graphical iteration.

We have seen that for some parameter a values, the logistic equation f_a(x) = ax(1-x) has orbits whose histograms 'fill out' an interval. Let's consider for example the case when a=4. Then all orbits appear to fill out the entire interval [0,1] (see Figure 10.17 on page 526, which is the histogram of an orbit). Now, if you construct a random sequence of numbers from [0,1] (i.e., each number x _n is from [0,1] and is picked randomly according to some distribution v(x) that is never 0 on [0,1]; see the handout Random Sequences ), then that sequence too will fill out the interval [0,1]. So in this sense the deterministic sequence constructed from the logistic equation and the random sequence look similar (in fact, such sequences from the logistic function were used as random sequences, but didn't work).

But is a sequence {x₀, x₁, x₂, . . . }, an orbit of f₄(x), a random sequence? Can you come up with a 'test' that may tell you if this sequence is random or not? (there are infinitely many such tests, actually; see page 4 of the handout 'Random Sequences'). Is randomness more than just the distribution of points of a sequence? (Yes! it is also the order of the points).

References for this question: the handout, Random Sequences and Section 6.4 in the text (where they play the Sierpinski chaos game with a sequence generated by the logistic equation; you can use the chaos game to 'test' the randomness of a sequence).

Let f(x) = 4x(1-x). By studying the graphs of f(x), f ²(x), f ³(x), f ⁴(x), f ⁵(x), and f ⁶(x), along with the diagonal y = x, show that f(x) has a periodic point of prime period 2, a periodic point of prime period 4, and a periodic point of prime period 6. Why does f(x) have a periodic point of prime period 3 and prime period 5? (you can use problem (6) to answer this last question too.) Show that in fact f(x) has two (distinct) period 3 orbits and three (distinct) period 4 orbits (Hint: How many period three and period 4 points does f have?). Notice that I am asking how many distinct periodic orbits f has, not how many distinct periodic points f has.
How many (distinct) period 6 orbits does f have?
In all these questions you should realize that every point in a period k orbit will be a fixed point of f ^k, and conversely that every fixed point of f ^k belongs to a period k orbit.

Here are the graphs of [f ³, f], [f ⁴, f ²], and [f ⁶, f ³, f ²] (although you should be able to sketch them without the use of a computer by first locating the 'peaks'of f ^k via 'backwards graphical iteration' of the point 1/2 (which is the peak of f) ). Click on the image to obtain a larger image in a new window:

Find an orbit of T ^~ (the transformation on binary sequences; see equation (10.9) on page 540) with prime period 3. Use your answer to find a periodic point of f(x) = 4x(1-x) with prime period 3. Use the applet Graphical Iteration to verify your answer and to study the stability of this periodic orbit.

Find a periodic point of T that lies in the interval [9/32, 10/32], and from this find a periodic point of f(x)=4x(1-x) that lies in the interval [0.1828, 0.2222]. (Hint: Start with the binary expansions of 9/32 and 10/32 and consider T ^~.) What is the smallest period such a point can have? The longest period?

• (10a*) What are the parities of the following sequences; .11101 and .01100 ?
• (10b) Prove that if the string c=c₁...c_k preserves (reverses) parity, then c*=c*₁...c*_k (the conjugate (or 'dual' as they say in the text) of c) reverses (perserves) parity.

Back to the MAT 335 Home Page