The picture
contains 4096 points. We can estimate the probability of each of the 16 pairs by counting the number of points in the corresponding subsquare and dividing by 4096. In this way, we obtain
subsquare | number of points | conditional probability P(i|j) |
11 | 176 | P(1|1) = 0.0430 |
12 | 0 | P(1|2) = 0.0000 |
13 | 0 | P(1|3) = 0.0000 |
14 | 729 | P(1|4) = 0.1780 |
21 | 269 | P(2|1) = 0.0657 |
22 | 0 | P(2|2) = 0.0000 |
23 | 0 | P(2|3) = 0.0000 |
24 | 385 | P(2|4) = 0.0940 |
31 | 281 | P(3|1) = 0.0686 |
32 | 0 | P(3|2) = 0.0000 |
33 | 183 | P(3|3) = 0.0447 |
34 | 479 | P(3|4) = 0.1169 |
41 | 179 | P(4|1) = 0.0437 |
42 | 655 | P(4|2) = 0.1599 |
43 | 760 | P(4|3) = 0.1855 |
44 | 0 | P(4|4) = 0.0000 |
Given this information, what is the probability that 241 would not occur in a sequence of 4096 values? As a first approximation, we build a simple Markov process with four states:
A | 241 has not occurred, and the current string does not have left-most entries 1 or 41 |
B | 241 has not occurred, and the current string has left-most entry 1 |
C | 241 has not occurred, and the current string has left-most entries 41 |
D | 241 has occurred |
In the standard language of Markov processes, D is an "absorbing state." That is, once the string enters state D, it remains in state D. In terms of the driven IFS, entering state D means having points in square 241. So we would like to find the probability of not entering state D in a string of 4096 points. To do this, we first note the probabilities of making transitions among states A, B, and C. (Row labels are "from;" column labels are "to.")
A | B | C | |
A | 1 - (P(1|2) + P(1|3) + P(1|4)) | P(1|2) + P(1|3) + P(1|4) | 0 |
B | 1 - (P(1|1) + P(4|1)) | P(1|1) | P(4|1) |
C | 1 - (P(2|4) + P(1|4)) | P(1|4) | 0 |
Call this matrix of probabilities M. Represent the probabilities of being in states A, B, and C by PA, PB, and PC. As approximated by the conditional probabilities, the effect of one step of the process on the probabilities is the matrix product
[PA PB PC]M
The effect of 4096 steps is
[PA PB PC](M4096)
The empty string corresponds to the vector [1 0 0], and the probabilities of being in states A, B, or C for a string of length 4096 are given by the respective components of [1 0 0](M4096). Consequently, the probability that 241 will not occur in a string of length 4096 is just the sum of the probabilities of remaining in states A, B, and C. This probability is .071, so it is quite likely that the square 241 is empty because of a real restriction on the underlying dynamics.
Return to Depth of History