Answer to Exercise 1Exercise 1: Iterate the following system: x(n+1) = 2x(n) mod 1. [By "mod 1" is meant that only the fractional part of the result is kept. For example, 3.1416 mod 1 = .1416.] Is this system chaotic? To get a feel for how the system behaves, let’s first iterate a few values. Start with x(0) = .1. We get x(1) = 2(.1) mod 1 = .2 mod 1 = .2 . This is the first iteration. This and the following iterations are listed in the table:
And so on. The values of x cycle through .6, .2, .4, .8, over and over. Now let x(0) = 1.25. What values to we get? The first iteration is x(1) = 2(1.25) mod 1 = 2.50 mod 1 = .50. The second iteration is x(2) = 2(.5) mod 1 = 1 mod 1 = 0. The third iteration is x(3) = 2(0) mod 1 = 0 mod 1 = 0. Once at zero, the system stays there.
Because all values are taken mod 1, we drop (chop off) anything to the left of the decimal point. So we are really only concerned with numbers between 0 and 1. Suppose we write each of the numbers between 0 and 1, not in the decimal system, but in the binary system. The binary system uses only 0s and 1s, which represent powers of 2. Consider, for example, the binary number .1101 . The first place to the right of the "decimal point" represents ½. The next place represents ¼ . The third place represents 1/8 . And so on. The n-th place represents 1/2n . So .1101 = 1 x ½ + 1 x ¼ + 0 x 1/8 + 1 x 1/16 = ½ + ¼ + 1/16 = 13/16. The binary .0011 = 0 x ½ + 0 x ¼ + 1 x 1/8 + 1 x 1/16 = 3/16. Now, this may look like we’ve made things more complicated, but actually we’ve made them extremely simple. What happens when we multiply by 2? Well, since the n-th decimal place represents 1/2n , if we multiply it by 2, we have 2 x 1/2n = 1/2n-1 . This is the (n-1)-th place to the right of the decimal point, or one place closer. So take .1101. To multiply it by 2, we move the decimal point one place to the right and get 1.101 . We then apply mod 1, which chops off everything to the left of the decimal point and get .101 . Multiply by 2 again, we get .01. Then multiply by 2 again, we get .1 Finally, one more multiplication, and we get 0. So the first observation we can make about the system x(n+1) = 2 x(n) mod 1, is that if the binary expansion of x(0) is finite, the system converges to 0. This is obvious, because if we chop off one binary digit with each iteration, we eventually run out of binary digits, if the number of binary digits is finite. Any fractional power of 2 will have a finite decimal expansion, and hence these values will converge to zero. (A fractional power of 2 is a fraction p/q where q = 2n for some n. For example, 3/256, which in binary is .00000011.) In our first example, we started with x = .1 (where here .1 was a decimal value, or 1/10). Let’s expand 1/10 into binary: .00011001100110011001… After the first 4 iterations, which chops off the leading 0001, we are left with a repeating 1001, 1001, 1001, etc. This is an infinite binary number, so it doesn’t get any shorter as we chop off places. So we cycle through the same four numbers over and over. Namely, the four numbers corresponding to: .10011001100110011001…
These correspond to the decimal numbers .6, .2, .4, .8, as we saw previously in the table. All rational numbers (p/q, where q is not zero) that are not fractional powers of 2 (i.e., q is not a power of 2) will eventually cycle. For example, the starting decimal x(0) = .71 begins to cycle after 21 iterations. We have x(22) = x(2) = .84, x(23) = x(3) = .68, and so on. The starting decimal x(0) = .7182 begins to cycle after 502 iterations. We have x(503) = x(3) = .7456. What if we start with an an irrational number, such as the square root of two, or p? Clearly these have non-repeating binary expansions, so the system is chaotic if x(0) is irrational.
|