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.

  • 1
    $\begingroup$ Try the first few terms. Do you notice a pattern? $\endgroup$ – Semiclassical Jul 31 '14 at 17:04
  • $\begingroup$ 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}$ $\endgroup$ – ruler501 Jul 31 '14 at 17:20
  • $\begingroup$ ...hmm. That's odd: I don't see a limit that's independent of $b_n$ (which seems quite wrong.) $\endgroup$ – Semiclassical Jul 31 '14 at 17:23
  • $\begingroup$ 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. $\endgroup$ – ruler501 Jul 31 '14 at 17:26
  • 1
    $\begingroup$ 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. $\endgroup$ – Semiclassical Jul 31 '14 at 17:28


(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$.


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]$.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.