# Linear recurrence relation in Cantor-like sets

I have a linear recurrence relation $$a_i = \alpha_0 a_{i-1} + \beta(i)$$ Where $\beta(i) = \beta_0b_i$ with $b_i \in \{0,1\}^\mathbb N$

I know that $0 < \alpha_0 < \frac{1}{2}$, $\beta_0 = 1 - \alpha_0$ and $a_1 \in [0,1]$

How can I express $\lim_{i \to \infty}a_i$ in terms of $b_i$?

The best I can get currently seems to be $\lim_{n \to \infty} \sum_{i=0}^{n-2} (\alpha_0^{i}-\alpha_0^{i+1})b_{n-i}$

This problem came up when looking at the Middle-m cantor-like sets. These are sets defined by the IFS $\{ S_0,S_1 \}$ with the contractions $S_0(x)=\frac{(m-1)x}{2m}$ and $S_1(x)=\frac{(m-1)x + m + 1}{2m}$ I was pretty sure that $$lim_{n \to \infty}S_{b_n}\circ \dotsb \circ S_{b_0}([0,1])$$ should be a point on the set.

• Try the first few terms. Do you notice a pattern? – Semiclassical Jul 31 '14 at 17:04
• I seem to get $\lim_{n \to \infty} a_n = \lim_{n \to \infty} \sum_{i=0}^n \alpha_0^{i}\beta_0b_{n-i}$ – ruler501 Jul 31 '14 at 17:20
• ...hmm. That's odd: I don't see a limit that's independent of $b_n$ (which seems quite wrong.) – Semiclassical Jul 31 '14 at 17:23
• Answer I got seems to suggest a taylor series with $\alpha_0$ as the independent variable, but I'm not sure what could cause some terms to disappear like that though. I'm pretty sure it has to depend on $b_n$ At least that seems right to me. – ruler501 Jul 31 '14 at 17:26
• Well, it would mean that the limit would only exist if $b$ takes on some specific value as $n\to \infty$. That's what seems bizarre. – Semiclassical Jul 31 '14 at 17:28

## 1 Answer

Preliminaries

(I didn't have time to write this short, so I wrote it long.) I'll take your recurrence relation to be $$a_{i+1} = \alpha_0 a_{i} + (1-\alpha_0) b_i,\hspace{.5cm} a_1,b_i \in [0,1],$$ The slight shift in indices is just so that $b_1$ plays a role--right now $b_2$ is the first that matters, and I dislike the asymmetry. For the moment, I'll make no assumptions as to the sequence $\{b_i\}$.

To analyze this recurrence, I'll give a demonstration of the generating functions method in analytic combinatorics. We introduce the generating functions $$A(z)=\sum_{i=0}^\infty a_{i+1} z^i,\hspace{1cm} B(z)=\sum_{i=0}^\infty b_{i+1} z^{i}$$ We will consider these as formal power series in $z$; that is, we won't worry about their convergence or evaluation. Observe that we may write

\begin{align} A(z) &= a_1+\sum_{i=1}^\infty a_{i+1} z^i \\ &= a_1+\sum_{i=1}^\infty \Big[\alpha_0 a_{i} + (1-\alpha_0) b_i\Big]z^{i} \\ &= a_1+\alpha_0 \sum_{i=1}^\infty a_{i}z^{i} + (1-\alpha_0) \sum_{i=1}^\infty b_i z^{i}\\ &=a_1+\alpha_0 z A(z)+(1-\alpha_0)z B(z) \end{align} which we may solve for $A(z)$ as $$A(z)=\frac{a_1+(1-\alpha_0)z B(z)}{1-\alpha_0 z}=\frac{a_1}{1-\alpha_0 z}- B(z) \left(\frac{1-z}{1-\alpha_0 z}\right)+B(z).$$ What this means is that we can now find the power series for $A(z)$ (and therefore the relevant coefficients) by expanding the RHS.

Analysis of different $b_i$ sequences

Note, though, one issue: we've made now assumptions as to the behavior of $B(z)$. This is a problem, since the behavior of the high-order coefficients (i.e. $\lim_{n\to\infty} a_n$) depends greatly on the particular sequence of $b_i$. Three cases will demonstrate this point:

• Suppose $B(z)=0$ (i.e. all $b_i=0$). Then $A(z)=\dfrac{a_1}{1-\alpha_0 z}$ and therefore its $n$th coefficient is $a_n=[z^n]A(z)=a_1\alpha_0^n$. Hence the coefficients converge geometrically to zero from above.

• Suppose we instead want $b_i=1$ always. Then $B(z)=(1-z)^{-1}$ and therefore $A(z)=\dfrac{1}{1-z}-\dfrac{1-a_1}{1-\alpha_0 z}$ which gives coefficients $a_n=1-(1-a_1)\alpha_0^n$. Hence $a_n$ converges geometrically to 1 from below.

• Suppose $b_i$ flips from 0 to 1 indefinitely. Then $B(z)=(1-z^2)^{-1}$, and a (tedious) partial fractions decomposition gives $$A(z)=\frac{1}{1-\alpha_0 z}\left(a_1 -\frac{\alpha_0}{1+\alpha_0}\right) +\frac{1}{1+\alpha_0}\frac{1}{1+z}+\frac{1}{1-z^2}$$ which finally gives $$a_n=\left(a_1 -\frac{\alpha_0}{1+\alpha_0}\right)\alpha_0^n +\left\{ \begin{array}{cc} 1+\alpha_0^{-1} ,& n\text{ even}\\ 1+\alpha_0,& n\text{ odd} \end{array}\right\}^{-1}$$

The first term displays the familiar geometric convergence to zero. The second term, by contrast, remains finite and is different between even and odd $n$. That means that the even and odd subsequences converge to different values; in other words, as $n\to\infty$ the map converges to the limit 2-cycle $\left\{\dfrac{1}{1+\alpha_0^{-1}},\dfrac{1}{1+\alpha_0}\right\}$ for all $0 <\alpha_0 <\frac12$.

Conclusions

Such analysis may be carried out for other $\{b_i\}$, but one's patience is quickly exhausted. (A wiser approach is to do a singularity analysis of the generating function---see Flajolet & Sedgwick's Analytic Combinatorics for an extensive treatment.) What should be clear from this treatment is that different sequences create vastly different behavior, and one cannot guarantee convergence to a fixed point.

Which, upon reflection, is not so shocking: The first map sends $a_n\in[0,1]$ to $[0,\alpha_0]\subset[0,1]$; the second, to $[1-\alpha_0,1]$. (Note that these intervals are disjoint when $\alpha_0<\dfrac{1}{2}$.) So if we only do one of the maps, we surely get a fixed point; if we oscillate back and forth, we can only hope for a limit cycle. Higher periodicities presumably lead to limit cycles of greater (even) length. (I suspect that, if one takes $b_i$ to be a random variable, then the resulting behavior will be ergodic on $[0,\alpha_0]\cup[1-\alpha_0,1]$.)