Truncation of strings

The Fractal Sequence applet defaults to filter method ``T.'' In fact, any character other than $X$ will run this filter method. In our example, this method replaces every substring ``12'' by the substring ``1,'' and uses the result to drive the chaos game. This means that the resulting object has points in exactly those addresses that contain no substring ``21'' (addresses are read in the opposite direction from sequences).

I believe that the resulting object is a near-fractal. Clearly there is a good deal of self-similarity: sub-squares $1$, $3$, and $4$ are exact half-scale replicas of the entire object, but this similarity breaks down for sub-square $2$. Every attempt (of mine...) to describe this object using a finite set of affine transformations misses a small portion. Of course, the fact that I've been unable to find a suitable finite set of affine transformations doesn't prove that there are none. However, below (see Section 4) I prove there there is no `` really nice'' set of affine transformations that do the job, where by ``really nice'' I mean a finite set of affine transformations that are each a contraction, whose ranges are not overlapping, and whose ranges correspond to sub-squares of some finite size.

If you render this object in the Fractal Sequence applet using $p_1$ $=$ $p_2$ $=$ $p_3$ $=$ $p_4$ $=$ $0.25$, you'll find that some addresses appear denser than others. For example, addresses $11$, $31$, and $41$ are ``hot spots'' (dense), whereas $12$, $22$, $32$, and $42$ are considerably sparser (of course $21$ is empty). Does this reflect the structure of the object, or simply the choice of probabilities? I think the answer is the latter (the choice of probabilities) but it may not be possible to choose an optimal set of $p_i$s.

Here's my reasoning. Suppose $s_1$ and $s_2$ are two equal-length substrings over the digits $\{1,2,3,4\}$. If I denote the corresponding areas as $A_{s_1}$, and $A_{s_2}$ (the areas of those sub-squares with addresses $s_1$-reversed and $s_2$-reversed), I would like $p_{s_1}/A_{s_1}$ $=$ $p_{s_2}/A_{s_2}$. For strings of length $1$ this means that

$$\frac{p_2}{3/4} = p_i\qquad i = 1,3,4,$$

...since sub-square $2$ has about $3/4$ the area of sub-squares $1$, $3$, or $4$. And additional consideration is that my filtering method has removed about $1/3$ of the $2$s. To see this, notice that every block of one or more $2$s is terminated on the left by a $1$, $3$, or $4$. Those terminated by a $1$ are removed, roughly $1/3$. of the total. If I assume that $p_1$ $=$ $p_3$ $=$ $p_4$, so that $p_2$ $=$ $1-3p_1$, I require

$$\frac{(2/3)(1-3p_1)}{3/4} = p_1 \Longrightarrow p_1 = p_3 = p_4 \frac{8}{33}, \quad p_2 = \frac{3}{11}.$$

If you run the Fractal Sequence applet with $p_2$ $=$ $0.2728$ ($3/11$), and the remaining $p_i$ $=$ $0.2424$ ($8/33$), and the ``level'' (length of addresses to compare) set to $1$, you should see that this gives a fairly uniform density.

However ``hot-spots'' remain at addresses $11$, $31$, and $41$. To see why this occurs, notice that whenever a string $12$ is truncated by removing the one (or more) trailing $2$s, a new string $1\alpha$ is created, where $\alpha$ is one of $1$, $3$, or $4$ -- the non-$2$ character to the right of the block of $2$s. So the frequency of strings $1\alpha$ is increased, which corresponds to the number of points in addresses $\alpha 1$. Since these addresses have areas equivalent to $\alpha 3$ and $\alpha 4$, their relative density increases.

Is it possible to ``tweak'' the probabilities $p_i$ so that all the addresses of length $2$ are rendered with equal density? I don't think so, for the following reason. There are fifteen legal addresses of length $2$ (address $21$ is generated by a sequence that contains the forbidden substring). Among these fifteen, addresses $12$, $22$, $32$, and $42$ have $3/4$ the area of the others, since they each have a sub-square (e.g. $121$) removed. Recalling that sequences are read in the opposite order from addresses, this means that we'd like (after filtering) to end up with addresses $p_i$ so that:

$$p_2 p_2 = p_2 p_1 \Longrightarrow p_2 = p_1$$

$$p_2 p_1 = \frac{3}{4} p_1 p_1 \Longrightarrow p_2 = \frac{3p_1}{4}$$

$$.$$

These two equations are inconsistent, unless $p_2$ $=$ $p_1$ $=$ 0, which fails, since addresses $1$ and $2$ aren't empty. So, it is impossible to choose the $p_i$ so that their products have the required properties.