next up previous
Next: Other sequences Up: Careful chaos: taming random Previous: Extraction of strings


Filter foibles

I claim that any ``nice'' IFS, $ W$ $ =$ $ w_1$ $ \cup$ $ \cdots$ $ \cup$ $ w_n$ (where each $ w_i$ is a contraction and the $ w_i$ are non-overlapping) corresponds to a choice of probabilities $ p_1$, $ \ldots$ $ p_n$ such that if $ S$ $ =$ $ i_1 \cdots i_k$ is a string with $ i_j$ $ \in$ $ \{1,\ldots, n\}$, the ratio

$\displaystyle \prod_{j=1}^k \left( p_{i_j}/ \text{Area}(i_1 \cdots i_k) \right) =
\text{constant}^k,
$

...where Area $ (i_1 \cdots i_k)$ denotes the image of the unit square under $ w_{i_1} \circ \cdots \circ w_{i_k}$. In other words for all addresses of a given length, the probability that a point lies in a particular address is proportional to the area of that address. This ensures (in the limit) equal densities at all addresses of the same length.

The converse may be true, but I don't see a ready proof. The contrapositive implies that our object constructed by driving the full square IFS with a random sequence lacking the substring ``12'' cannot be created by a ``nice'' IFS whose transformations map to sub-squares $ 1$, $ 2$, $ 3$, and $ 4$. A similar argument excludes IFSs based on smaller sub-squares, strongly suggesting that our object is not a ``really nice'' fractal.

Proof Let $ c_i$ be the contraction corresponding to $ w_i$, then $ c_i^2$ is $ \vert\det(w_i)\vert$. Let $ C$ $ =$ $ c_1^2$ $ +$ $ \cdots$ $ +$ $ c_n^2$, and let $ p_i$ $ =$ $ c_i^2/C$. Let $ U$ be a unit square containing our fixed point $ \mathcal{F}$, and so the area of $ w_i(U)$ is $ A(i)$ $ =$ $ c_i^2$, so you have

$\displaystyle \frac{p_i}{A(i)} = \frac{1}{C}.
$

For compositions $ w_{i_1}$ $ \circ$ $ \cdots$ $ \circ$ $ w_{i_k}$, you have

$\displaystyle \frac{p_{i_1} \cdots p_{i_k}}{A(i_1) \cdots A(i_k)} = \frac{1}{C^k}.
$

This is what I claimed.


next up previous
Next: Other sequences Up: Careful chaos: taming random Previous: Extraction of strings
Danny Heap 2001-05-18