text:
\section{Introduction}

Nowadays, computers are being widely used to generate images
in the analysis and simulations of real-life processes and their
mathematical models. A natural issue is to measure the complexity
of drawing a set of points on a computer, which describes a continuous
object at a given precision.
Particular examples of complex objects are fractal sets which arise in many contexts \cite{fractalbook}.
Well-known examples of fractal sets are strange attractors of dissipative dynamical systems and Julia sets.
Another way to generate fractal sets is to use iterated function systems \cite{barnsley}.

The way we measure the complexity of a (compact) set can be
colloquially described as follows. We define the $\varepsilon$-distortion
complexity of a set $\mathscr{C}$ as the minimal length of the programs
producing a finite set $\varepsilon$-close to $\mathscr{C}$, in the sense of
Hausdorff distance. As in the classical notion of Kolmogorov complexity of sequences,
by programs we mean programs running on a universal Turing machine \cite{li-vit}.
We are interested in the behavior of  the $\varepsilon$-distortion
complexity when $\varepsilon$ is getting small, and in eventual relations of this behavior
with other characteristics of the set ({\em e.g.}, fractal dimension).

In the present article we consider various classes of Cantor sets on the real
line generated by iterated function systems (IFS's) \cite{barnsley} and
compute bounds from above and below of their $\varepsilon$-distortion
complexity as a function of $\varepsilon$.
We first consider IFS's with polynomial contractions and obtain the upper bound
$const\times\log(\varepsilon^{-1})$ for the $\varepsilon$-distortion
complexity of the generated Cantor set, where the (finite) constant may depend on the polynomials.
We can produce ``many'' polynomial IFS's
with a lower bound of the same order using a probabilistic construction.
It turns out  that some particular Cantor sets like the usual middle
third Cantor set are of much lower complexity.
For analytic IFS's, we obtain the upper bound $const\times (\log(\varepsilon^{-1}))^2$.
Next we consider random central Cantor sets produced by affine IFS's,
for which the contraction rate is chosen at random at each step of
the construction. In this case, we get the upper bound
$const\times(\log(\varepsilon^{-1}))^2$ and the lower bound
$const\times(\log(\varepsilon^{-1}))^{2-\delta}$,
for any $\delta>0$, for almost all such Cantor sets (where the constant in our bound depends on $\delta$
and tends to $0$ when $\delta\to 0$). Finally, we
consider $C^k$ IFS's. Contrarily to the previous cases, the leading, asymptotic behavior
of the $\varepsilon$-distortion complexity depends on the box counting
dimension $D$ of the generated Cantor set. Indeed, we obtain the upper
bound $const\times\varepsilon^{-\frac{D}{k}-\delta}$, for any $\delta>0$ (where the constant in our bound depends on $\delta$
and blows up when $\delta\to 0$).
We then construct ``many'' $C^k$ (random) Cantor sets
with a lower bound $const\times\varepsilon^{-\frac{D}{k}+\delta}$ (for any $\delta>0$),
by constructing their scaling function \cite{sullivan}.

The case of sets reduced to one point on the line was investigated in \cite{cai} where in particular the Hausdorff dimension
of the set of reals with given asymptotic complexity is computed.
For graphs of functions, from the point of view of determining the values of a function at given precision, relations
with $\varepsilon$-entropy are obtained in \cite{asarin}.
Another notion of complexity is to ask about the smallest execution time of the programs  generating a given set with $\varepsilon$-precision,
in the sense of Hausdorff distance \cite{W}. This was used in \cite{braverman} to show that a class of Julia sets
was polynomial time computable.

This article is organized as follows. In Section \ref{definition}
we define the $\varepsilon$-distortion complexity of a compact set and
state our results. Section \ref{allproofs} is devoted to the proofs.

\section{Definitions and results} \label{definition}

For a compact set $\mathscr{C} \subset \mathbb R^d$, we define its \emph{$\varepsilon$-distortion
complexity} as follows.

\begin{defn}
The $\varepsilon$-distortion complexity of a compact set $\mathscr{C} \subset
\mathbb R^d$ at precision $\varepsilon>0$ is defined by
$$
\Delta(\mathscr{C},\varepsilon)=\min\left\{ \ell(\mathtt{P}) : d_{\scriptscriptstyle{\mathrm{H}}}(\mathtt{C}(\mathtt{P}),\mathscr{C})<\varepsilon
\right\}\ ,
$$
where the minimum is taken over all binary programs $\mathtt{P} \in
\set{0,1}^*$ running on a universal Turing machine $U$, which
produce a finite subset $\mathtt{C}(\mathtt{P}) \in \mathbb R^d$; $\ell(\mathtt{P})$ is the
program length; $d_{\scriptscriptstyle{\mathrm{H}}}$ denotes the Hausdorff distance.
\end{defn}

Notice that, because of the compactness of $\mathscr{C}$, we can
use a minimum in the above definition, which always leads to a
finite number.

For the reader's convenience, we recall that the Hausdorff distance $d_{\scriptscriptstyle{\mathrm{H}}}$
between two closed subsets $F_1,F_2$ of a metric space with metric $d$ is
given by (see, {\em e.g.}, \cite{mattila,barnsley})
$$
d_{\scriptscriptstyle{\mathrm{H}}}(F_1,F_2)=\max\{ \sup_{x_2\in F_2} d(x_2,F_1),\sup_{x_1\in F_1} d(x_1,F_2)\} .
$$

\begin{remark}
If $T$ is a bi-Lipschitz map, there exist two positive constants $c_1,c_2$ such that, if
$\mathscr{C}$ is a compact set, we have
$$
\Delta(T(\mathscr{C}),c_1 \varepsilon)\leq \Delta(\mathscr{C},\varepsilon) \leq \Delta(T(\mathscr{C}),c_2 \varepsilon) .
$$
\end{remark}

We now recall the definition of Cantor sets generated by iterated
function systems \cite{barnsley}.
For the sake of simplicity, we restrict ourselves to Cantor sets in the unit
interval $[0,1]\subset \mathbb R$, although several results can be easily
generalised to arbitrary finite dimension.

Let $A=[0,1]$ and let $\mathcal{I}$ be a finite set of indices with at
least two elements. An \emph{Iterated Function System} (IFS for
short) is a collection
$$
\set{\phi_i : A \to A  : i\in \mathcal{I}}
$$
of injective contractions on $A$ with uniform contraction rate
$\rho \in (0,1)$, and such that $\phi_i(A) \cap \phi_j(A) =
\emptyset$ for $i\not= j$.

For any infinite word $\omega \in \mathcal{I}^\infty$ and for any $n\in
\mathbb N$, let $\omega_1^n \in \mathcal{I}^n$ denote the prefix of length $n$
given by the first $n$ symbols of $\omega$, and let
\begin{equation} \label{ifs-finite}
\phi_{_{\omega_1^n}} := \phi_{\omega_n} \circ \phi_{\omega_{n-1}}
\circ \dots \circ \phi_{\omega_1}.
\end{equation}
The map $\pi:\mathcal{I}^\infty \to A$ defined by
$
\omega \mapsto \pi(\omega):= \bigcap_{n=0}^\infty \
\phi_{_{\omega_1^n}}(A)
$
is continuous (in product topology) and, since
$$
\hbox{diam } (\phi_{_{\omega_1^n}} (A)) \le \rho^n \hbox{ diam }(A),
$$
$\pi(\omega)$ is a point in $A$ for all $\omega \in \mathcal{I}^\infty$.
The set
$$
\mathscr{C}:= \pi(\mathcal{I}^\infty) = \bigcup_{\omega \in \mathcal{I}^\infty}\
\bigcap_{n=0}^\infty \ \phi_{_{\omega_1^n}}(A)
$$
is a Cantor set and satisfies
\begin{equation} \label{ifs-prop}
\mathscr{C} = \bigcup_{i\in \mathcal{I}} \ \phi_i(\mathscr{C}).
\end{equation}

We are interested in the behaviour of $\Delta(\mathscr{C},\varepsilon)$ when
$\varepsilon$ tends to zero. Note that this is a monotone decreasing
function.

\begin{notation}
In the sequel we write $f\asymp g$ if there are two positive
constants $C_1$ and $C_2$ such that for any $\varepsilon>0$ small enough
$$
C_1 f(\varepsilon)\le g(\varepsilon)\le C_2 f(\varepsilon).
$$
We write $f\preccurlyeq g$ if there is a positive constant $C$
such that for any $\varepsilon>0$ small enough
$$
f(\varepsilon)\le C g(\varepsilon).
$$
\end{notation}

\bigskip

Our first result deals with polynomial IFS's.
\begin{thm} \label{thm:pol}
Let $\mathscr{C}$ be a Cantor set generated by an IFS with polynomial
functions. Then
\begin{equation} \label{pol-1}
\Delta(\mathscr{C},\varepsilon) \preccurlyeq \log(\varepsilon^{-1}).
\end{equation}
Moreover, for any $\delta>0$, there exist (many) polynomial IFS's
such that the generated Cantor set satisfies
\begin{equation} \label{pol-2}
(1-\delta) \log(\varepsilon^{-1}) \leq \Delta(\mathscr{C},\varepsilon).
\end{equation}
\end{thm}

\begin{remark} A more precise upper bound follows easily from the
proof, namely
$$
\Delta(\mathscr{C},\varepsilon) \le \left( \sum_{i\in \mathcal{I}}  (1+ \textup{deg}\
\phi_i) \right)\ \log(\varepsilon^{-1}) + o(\log(\varepsilon^{-1})).
$$
A more precise lower bound of the same kind can also be obtained for a
large class of Cantor sets which are generated by a set of full measure of
some random polynomial IFS's (see below for the definition of a random IFS).
\end{remark}

\begin{remark}
The classical examples of Cantor sets are the middle $\frac 1
\rho$-th Cantor sets in the unit interval ($\rho=\frac 1 3$ gives
the usual middle third Cantor set). They can be thought of as
generated by IFS with affine contractions $\phi_0$ and $\phi_1$,
and contraction rate $\rho$. For these Cantor sets, all
we need for their construction is the knowledge of $\varepsilon$ and of $\rho$.
We can choose $\varepsilon$ to be a number of low complexity.
In the particular case where $\rho$ is rational, $\Delta(\mathscr{C},\varepsilon)$ grows slower
than any unbounded partial recursive function.
\footnote{We thank Arnaldo Mandel for this observation.}
\end{remark}

\begin{remark}
Notice that there are examples of Cantor sets with low
$\varepsilon$-distortion complexity which contain numbers of high
complexity. This happens for example in the middle third Cantor
set.
\end{remark}

Our next result is about real analytic IFS's.

\begin{thm} \label{thm:analytic}
Let $\mathscr{C}$ be a Cantor set generated by an IFS with real analytic
functions. Then
$$
\Delta(\mathscr{C},\varepsilon)\preccurlyeq \big(\log(\varepsilon^{-1})\big)^2.
$$
\end{thm}

\bigskip

We now turn to random affine IFS's, for which at each step of the
construction we consider a random choice for the contraction rate.
For the definition we follow \cite{bamon}.

Let us consider a family $(\lambda_k)_{k\in \mathbb N}$ of
independent identically distributed random variables with values
in the interval $(0,1)$. To each sequence
$\lambda=(\lambda_k)_{k\in\mathbb N}$ we associate a Cantor set $\mathscr{C}$ in
the following way. Let $C^0_\lambda := [0,1]$. We define
$$
J^1_1(\lambda) := \left[0,\frac{\lambda_1}{2}\right],\
J^1_2(\lambda):= \left[1- \frac{\lambda_1}{2},1\right],
\ \textup{and}\
C^1_\lambda := J^1_1(\lambda) \cup J^1_2(\lambda) .
$$
In words, $C^1_\lambda$ is obtained by removing the central interval
of length $(1-\lambda_1)$ from $C^0_\lambda$. At the $(k+1)$-st step,
we delete from each interval $J^k_i(\lambda)$, $i=1,\dots,2^k$,
the central interval of length $(1-\lambda_{k+1})$, obtaining
$2^{k+1}$ intervals $J^{k+1}_i(\lambda)$, $i=1,\dots, 2^{k+1}$,
such that
\begin{equation} \label{rand-cantor-length}
|J^{k+1}_i(\lambda)|= \frac{1}{2^{k+1}} \prod_{h=1}^{k+1}
\lambda_h \qquad \forall  i=1,\dots,2^{k+1}.
\end{equation}
Then we define
$$
C^{k+1}_\lambda := \bigcup_{i=1}^{2^{k+1}} J^{k+1}_i(\lambda).
$$
We call \emph{random central Cantor set} the set
$$
\mathscr{C}_\lambda := \bigcap_{k=0}^\infty C^k_\lambda.
$$
We remark that by construction the boundary points $\partial
J^k_i(\lambda)$ of all the intervals $J^k_i(\lambda)$ are
contained in $\mathscr{C}_\lambda$.

The next theorem states that random central Cantor sets need more information
than those generated by polynomial IFS's.

\begin{thm} \label{thm-centcanrand}
Let $\mathscr{C}_\lambda$ be a random central Cantor set as described above.
Then, for any $\lambda \in (0,1)^\mathbb N$,
\begin{equation} \label{rand-1}
\Delta(\mathscr{C}_\lambda,\varepsilon) \preccurlyeq
\left(\log(\varepsilon^{-1})\right)^{2}.
\end{equation}
Moreover, let us assume that the common distribution of the i.i.d. random
variables $(\lambda_k)$ is absolutely continuous, with a density
$f(x)$ bounded above and below away from zero. Then, for any
$\delta >0$, we have
\begin{equation} \label{rand-2}
\left( \log(\varepsilon^{-1})\right)^{2-\delta} \preccurlyeq
\Delta(\mathscr{C}_\lambda,\varepsilon)
\end{equation}
for almost every $\lambda \in (0,1)^\mathbb N$.
\end{thm}

We now consider Cantor sets with a differentiable structure.
Following \cite{sullivan}, \cite{feliks} and \cite{bedford}, this
corresponds to Cantor sets generated by $C^k$ IFS's and we call
them $C^k$ Cantor sets. We shall recall their contruction in
Subsection \ref{sec:ck-central}.

\begin{thm}\label{thm:ckupper}
Let $k\ge 1$. For any $\delta>0$, for any $C^k$ Cantor set $\mathscr{C}$ with
box counting dimension $D$, we have
\begin{equation} \label{ck-1}
\Delta(\mathscr{C},\varepsilon)\preccurlyeq \varepsilon^{-\frac D k -\delta}.
\end{equation}
Moreover, for any $\delta>0$, there exist (many) $C^{k}$ central
Cantor sets $\mathscr{C}$ with box counting dimension, at most $D+\delta$, such that
\begin{equation} \label{ck-2}
\varepsilon^{-\frac D k+\delta} \preccurlyeq \Delta(\mathscr{C},\varepsilon).
\end{equation}
\end{thm}

We emphasise that in this case the asymptotic behaviour of the $\varepsilon$-distortion complexity,
when $\varepsilon$ tends to zero,  depends in general on the regularity $k$ of the set and, contrarily to the
previous cases, it also depends on its box counting dimension $D$.

\begin{remark}
We notice that our proofs also provide estimates for the Kolmogorov's $\varepsilon$-entropy of some
families of Cantor sets \cite{titi} in the Hausdorff distance.
\end{remark}

\section{Proofs}\label{allproofs}

The following two simple lemmas will be used repeatedly in the proofs
hereafter. We leave their elementary proof to the reader.

\begin{lemma} \label{lemma:1}
Let $F$ and $F'$ be closed subsets of $A$. Let $I=[a,b]$ and
$I'=[a',b']$ be closed sub-intervals of $A$. Let $H=[c,d]$ and
$H'=[c',d']$ be closed subsets of $\stackrel{\scriptscriptstyle{\circ}}{I}$ and
$\stackrel{\scriptscriptstyle{\circ}}{I'}$ respectively. Assume that $\partial H
\subset F$, $\partial H' \subset F'$, $F\cap \stackrel{\scriptscriptstyle{\circ}}{H} =
\emptyset$ and $F'\cap \stackrel{\scriptscriptstyle{\circ}}{H'} = \emptyset$. Moreover
assume that there exists $\varepsilon >0$ such that $|a-a'|\le \varepsilon$,
$|b-b'|\le \varepsilon$, $|c-d|>2\varepsilon$, $|c'-d'|>2\varepsilon$ and $\max
\set{|c-c'|,|d-d'|}>\varepsilon$, then $d_{\scriptscriptstyle{\mathrm{H}}}(F,F')>\varepsilon$.
\end{lemma}

In the sequel, this lemma will be used to show that two Cantor sets ($F$ and $F'$)
are a Hausdorff distance larger than $\varepsilon$, $H$ and $H'$ playing the role of
holes in the Cantor sets.

\begin{lemma} \label{lemma:2}
Let $(\Omega,\cal{A},\mathbb P)$ be a probability space. Let $\mathscr{C}$
be a measurable map from $(\Omega,\cal{A})$ to the set of closed
subsets of $A$ equipped with the Borel $\sigma$-algebra induced by
the Hausdorff metric. Let $(a_k)_k$ be a positive, increasing, diverging
sequence. Assume that for any integer $k$ there exists a sequence
$(V_{k,j})_{1\le j\le 2^{a_k}}$ of measurable subsets of $\Omega$
such that
$$
\set{\omega : \Delta(\mathscr{C}(\omega),2^{-k}) < a_k} \subset
\bigcup_{j=1}^{2^{a_k}}\ V_{k,j}
$$
and
$$
\sum_{k}\ \sum_{j=1}^{2^{a_k}}\ \mathbb P(V_{k,j}) < \infty.
$$
Then, for $\mathbb P$-almost every $\omega$,
$\Delta(\mathscr{C}(\omega),2^{-k}) \ge a_k$ for any $k$ large enough
(depending on $\omega$).
\end{lemma}

\subsection{Proof of Theorem \ref{thm:pol}}

Let $N$ be the largest degree of the polynomial functions
$\set{\phi_i}$, then we can write
$$\phi_i(x) = \sum_{0\le \alpha \le N} \ c_{i,\alpha} x^\alpha \qquad
\forall \ i \in \mathcal{I}$$ with coefficients $c_{i,\alpha} \in \mathbb R$. We
now show how to construct a program $\mathtt{P}$ approximating $\mathscr{C}$
within Hausdorff distance $\varepsilon$.

Let $\varepsilon$ be fixed and $K$ a constant to be specified later on. Let
us define $\varepsilon'=\frac{\varepsilon}{K}$. We construct polynomials
$$
\tilde \phi_i(x) := \sum_{0\le \alpha \le N} \ \tilde c_{i,\alpha}
x^\alpha \qquad \forall \ i \in \mathcal{I}
$$
with coefficients satisfying
\begin{equation} \label{polyn-app-coeff}
|c_{i,\alpha} - \tilde c_{i,\alpha}| < \varepsilon' \qquad \forall\ i\in
\mathcal{I} \quad \forall\ 0\le \alpha \le N
\end{equation}
such that the $\tilde \phi_i$'s are injective contractions on $A$
with uniform contraction rate $\tilde \rho \in (0,1)$. For any
$\omega_1^n \in \mathcal{I}^n$ we construct the composition $\tilde
\phi_{_{\omega_1^n}}$ as in (\ref{ifs-finite}).

We first show that for any bounded set $B\subset \mathbb R$ such that
$\phi_i(B)\subset B$ for all $i\in \mathcal{I}$ with the same contraction
rate $\rho$, and $\tilde \phi_i(B)\subset B$ for all $i\in \mathcal{I}$, we
have for all $n\in \mathbb N$
\begin{equation} \label{polyn-estim-finite}
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^n}}(B), \tilde \phi_{_{\omega_1^n}}(B)) <
\varepsilon' \ \frac{1-\rho^n}{1-\rho}\ \sup\limits_{x\in B}\ \left|
\sum_{0\le \alpha \le N}\ x^\alpha \right| \qquad \forall\
\omega_1^n \in \mathcal{I}^n.
\end{equation}
The proof is by induction. By (\ref{polyn-app-coeff}) and
definition of $d_{\scriptscriptstyle{\mathrm{H}}}$, one immediately gets
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_i(B),\tilde \phi_i(B)) < \varepsilon' \ \sup\limits_{x\in B}\
\left| \sum_{0\le \alpha \le N}\ x^\alpha \right| \qquad \forall \
i\in \mathcal{I}.
$$
The inductive step is obtained by using the triangle inequality
for $d_{\scriptscriptstyle{\mathrm{H}}}$. By the first step we have
$$
d_{\scriptscriptstyle{\mathrm{H}}}\left(\phi_{\omega_n}(\tilde \phi_{_{\omega_1^{n-1}}}(B)), \tilde
\phi_{\omega_n} (\tilde \phi_{_{\omega_1^{n-1}}}(B))\right) < \varepsilon' \
\sup\limits_{x\in B}\ \left| \sum_{0\le \alpha \le N}\ x^\alpha
\right|
$$
where we have used $\tilde \phi_{_{\omega_1^{n-1}}}(B) \subset B$.
Moreover, by using the contraction rate $\rho$, we get
$$
d_{\scriptscriptstyle{\mathrm{H}}}\left(\phi_{\omega_n}(\phi_{_{\omega_1^{n-1}}}(B)),
\phi_{\omega_n} (\tilde \phi_{_{\omega_1^{n-1}}}(B))\right) < \rho\
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^{n-1}}}(B),\tilde
\phi_{_{\omega_1^{n-1}}}(B))
$$
$$
< \varepsilon' \ \rho\ \frac{1-\rho^{n-1}}{1-\rho}\ \sup\limits_{x\in B}\
\left| \sum_{0\le \alpha \le N}\ x^\alpha \right|
$$
where the last inequality is the $(n-1)$-th step of the induction.
Hence the triangle inequality implies that
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^n}}(B), \tilde \phi_{_{\omega_1^n}}(B))
<\varepsilon' \ \left(1+\rho\ \frac{1-\rho^{n-1}}{1-\rho}\right)\
\sup\limits_{x\in B}\ \left| \sum_{0\le \alpha \le N}\ x^\alpha
\right|.
$$
This finishes the proof of (\ref{polyn-estim-finite}).

Let us choose $\bar n\in \mathbb N$ such that $\rho^{\bar n} < \varepsilon'$ and
$\tilde \rho^{\bar n} < \varepsilon'$. For this fixed $\bar n$, let
$V:=\set{0,1}=\partial[0,1]$ and define
$$
\mathtt{C} := \bigcup_{\omega_1^{\bar n} \in \mathcal{I}^{\bar n}}\ \tilde
\phi_{_{\omega_1^{\bar n}}} (V).
$$
We now prove that $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C},\mathtt{C}) < \varepsilon$. Let us consider $x\in
\mathscr{C}$ and $y\in \mathtt{C}$. By (\ref{ifs-prop}) there exists $z\in \mathscr{C}$
such that $x= \phi_{_{\omega_1^{\bar n}(x)}}(z)$ for a given
sequence $\omega_1^{\bar n}(x) \in \mathcal{I}^n$. Hence
\begin{equation} \label{pointwise-estim}
\begin{array}{c}
d(x,y)= d(\phi_{_{\omega_1^{\bar n}(x)}}(z),y) \le \\[0.5cm]
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^{\bar
n}(x)}}(z),\phi_{_{\omega_1^{\bar n}(x)}}(V)) +
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^{\bar n}(x)}}(V), \tilde
\phi_{_{\omega_1^{\bar n}(x)}}(V)) + d_{\scriptscriptstyle{\mathrm{H}}}(\tilde
\phi_{_{\omega_1^{\bar n}(x)}}(V), y).
\end{array}
\end{equation}
For the first term we use the contraction properties to get
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^{\bar n}(x)}}(z),\phi_{_{\omega_1^{\bar n}(x)}}(V))
< \rho^{\bar n} \hbox{ diam } (A) < \varepsilon'.
$$
By (\ref{polyn-estim-finite}), for the second term we have
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^{\bar n}(x)}}(V), \tilde
\phi_{_{\omega_1^{\bar n}(x)}}(V)) < \frac{\varepsilon'}{1-\rho}\ (N+1).
$$
If we take
$$
K= 1 + \frac{N+1}{1-\rho}
$$
then
$$
d(x,y) \le \varepsilon' K + d_{\scriptscriptstyle{\mathrm{H}}}(\tilde \phi_{_{\omega_1^{\bar n}(x)}}(V), y)=
\varepsilon + d_{\scriptscriptstyle{\mathrm{H}}}(\tilde \phi_{_{\omega_1^{\bar n}(x)}}(V), y).
$$
Choosing $y\in \tilde \phi_{_{\omega_1^{\bar n}(x)}}(V) \subset
\mathtt{C}$, we have
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\tilde \phi_{_{\omega_1^{\bar n}(x)}}(V), y)=0,
$$
hence $d(x,y)< \varepsilon$. Therefore
$$
\sup\limits_{x\in \mathscr{C}} \ d(x,\mathtt{C}) < \varepsilon.
$$
On the other hand for a given $\omega_1^{\bar n} \in \mathcal{I}^{\bar n}$
and $y\in \tilde \phi_{_{\omega_1^{\bar n}}}(V)$, take $x\in
\phi_{_{\omega_1^{\bar n}}}(A) \cap \mathscr{C}$, noticing that this set is
not empty. Then we deduce that
$$
\sup\limits_{y\in \mathtt{C}} \ d(y,\mathscr{C}) < \varepsilon.
$$
Hence $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C},\mathtt{C}) < \varepsilon$.

Let us define the program $\mathtt{P}$ that contains the numbers $\varepsilon$,
$\rho$ and $K$, and such that it specifies the coefficients
$\set{\tilde c_{i,\alpha}}$, computes $\bar n$ and makes the
computation of the $\tilde \phi_i(V)$'s. The binary length
$\ell(\mathtt{P})$ satisfies
$$
\ell(\mathtt{P}) \preccurlyeq \log \left((\varepsilon')^{-1} \right) =
\log K + \log(\varepsilon^{-1})\ .
$$
Indeed, $\varepsilon$ is specified with $O(\log \varepsilon^{-1})$ bits, and $\rho$
and $K$ do not depend on $\varepsilon$ and can be approximated by
rational numbers. The coefficients $\set{\tilde c_{i,\alpha}}$ are
approximations of the $\set{c_{i,\alpha}}$ with precision $\varepsilon'$,
hence we can choose them as rational numbers requiring only
$O(\log (\varepsilon')^{-1})$ bits of information. Finally the
information for the computation of $\bar n$ and $\mathtt{C}$ needs only
$O(1)$ bits of information. Hence this proves (\ref{pol-1}).

We now prove (\ref{pol-2}). Let $\mathcal{I}=\set{0,1}$ and define
$\phi_1(x)=bx$, $\phi_2(x)=1-bx$ for $b\in (0,1/2)$. We denote by
$\mathscr{C}_b$ the Cantor set generated by the IFS $\set{\phi_1,\phi_2}$.
To be in the context of Lemma \ref{lemma:2}, we take $b$ at random
according to the uniform distribution on the interval $(1/4,1/3)$.
We restrict the possible values of $b$ to ensure that the middle
hole is large enough so that an obviously simplified version of
Lemma \ref{lemma:1} applies.

For a fixed $\delta \in (0,1)$, define $a_k:=(1-\delta) k$. For
any $k$, there are at most $2^{a_k}$ different binary programs
$(\mathtt{P}_j)_{1\le j \le 2^{a_k}}$ of length $a_k-1$, which generate
at most $2^{a_k}$ different sets $\mathtt{C}_j:=\mathtt{C}(\mathtt{P}_j)$. We define
$$
V_{k,j}:= \set{b : d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_b,\mathtt{C}_j) < 2^{-k}}.
$$
Then
$$
\set{b : \Delta(\mathscr{C}_b,2^{-k})< a_k} \subset
\bigcup_{j=1}^{2^{a_k}}\ V_{k,j}.
$$
We now estimate $\mathbb P(V_{k,j})$. We denote by $\partial^+ \mathtt{C}_j$
the rightmost point of $\mathtt{C}_j \cap (0,1/2)$. For $k$ large enough
($k\ge 3$) and for a given $j$, if $b\in V_{k,j}$ then
$d(b,\partial^+ \mathtt{C}_j)< 2^{-k}$ and therefore $\mathbb P(V_{k,j}) <
2^{1-k}$. This implies that
$$
\sum_k \ \sum_{j=1}^{2^{a_k}}\ \mathbb P(V_{k,j}) < \sum_k \ 2^{a_k}\
2^{1-k} = \sum_k \ 2^{1-\delta k} < \infty.
$$
The result follows from Lemma \ref{lemma:2}.

\begin{remark}
Notice that this proof works also in arbitrary finite dimension.
\end{remark}

\subsection{Proof of Theorem \ref{thm:analytic}}

We give the proof in the case that the $\set{\phi_i}$ are analytic
functions on an open ball $B(0,R)\subset \mathbb C$ of radius $R>1$.
The general case follows by applying the same argument to
piecewise polynomial approximations of the $\set{\phi_i}$.

By hypothesis we can write for $z\in A$
$$
\phi_i(z) = \sum_{h=0}^\infty\ c_{i,h} \ z^h \qquad \forall \ i\in
\mathcal{I}
$$
with coefficients $c_{i,h} \in \mathbb C$. By the analyticity of the
functions $\set{\phi_i}$ in $B(0,R)$ it follows that
$$
\limsup\limits_{h\to \infty} \ |c_{i,h}|\ R^h \le 1\ .
$$
Hence there exists a real constant $r$ such that
$$
|c_{i,h}|\ R^h \le r \qquad \forall \ h\ge 0.
$$
As above let us denote by $V=\set{0,1}=\partial[0,1]$. We now construct
approximations of the analytic functions $\set{\phi_i}$.

Let $\delta\in (0,1)$ be such that $\delta R>1$, and, for $\varepsilon$
fixed, define
\begin{equation} \label{analytic-help}
\varepsilon':= \frac{r(\delta R-1)}{R(1-\delta)}\ ((1-\delta)
\varepsilon)^{\left( \frac{\log R}{\log \frac{1}{\delta}} \right)}.
\end{equation}
Let $N$ be the smallest integer satisfying
\begin{equation} \label{analytic-app-degree}
\sum_{h=N}^\infty \ \delta^h = \frac{\delta^N}{1-\delta} <
(1-\rho)\ \frac{\varepsilon}{4r} \cdot
\end{equation}
Hence we construct the polynomials
$$
\tilde \phi_i(z) := \sum_{h=0}^{N-1} \ \tilde c_{i,h} \ z^h \qquad
\forall\ i\in \mathcal{I}
$$
with coefficients $\tilde c_{i,h} \in \mathbb C$ such that
\begin{equation} \label{analytic-app-coeff}
|c_{i,h} - \tilde c_{i,h} | < \varepsilon' \qquad \forall\ i \in \mathcal{I} \quad
\forall \ h=0,\dots,N-1
\end{equation}
and the $\tilde \phi_i$'s are contractions functions on $A$ with
$\tilde \phi_i (A) \subset A$ for all $i\in \mathcal{I}$, and uniform
contraction rate $\tilde \rho \in (0,1)$.

Let us choose ${\bar n}\in \mathbb N$ such that $\rho^{\bar n} <
\frac{\varepsilon}{4R}$ and $\tilde \rho^{\bar n} < \frac{\varepsilon}{4R}$.
For this fixed ${\bar n}$, we define
$$
\mathtt{C} := \bigcup_{\omega_1^{\bar n} \in \mathcal{I}^{\bar n}}\
\tilde \phi_{_{\omega_1^{\bar n}}}(V) .
$$
We now prove that $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C},\mathtt{C}) < \varepsilon$.
The proof will follow again by using (\ref{pointwise-estim}) and the
analogue of (\ref{polyn-estim-finite}).

For any bounded set $B\subset B(0,\delta R)$ such that $\phi_i(B)
\subset B$ and $\tilde \phi_i(B) \subset B$, we have for all $n\in
\mathbb N$
\begin{equation} \label{analytic-estim-finite}
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_{_{\omega_1^n}}(B), \tilde \phi_{_{\omega_1^n}}(B)) <
\varepsilon \ \frac{1-\rho^n}{2} \qquad \forall\ \omega_1^n \in \mathcal{I}^n \ .
\end{equation}
The proof of (\ref{analytic-estim-finite}) is by induction as the
proof of (\ref{polyn-estim-finite}). We only show the first step.
By using (\ref{analytic-app-coeff}) and
(\ref{analytic-app-degree}), we obtain for all $z\in B(0,\delta
R)$
$$
|\phi_i(z)-\tilde \phi_i(z)| = \left| \sum_{h=0}^{N-1}\
(c_{i,h}-\tilde c_{i,h}) \ z^h + \sum_{h=N}^\infty \ c_{i,h} \ z^h
\right|
$$
$$\le \varepsilon' \sum_{h=0}^{N-1}\ \delta^h R^h + r \sum_{h=N}^\infty \
\delta^h < \varepsilon' \frac{\delta^N R^N}{R\delta -1} + (1-\rho)\
\frac{\varepsilon}{4r} \ r
$$
$$
< (1-\rho)\ \varepsilon \left(\varepsilon' \frac{R(1-\delta)
((1-\delta)\varepsilon)^{\big(-\frac{\log R}{\log \delta^{-1}}\big)} }{4r(\delta
R -1)} + \frac{r}{4r}\right)  = (1-\rho)\ \frac{\varepsilon}{2}\ ,
$$
where in the last equality we have used (\ref{analytic-help}).
Hence
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\phi_i(B),\tilde \phi_i(B)) < \varepsilon \ \frac{(1-\rho)}{2}
\qquad \forall \ i\in \mathcal{I}.
$$
The inductive step is obtained as in the proof of
(\ref{polyn-estim-finite}) by the triangle inequality for
$d_{\scriptscriptstyle{\mathrm{H}}}$.

We now write (\ref{pointwise-estim}) and, by repeating the
argument of the proof of Theorem \ref{thm:pol} and by
(\ref{analytic-estim-finite}), we obtain $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C},\mathtt{C}) < \varepsilon$.

Let us define the program $\mathtt{P}$ which contains the numbers $\varepsilon$,
$R$, $r$, $\delta$, $N$ and ${\bar n}$, and such that it specifies
the coefficients $\set{\tilde c_{i,h}}$ for $h=0,\dots,N-1$, and
makes the computation of the $\tilde \phi_i(V)$'s. The binary length
$\ell(\mathtt{P})$ satisfies
$$
\ell(\mathtt{P}) \preccurlyeq N \log \left((\varepsilon')^{-1} \right)
\preccurlyeq \left( \log (\varepsilon^{-1}) \right)^2\ .
$$
Indeed, $\varepsilon$ is specified with $O(\log \varepsilon^{-1})$ bits, and $\bar n \asymp \log
\varepsilon^{-1}$. Hence it is specified by $o(\log \varepsilon^{-1})$ bits and
$N\asymp \log \varepsilon^{-1}$, hence it is specified by $o(\log
\varepsilon^{-1})$ bits. The coefficients $\set{\tilde c_{i,h}}$ are
approximations of the $\set{c_{i,h}}$ with precision $\varepsilon'$,
hence we can choose them as rational numbers requiring only
$O(\log (\varepsilon')^{-1})$ bits of information, but there are $N$ of
them for each function $\phi_i$ (see (\ref{analytic-help}) and
(\ref{analytic-app-degree})), hence we need $O(N \log
(\varepsilon')^{-1})$ bits of information, that is $O(\left( \log
(\varepsilon^{-1}) \right)^2)$. Finally $R$, $r$ and $\delta$ do not
depend on $\varepsilon$, hence the information for them and for the
computation of $\mathtt{C}$ need only $O(1)$ bits of information. Hence
$$\Delta(\mathscr{C},\varepsilon) \preccurlyeq \left( \log (\varepsilon^{-1}) \right)^2$$
and the theorem is proved.

\subsection{Proof of Theorem \ref{thm-centcanrand}}

We first prove (\ref{rand-1}) by constructing an approximation
$\mathtt{C}$ of the set $\mathscr{C}$.

Let us consider a fixed sequence $\lambda \in (0,1)^\mathbb N$ and the
Cantor set $\mathscr{C}_\lambda$. For a fixed $\varepsilon$, let $\bar n$ be given by
\begin{equation} \label{rand-cantor-app-degree}
\bar n := \min \set{n\in \mathbb N:\frac{1}{2^n}< \frac \varepsilon 2}.
\end{equation}
Next, let us consider a sequence $\tilde \lambda=(\tilde \lambda_k)_{k\in \mathbb N}\in(0,1)^{\mathbb N}$
such that $|\lambda_1 - \tilde \lambda_1| < \varepsilon$ and
\begin{equation} \label{rand-cantor-coeff}
|\lambda_k - \tilde \lambda_k| < 2^{k-2}\ \varepsilon \qquad \forall\
k=2,\dots,\bar n\ .
\end{equation}
Then we define the approximation $\mathtt{C}$ of $\mathscr{C}_\lambda$ to be the finite
set
$$
\mathtt{C} := \partial C^{\bar n}_{\tilde \lambda} =
\bigcup_{i=1}^{2^{\bar n}}\ \partial J^{\bar n}_i(\tilde \lambda)
$$
where the sets $C^{\bar n}_{\tilde \lambda}$ and $J^{\bar
n}_i(\tilde \lambda)$ are constructed as specified in Section
\ref{definition}. We now prove that $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathtt{C})
<\varepsilon$. To this aim we show that
\begin{equation} \label{rand-cantor-app-finite}
d_{\scriptscriptstyle{\mathrm{H}}}(\partial J^k_1(\lambda),\partial J^k_1(\tilde \lambda)) <
\frac \varepsilon 2
\end{equation}
for all $k=1,\dots,\bar n$. The same argument applies to all other
sets $J^k_i$. This is enough since it implies that, for any two
points $x\in \mathscr{C}_\lambda$ and $y\in \mathtt{C}$ in the analogous intervals
({\em i.e.},  $x\in J^{\bar n}_i(\lambda)$ and $y\in
\partial J^{\bar n}_i(\tilde \lambda)$ with the same index
$i=1,\dots,2^{\bar n}$),
\begin{eqnarray*}
d(x,y)  & \le & d(x,\partial J^{\bar n}_i(\lambda)) + d_{\scriptscriptstyle{\mathrm{H}}}(\partial J^{\bar
n}_i(\lambda),\partial J^{\bar n}_i(\tilde \lambda)) +
d(\partial J^{\bar n}_i(\tilde \lambda),y)\\
& < & \frac{1}{2^{\bar n}} + \frac \varepsilon 2 + 0 < \varepsilon ,
\end{eqnarray*}
where for the first term we have used (\ref{rand-cantor-length})
and (\ref{rand-cantor-app-degree}), for the second term we have
used (\ref{rand-cantor-app-finite}), and for the third term we
have used the definition of $\mathtt{C}$. Hence $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathtt{C})<
\varepsilon$. It remains to prove (\ref{rand-cantor-app-finite}). By
definition
$$
\partial J^k_1(\lambda) = \set{0, \frac{1}{2^k}
\prod_{h=1}^k  \lambda_h} , \partial J^k_1(\tilde \lambda) =
\set{0, \frac{1}{2^k}  \prod_{h=1}^k  \tilde \lambda_h}.
$$
Hence it is enough to show that
\begin{equation} \label{rand-cantor-app-finite-help}
d\left(\frac{1}{2^k}  \prod_{h=1}^k  \lambda_h, \frac{1}{2^k}
\prod_{h=1}^k  \tilde \lambda_h\right) < \frac \varepsilon 2
\end{equation}
for all $k=1,\dots,\bar n$. By definition of $\tilde \lambda$, it
holds
$$
d\left( \frac 1 2 \lambda_1, \frac 1 2 \tilde \lambda_1 \right) <
\frac \varepsilon 2.
$$
Assuming that (\ref{rand-cantor-app-finite-help}) holds for $k-1$, one gets
$$
d\left(\frac{1}{2^k}  \prod_{h=1}^k  \lambda_h, \frac{1}{2^k}
\prod_{h=1}^k  \tilde \lambda_h\right)
$$
$$
\le \left|\frac{1}{2^{k-1}}  \prod_{h=1}^{k-1}  \lambda_h\right|\
\left|\frac{\lambda_k - \tilde \lambda_k}{2} \right| +
d\left(\frac{1}{2^{k-1}}  \prod_{h=1}^{k-1}  \lambda_h,
\frac{1}{2^{k-1}}  \prod_{h=1}^{k-1}  \tilde \lambda_h\right) \
\frac{\tilde \lambda_k}{2}
$$
$$
< \frac{1}{2^{k-1}} \ \frac{2^{k-2} \varepsilon}{2} + \frac{\varepsilon}{4} < \frac \varepsilon 2,
$$
where we have used (\ref{rand-cantor-coeff}) for the first term,
the inductive hypothesis for the second term, and the fact that
$\lambda, \tilde \lambda \in (0,1)^\mathbb N$.

To finish the proof of (\ref{rand-1}) we have to estimate the
length of a binary program $\mathtt{P}$ producing the finite set $\mathtt{C}$.
The program $\mathtt{P}$ must contain the number $\varepsilon$, the information
to compute $\bar n$, the contraction factors $(\tilde \lambda_k)$
for $k=1,\dots,\bar n$ and the instruction to compute
$\mathtt{C}$. The number of instructions for all the computations are $O(1)$ with
respect to $\varepsilon$. The number $\varepsilon$ is specified by $O(\log
\varepsilon^{-1})$ bits of information and $\bar n \approx \log \varepsilon^{-1}$
and each coefficient $\tilde \lambda_k$ needs $O(\log \varepsilon^{-1})$
bits of information. Since there are $\bar n$ coefficients to be
specified, we find
$$
\ell(\mathtt{P}) \preccurlyeq \left( \log (\varepsilon^{-1}) \right)^2
$$
hence (\ref{rand-1}) follows.

We now prove (\ref{rand-2}). First of all we identify a full
measure set of \virg{good} $\lambda$. By the hypothesis on the
density $f(x)$ of the common distribution of the random variables
$(\lambda_k)$, the following quantity is finite
$$
\gamma:= \int_0^1 \ \log (x)\ f(x) \ dx < 0.
$$
Notice that $\frac{e^{\gamma}}{2}$ can be interpreted as the
typical contraction rate, since products of many i.i.d. random variables $\lambda_k$
will be involved.

Given any $\eta >0$ we define, for all $n\in \mathbb N$,
\begin{equation} \label{rand-cantor-null-set}
\Lambda_n:= \set{\lambda \in (0,1)^\mathbb N  : \prod_{h=1}^k
\lambda_h > e^{k(\gamma-\eta)} \ , \forall\
k=\lfloor \sqrt{n} \rfloor,\dots, n}\ .
\end{equation}
We remark that, since $\lambda_k \in (0,1)$ for all $k \ge 1$, if
$\lambda \in \Lambda_n$ then
\begin{equation} \label{rand-cantor-bel-help}
\prod_{h=1}^k  \lambda_h >
e^{\sqrt{n}(\gamma-\eta)}\qquad \forall\ k=1,\dots,\lfloor \sqrt{n}
\rfloor -1.
\end{equation}

\begin{lemma} \label{lem:centcanrand}
Let us denote by $\Lambda_n^c$ the complement of  $\Lambda_n$ in
$(0,1)^\mathbb N$, then
$$
\sum_n\ \mathbb P(\Lambda_n^c) < \infty\ ,
$$
\emph{i.e.}, almost every $\lambda \in (0,1)^\mathbb N$ belongs to
$\Lambda_n^c$ only for finitely many $n\in \mathbb N$.
\end{lemma}

\noindent {\it Proof.} We use the large deviation principle for
independent and identically distributed random variables (see,
{\emph{e.g.}, \cite{DZ}). It implies that for any fixed $\eta >0$
there exists a positive
constant $C$ such that
$$
\lim\limits_{k\to \infty}\ \frac{1}{k} \ \log \mathbb P
\set{\frac{\log(\lambda_1\times\cdots\times\lambda_k)}{k} - \gamma <
  -\eta}
= -C\ .
$$
Hence, for $n$ large enough and for all $0<C'<C$, we have the
estimate
$$
\mathbb P(\Lambda_n^c) \le \sum_{k=\lfloor \sqrt{n} \rfloor}^n
\mathbb P \set{\prod_{h=1}^k  \lambda_h < e^{k(\gamma-\eta)}} \le e^{-C' \sqrt{n}}\
\sum_{k=\lfloor \sqrt{n} \rfloor}^n \ e^{-C'(k-\sqrt{n})}\ .
$$
Therefore
$$
\mathbb P(\Lambda_n^c) \preccurlyeq e^{-C' \sqrt{n}}
$$
and the lemma follows by the Borel-Cantelli Lemma. \qed

For any $\varepsilon$ we define
\begin{equation} \label{rand-cantor-bel-degree}
N(\varepsilon) := \min \set{n\in \mathbb N : \left(2 e^{\eta-\gamma}\right)^n  \varepsilon > \left( \log (\varepsilon^{-1})\right)^{-2}} .
\end{equation}
We now consider a subset of $\Lambda_{N(\varepsilon)}$. Let $q\in \mathbb N$ and
define
$$
\Psi_q:= \set{\lambda \in \Lambda_{N(2^{-q})} :
(1-\lambda_{k+1})\ \frac{\prod_{h=1}^k \ \lambda_h}{2^k} >
2^{2-q} , \forall\ k=0,\dots,N(2^{-q})}.
$$

\begin{lemma} \label{lem:rand-useful}
We have
$$
\sum_q\ \mathbb P(\Psi_q^c) < \infty
$$
\emph{i.e.}, almost every $\lambda \in (0,1)^\mathbb N$ lies in
$\Psi_q^c$ only for finitely many $q\in \mathbb N$.
\end{lemma}

\noindent {\bf Proof.} By Lemma \ref{lem:centcanrand} and the
Borel-Cantelli Lemma, it is enough to prove that
$$
\sum_q \ \mathbb P \left( \Psi_q^c \cap \Lambda_{N(2^{-q})} \right) <
\infty.
$$
First observe that if $0\le k \le \sqrt{N(2^{-q})}$ and
$$
(1-\lambda_{k+1}) > 2^{2-q}\ 2^k\
(e^{\eta-\gamma})^{\sqrt{N(2^{-q})}}
$$
then $\lambda$ satisfies
\begin{equation} \label{cond-rand}
(1-\lambda_{k+1})\ \frac{\prod_{h=1}^k \ \lambda_h}{2^k} >
2^{2-q}.
\end{equation}
Similarly, if $\sqrt{N(2^{-q})}\le k \le N(2^{-q})$ and
$$
(1-\lambda_{k+1}) > 2^{2-q}\ 2^k\ (e^{\eta-\gamma})^k\ ,
$$
then (\ref{cond-rand}) holds. Therefore
$$
\mathbb P \set{\lambda \in \Lambda_{N(2^{-q})} \setminus \Psi_q}\ \le
\ 2^{3-q}\ 2^{\sqrt{N(2^{-q})}}\
e^{(\eta-\gamma)\sqrt{N(2^{-q})}}\ +
$$
$$
+\ 2^{2-q}\ 2^{N(2^{-q})+1}\ e^{(\eta-\gamma)(N(2^{-q})+1)} \le
\frac{O(1)}{q^2}
$$
which is summable over $q$. The lemma is proved. \qed

For a given $\varepsilon$, let $\lambda \in \Psi_{\log
(\varepsilon^{-1})}$ and define
$$
M_{\varepsilon,N(\varepsilon)}(\lambda):=\Psi_{\log (\varepsilon^{-1})}\; \bigcap
$$
\begin{equation} \label{rand-cantor-bel-closed}
\left\{\tilde \lambda :
\begin{array}{ll}
|\lambda_1 - \tilde \lambda_1| < 2 \varepsilon & \\
|\lambda_k - \tilde \lambda_k| < 2^{k+1} \left( e^{\eta-\gamma}
\right)^{\sqrt{N}} \varepsilon & \textup{if}\ k=2,\dots,
\lfloor \sqrt{N} \rfloor -1 \\[0.2cm]
|\lambda_k - \tilde \lambda_k| < \frac{2}{e^{\eta-\gamma}} \left(
2\ e^{\eta-\gamma} \right)^k  \varepsilon & \textup{if}\ k=\lfloor
\sqrt{N} \rfloor, \dots, N
\end{array}
\right\}
\end{equation}
We now show that if $\tilde \lambda \not\in M(\lambda)$ then
$d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda, \mathscr{C}_{\tilde \lambda}) \ge \varepsilon$. This follows
from Lemma \ref{lemma:1} and we now check the hypothesis to be
satisfied.

If $\tilde \lambda \in \Psi_{\log (\varepsilon^{-1})} \setminus
M(\lambda)$ then one of the conditions in
(\ref{rand-cantor-bel-closed}) is violated. Following the notation
of Lemma \ref{lemma:1}, we start with $I=I'=[0,1]$. We take
$H=[\frac{\lambda_1}{2}, 1-\frac{\lambda_1}{2}]$ and
$H'=[\frac{\tilde \lambda_1}{2}, 1-\frac{\tilde \lambda_1}{2}]$. Then
$|H|>2\varepsilon$ and $|H'|>2\varepsilon$ since $\lambda$ and $\tilde \lambda$
are in $\Psi_{\log (\varepsilon^{-1})}$. If $|\lambda_1 - \tilde
\lambda_1| \ge 2 \varepsilon$, then
$\left|\frac{\lambda_1}{2}-\frac{\tilde \lambda_1}{2}\right| \ge \varepsilon$,
and Lemma \ref{lemma:1} applies with $F=\mathscr{C}_\lambda$ and $F'=\mathscr{C}_{\tilde
\lambda}$, implying $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathscr{C}_{\tilde \lambda})>\varepsilon$.

Assume that, for some $k=2,\dots, \lfloor \sqrt{N} \rfloor -1$, all
conditions in (\ref{rand-cantor-bel-closed}) are satisfied up to
$k-1$ and condition $k$ is violated.
Either there is an $\ell<k$ such that
$$
\left| \frac{1}{2^\ell}  \prod_{h=1}^\ell  \lambda_h -
\frac{1}{2^\ell}  \prod_{h=1}^\ell  \tilde \lambda_h \right|>\varepsilon,
$$
in which case we define $\hat k$ to be the smallest such $\ell$.
Or, if no such $\ell$ exists,
$$
\left| \frac{1}{2^k}  \prod_{h=1}^k  \lambda_h -
\frac{1}{2^k}  \prod_{h=1}^k  \tilde \lambda_h \right| \ge
\frac{\left| \lambda_k - \tilde \lambda_k \right|}{2^k}
\prod_{h=1}^{k-1}  \lambda_h  - \frac{\tilde \lambda_k}{2^k}
\left| \prod_{h=1}^{k-1}  \lambda_h - \prod_{h=1}^{k-1}  \tilde
\lambda_h \right| \ge
$$
$$
\ge 2\ \varepsilon \left( e^{\eta-\gamma} \right)^{\sqrt{N}}
\prod_{h=1}^{k-1}  \lambda_h - \varepsilon > \varepsilon
$$
where we have used (\ref{rand-cantor-bel-help}) and the fact  that the leftmost
positive points up to the $(k-1)$-th step of the construction are $\varepsilon$-close, and we set $\hat k=k$.

We will apply Lemma \ref{lemma:1} with $I=J^{{\hat k}-1}_1(\lambda)$ and
$I'=J^{{\hat k}-1}_1(\tilde \lambda)$. We take
$$
H=\left[\frac{1}{2^{\hat k}}  \prod_{h=1}^{\hat k}  \lambda_h, \left( 1
-\frac{\lambda_{\hat k}}{2}\right) \frac{1}{2^{{\hat k}-1}}  \prod_{h=1}^{{\hat k}-1}
 \lambda_h \right]
$$
and
$$
H'=\left[\frac{1}{2^{\hat k}}  \prod_{h=1}^{\hat k}  \tilde\lambda_h, \left( 1
-\frac{\tilde\lambda_{\hat k}}{2}\right) \frac{1}{2^{{\hat k}-1}}  \prod_{h=1}^{{\hat k}-1}
 \tilde\lambda_h \right]\ .
$$
We have $|H|>2\varepsilon$ and $|H'|>2\varepsilon$
since $\lambda$ and $\tilde \lambda$ are in $\Psi_{\log
(\varepsilon^{-1})}$, and we can apply Lemma \ref{lemma:1}
which gives $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathscr{C}_{\tilde \lambda})>\varepsilon$.

The same argument applies if the $k$-th condition
with $k=\sqrt{N},\dots,N$ is violated, and all conditions up to $k-1$ are
satisfied.
If the leftmost positive points up to the $(k-1)$-th step of the construction are $\varepsilon$-close, we get
$$
\left| \frac{1}{2^k}  \prod_{h=1}^k  \lambda_h -
\frac{1}{2^k}  \prod_{h=1}^k \tilde \lambda_h \right| \ge 2
\varepsilon \left( e^{\eta-\gamma} \right)^{k-1} \prod_{h=1}^{k-1}
\lambda_h - \varepsilon > \varepsilon
$$
by definition (\ref{rand-cantor-null-set}) of $\Lambda_{N(\varepsilon)}$
and using, as above, that all previous leftmost positive points are
$\varepsilon$-close to each other. Again this implies that
$d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathscr{C}_{\tilde \lambda})>\varepsilon$.

Let us now estimate the measure of the set $M_{\varepsilon,N(\varepsilon)}(\lambda)$.
By an easy computation based on the independence of the random variables
$(\tilde{\lambda}_k)$, we obtain that for all $\lambda \in
\Psi_{\log(\varepsilon^{-1})}$
$$
\mathbb P(M_{\varepsilon,N(\varepsilon)}(\lambda))
$$
$$
\leq \big(\max\limits_{x\in [0,1]} f(x)\big)^{N(\varepsilon)}
(2\varepsilon)^{N(\varepsilon)} (e^{\eta-\gamma})^{-\sqrt{{N(\varepsilon)}}} \
2^{\sum_{k=2}^{N(\varepsilon)} \ k} \
(e^{\eta-\gamma})^{\sum_{k=\lfloor\sqrt{{N(\varepsilon)}}\rfloor}^{N(\varepsilon)} \ k}
$$
\begin{equation}
\label{emme}
\leq \left( 2\ e^{\eta-\gamma} \right)^{-\frac{{N(\varepsilon)}^2}{2} +
O({N(\varepsilon)})} = e^{-O(1) (\log(\varepsilon^{-1}))^2} ,
\end{equation}
where we have used the definition (\ref{rand-cantor-bel-degree}) of ${N(\varepsilon)}$.
Note that this estimate is uniform in $\lambda\in \Psi_{\log(\varepsilon^{-1})}$.

For a fixed $\delta \in (0,1)$, define $a_q:=q^{2-\delta}$. For
any $q$, there are at most $2^{a_q}$ different binary programs
$(\mathtt{P}_j)_{1\le j \le 2^{a_q}}$ of length $a_q-1$, which generate
at most $2^{a_q}$ different sets $\mathtt{C}_j:=\mathtt{C}(\mathtt{P}_j)$. We define
$$
V_{q,j}:= \set{\lambda : d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathtt{C}_j) < 2^{-q}}.
$$
Then
$$
\set{\lambda  : \Delta(\mathscr{C}_\lambda,2^{-q})< a_q} \subset
\bigcup_{j=1}^{2^{a_q}}\ V_{q,j}.
$$
We can write
$$
\mathbb P\left( \bigcup_{j=1}^{2^{a_q}} \ V_{q,j} \right) \le
\mathbb P(\Lambda^c_{N(2^{-q})}) + \mathbb P(\Psi_q^c \cap
\Lambda_{N(2^{-q})}) + \sum_{j=1}^{2^{a_q}}\ \mathbb P(V_{q,j} \cap
\Psi_q).
$$
Moreover if $V_{q,j} \cap \Psi_q\not= \emptyset$, there is a
$\lambda \in \Psi_{q}$ such that $V_{q,j} \cap \Psi_q \subset
M_{2^{-q},N(2^{-q})}(\lambda)$. By Lemmas \ref{lem:centcanrand} and
\ref{lem:rand-useful}, and by (\ref{emme}) it follows that
$$
\sum_q \sum_{j=1}^{2^{a_q}}\ \mathbb P(V_{q,j}) < \infty.
$$
The result follows from Lemma \ref{lemma:2}.

\subsection{Proof of Theorem \ref{thm:ckupper}}
\label{sec:ck-central}

{\bf Preliminaries.} We first recall the definition of the
\emph{scaling function} $S_\mathscr{C}$ of a $C^k$ Cantor set $\mathscr{C}$
(\cite{sullivan},\cite{feliks}). In the sequel we fix
$\mathcal{I}=\set{0,1}$. For a word $\omega_1^n \in \mathcal{I}^n$ we let
$$
J_{\omega_1^n}:= \phi_{_{\omega_1^n}}([0,1])=\phi_{\omega_n} \circ
\phi_{\omega_{n-1}} \circ \dots \circ \phi_{\omega_1}([0,1])\ .
$$
Then by definition
$\phi_i(J_{\omega_1^n})= J_{\omega_1^n i}$ for any $i\in \mathcal{I}$, and
it holds
$$
J_{\omega_1^n} \subset J_{\omega_2^n} \subset \dots \subset
J_{\omega_{n-1}^n}\subset J_{\omega_n}.
$$
The scaling function describes the contraction rates in the
previous inclusions. For a word $\omega_1^n \in \mathcal{I}^n$ we define
$\tilde S_\mathscr{C}(\omega_1^n) \in (0,1)^2$. The two components of
$\tilde S_\mathscr{C}(\omega_1^n)$ are the rates of contractions
$$
(\tilde S_\mathscr{C}(\omega_1^n))_i =\
\frac{|J_{i\omega_1^n}|}{|J_{\omega_1^n}|}\qquad i=0,1
$$
where $|J|$ denotes the length of the interval $J$. The length of
the gap between the two intervals $J_{0\omega_1^n}$ and
$J_{1\omega_1^n}$ in $J_{\omega_1^n}$ can be reconstructed from
these data. The scaling function is defined to be the
function
$$
S_\mathscr{C} : \mathcal{I}^\infty \to (0,1)^2
$$
given by
$$
S_\mathscr{C} (\omega) := \lim_{n\to \infty}\ \tilde
S_\mathscr{C}(\omega_1^n).
$$
We refer to \cite{sullivan} for the proof of the existence of this limit.

By definition one has
$$
|J_{\omega_1^n}| = \prod_{j=1}^{n-1} \left( \tilde S_\mathscr{C}
(\omega_{j+1}^n) \right)_{\omega_j}\ .
$$
By using the scaling function we can introduce a distance
$d_S(\omega,\tilde \omega)$ on $\mathcal{I}^\infty$ in the following way.
For two sequences $\omega,\tilde \omega \in \mathcal{I}^\infty$, let
$\omega \cap \tilde \omega$ denote their longest common prefix,
and let $|\omega \cap \tilde \omega|$ denote its length. Then we
let
\begin{equation} \label{scaling-distance}
d_S(\omega,\tilde \omega) := \sup\limits_{\alpha \in I^\infty}\
\prod_{j=1}^{n=|\omega \cap \tilde \omega|} \left( S_\mathscr{C}
(\omega_{j+1}^n \ \alpha) \right)_{\omega_j}\ .
\end{equation}
Then there exists a constant $H>0$ such that for any
$\omega,\tilde \omega \in \mathcal{I}^\infty$ it holds
$$
\frac 1 H \le \frac{J_{\omega \cap \tilde
\omega}}{d_S(\omega,\tilde \omega)}\le H \ .
$$
Relations between the properties of the scaling function of a
$C^k$ central Cantor set and the differentiability of the IFS
generating this Cantor set have been studied in \cite{feliks} in
the case $k\ge 1$ (we refer the reader to Main Theorem
\cite{feliks}, page 406). The idea is the following. Let
$A(\omega_1^n)$ denote the set of the four boundary points of the
intervals $(J_{i\omega_1^n})_{i\in \mathcal{I}}$. A scaling function $S_\mathscr{C}$
generates a $C^k$ Cantor set $\mathscr{C}$ if and only if for any $n\in \mathbb N$
there are diffeomorphisms from $A(\omega_1^n)$ into $A(\tilde
\omega_1^n)$, for any $\omega_1^n \not= \tilde \omega_1^n \in
\mathcal{I}^n$, with derivatives bounded by a constant $C(\omega_1^n,
\tilde \omega_1^n)$ which satisfies
\begin{equation} \label{ck-condition}
C(\omega_1^n, \tilde \omega_1^n) = C\ d_S(\omega_1^n \alpha,
\tilde \omega_1^n \alpha)^{k-1}
\end{equation}
where $C$ does not depend on $n$ and from the definition of $d_S$
the right hand side is independent on $\alpha \in \mathcal{I}^\infty$.

\noindent \textbf{Proof of Theorem \ref{thm:ckupper}.} We first
prove (\ref{ck-1}). Let $\varepsilon$ be fixed. We show how to
approximate the set $\mathscr{C}$ within Hausdorff distance $\varepsilon$.
We will  give the proof for integer $k\geq 1$. The proof easily
extends to functions whose $k$-th derivative is H\"older.

We can write the Taylor expansions of the maps $\phi_i$ at a point $x_0$
$$
\phi_i (x) = \sum_{p=0}^{k-1}\ c_{i,p}(x_0)\ (x-x_0)^p + R_i(x,x_0)
\qquad \forall\ x\in [0,1].
$$
Moreover there exists a constant $K>0$ such that $|R_i(x,x_0)|\le
K |x-x_0|^k$ for $x\in [0,1]$, for all $i\in \mathcal{I}$ and $x_0 \in
[0,1]$.

Let $\varepsilon'= \varepsilon \ \frac{1-\rho}{M}$ for a constant $M$ to be
specified later on. We now construct a sequence of polynomials which
approximate the maps $(\phi_i)_{i\in \mathcal{I}}$. If $D$ is the box
counting dimension of the Cantor set $\mathscr{C}$, we need for any
$\delta>0$ at most $N =O((\varepsilon')^{-\frac D k-\delta})$ intervals
$(I_s)_{s=1,\dots,N}$ of size $(\varepsilon')^{\frac 1 k}$ to cover $\mathscr{C}$.
Hence we can consider the maps $(\phi_i)_{i\in \mathcal{I}}$ restricted to
the sets $(I_s)$. If $y_s$ denotes the middle point of the
interval $I_s$, let $\tilde y_s$ be the approximation of the point
$y_s$ within a distance $\varepsilon'$. Then we define
$$\tilde \phi_i^s (x) = \sum_{p=0}^k\ \tilde
c_{i,p}(y_s)\ (x-\tilde y_s)^p \qquad \forall\ x\in [0,1]$$ such
that
\begin{equation} \label{ck-app-coeff}
|c_{i,p}(y_s) - \tilde c_{i,p}(y_s)| < \varepsilon' \qquad \forall \ i\in
\mathcal{I} \ \ \forall\ p=0,\dots,k
\end{equation}
and they are contractions on $\mathbb R$ with the same uniform
contraction rate $\tilde{\rho} <1$.

To construct an approximation of $\mathscr{C}$, we work on the boundary
points of the intervals $J_{\omega_1^n}$ which all are in $\mathscr{C}$.
Let us denote
$J_{\omega_1^n}=[y^1_{\omega_1^n},y^2_{\omega_1^n}]$. Since for
any $n\in \mathbb N$ and any $\omega_1^n \in \mathcal{I}^n$ we have
$y^\eta_{\omega_1^n}\in \mathscr{C}$ for $\eta=1,2$, we can associate to a
given $y^\eta_{\omega_1^n}$ a sequence $\sigma_0^{n-1} \in
\set{1,\dots,N}^{n-1}$ which specifies to which intervals of the
cover $(I_s)_{s=1,\dots,N}$ the pre-images
$y^\eta_{\omega_1^{n-1}}, y^\eta_{\omega_1^{n-2}}, \dots,
y^\eta_{\omega_1}, y^\eta_{\sharp}$ of $y^\eta_{\omega_1^n}$
belong, where $y^\eta_{\sharp} \in \set{0,1}$.

We now establish the analogue of (\ref{polyn-estim-finite}) for
the boundary points. Let us define
$$
\tilde y^\eta_{\omega_1^n}:= \tilde \phi_{\omega_n}^{\sigma_{n-1}}
\circ \tilde \phi_{\omega_{n-1}}^{\sigma_{n-2}} \circ \dots \circ
\tilde \phi_{\omega_1}^{\sigma_0} (y^\eta_\sharp)
$$
then for all $n\in \mathbb N$ it holds
\begin{equation} \label{ck-estim-finite}
|y^\eta_{\omega_1^n} - \tilde y^\eta_{\omega_1^n}| < \left( k+1 +
K + \max\limits_{i\in \mathcal{I},\ s=1,\dots,N} \sum_{p=0}^k\
|c_{i,p}(y_s)| \right) \frac{\varepsilon'}{1-\rho} \qquad \forall\
\omega_1^n \in \mathcal{I}^n.
\end{equation}
The proof is by induction. The first step ($n=1$) follows by
definition of the approximating polynomials,  estimates
(\ref{ck-app-coeff}) and properties of the remainder
$R_i(x,x_0)$. This yields
\begin{eqnarray*}
|y^\eta_i-\tilde y^\eta_i| & =  & |\phi_i(y^\eta_\sharp)- \tilde \phi_i^{\sigma_0}(y^\eta_\sharp)| \\
& \le & \varepsilon'\sum_{p=0}^k (\varepsilon')^{\frac p k} + \sum_{p=0}^k\ |c_{i,p}(y_{\sigma_0})|
|(y^\eta_\sharp-y_{\sigma_0})^p-(y^\eta_\sharp-\tilde
y_{\sigma_0})^p| + K \varepsilon' \\
& \le & \left( k+1 + K + \max\limits_{i\in \mathcal{I},\ s=1,\dots,N} \sum_{p=0}^k\ |c_{i,p}(y_s)|
\right) \varepsilon'  .
\end{eqnarray*}
The inductive step follows by using the triangle inequality
$$
|y^\eta_{\omega_1^n} - \tilde y^\eta_{\omega_1^n}|\le
|\phi_{\omega_n}(y^\eta_{\omega_1^{n-1}})-\tilde
\phi_{\omega_n}^{\sigma_{n-1}}(y^\eta_{\omega_1^{n-1}})| + |\tilde
\phi_{\omega_n}^{\sigma_{n-1}}(y^\eta_{\omega_1^{n-1}})-\tilde
\phi_{\omega_n}^{\sigma_{n-1}}(\tilde y^\eta_{\omega_1^{n-1}})|
$$
together with
$$
|\phi_{\omega_n}(y^\eta_{\omega_1^{n-1}})-\tilde
\phi_{\omega_n}^{\sigma_{n-1}}(y^\eta_{\omega_1^{n-1}})| < \varepsilon'
\left( k+1 + K + \max\limits_{i\in \mathcal{I},\ s=1,\dots,N} \sum_{p=0}^k\
|c_{i,p}(y_s)| \right)
$$
and
$$
|\tilde \phi_{\omega_n}^{\sigma_{n-1}}(y^\eta_{\omega_1^{n-1}})-\tilde
\phi_{\omega_n}^{\sigma_{n-1}}(\tilde y^\eta_{\omega_1^{n-1}})| <
\rho\ |y^\eta_{\omega_1^{n-1}} - \tilde y^\eta_{\omega_1^{n-1}}|,
$$
where $\rho$ is the uniform contraction rate of the approximating
polynomials.

Let us choose $\bar n$ such that $\rho^{\bar n} < \frac{\varepsilon}{2}$
for all $n\ge \bar n$. Then we define the set
$$\mathtt{C} := \bigcup_{\omega_1^{\bar n}\in \mathcal{I}^{\bar n}}\ \left(\tilde
y^1_{\omega_1^{\bar n}}\cup \tilde y^2_{\omega_1^{\bar n}}
\right)$$ and we claim that $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C},\mathtt{C})< \varepsilon$. Indeed, by
definition of $\bar n$, any point in the Cantor set $\mathscr{C}$ is at
most at distance $\frac \varepsilon 2$ from a point in the boundary of
one of the sets $J_{\omega_1^{\bar n}}$. Moreover, by construction
of the points $\tilde y^\eta_{\omega_1^{\bar n}}$ we have
(\ref{ck-estim-finite}), hence the claim follows since
$$
d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C},\mathtt{C}) \le \sup\limits_{x\in \mathscr{C}}
\inf\limits_{\omega_1^{\bar n} \in \mathcal{I}^{\bar n}} |x-\tilde
y^\eta_{\omega_1^{\bar n}}|
$$
$$
\le \sup_{x\in \mathscr{C}}
\inf\limits_{\omega_1^{\bar n} \in \mathcal{I}^{\bar n}} \left( |x-
y^\eta_{\omega_1^{\bar n}}| + |y^\eta_{\omega_1^{\bar n}} - \tilde
y^\eta_{\omega_1^{\bar n}}| \right)< \varepsilon
$$
provided that we choose
$$
M:= 2 \left(
k+1 + K + \max\limits_{i\in \mathcal{I},\ s=1,\dots,N} \sum_{p=0}^k\
|c_{i,p}(y_s)| \right)\ .
$$

Let us define the program $\mathtt{P}$ that contains the numbers $\varepsilon$,
$\rho$, $D$, $M$, $K$ and $k$, and such that it specifies all the
necessary coefficients $\tilde c_{i,p}$, makes the computation to
obtain $N$ and the approximated points $\tilde y_s$, and moreover
it makes the computations to obtain $\bar n$ and the points
$\tilde y^\eta_{\omega_1^{\bar n}}$. The binary length
$\ell(\mathtt{P})$ satisfies
$$
\ell(\mathtt{P}) \preccurlyeq \ \varepsilon^{-\frac D k-\delta}
$$
since $\varepsilon$ is specified with $O(\log(\varepsilon^{-1}))$ bits; $\rho$,
$D$, $M$, $K$ and $k$ do not depend on $\varepsilon$ and can be
approximated by rational numbers. The coefficients $\tilde
c_{i,p}$ and the points $\tilde y_s$ are constructed as in the
previous proofs with precision $\varepsilon'$, hence each of them needs
$O(\log(\varepsilon^{-1}))$ bits of information and their number is $N(k+2) =
O(\varepsilon^{-\frac D k-\delta})$. Finally all the computations to
obtain $\mathtt{C}$ need $O(1)$ bits of instructions. Hence (\ref{ck-1})
follows.

We now prove (\ref{ck-2}). We define a class of particular scaling
functions $S(\alpha)$ on $\mathcal{I}^\infty$ to construct differentiable
Cantor sets with the given distortion complexity.

Let us denote by $\mathcal{I}^*:= \cup_{n\in \mathbb N}\ \mathcal{I}^n$ the countable set
of finite strings $s$ written using the alphabet $\mathcal{I}$. Let
$(\lambda_s)_{s \in \mathcal{I}^*}$ be a family of independent
identically distributed random variables with values in the
interval $(0,1)$ and absolutely continuous distribution with
density $f(x)$ bounded above and below away from zero. Note that the
empty string $\sharp$ belongs to $\mathcal{I}^*$ and therefore there is an
associated random variable $\lambda_\sharp$.

Let $0<\zeta <1$, $0<\rho <1$ and $\rho<\theta<1$ be given
constants, with $\rho$ determining the contraction rate. $\zeta$ will be chosen
small enough later on. We will
only consider central Cantor sets, namely the two components of
the scaling functions will be equal. We define the scaling
function
$$
S_\lambda(\alpha) := \rho + \zeta \sum_{q=1}^\infty\ \theta^{q-1}\
\lambda_{\alpha_1^{q}} \qquad \forall\ \alpha \in \mathcal{I}^\infty
$$
which depends on the realisation of the family $(\lambda_s)$.
We remark that for any realisation it holds
\begin{equation} \label{ck-scaling-estimate}
\rho \le S_\lambda(\alpha) \le \rho + \frac{\zeta}{1-\theta}
\qquad \forall\ \alpha \in \mathcal{I}^\infty\ .
\end{equation}
Hence if $\zeta$ is small enough, the rate of contraction is
almost $\rho$. It is also useful to define the truncated scaling
function $\tilde S_\lambda$ by
\begin{equation} \label{truncated}
\tilde S_\lambda(\omega_1^m) := \rho + \zeta \sum_{q=1}^{m} \
\theta^{q-1} \ \lambda_{\omega_1^{q}}  \quad \forall\ m\ge 0.
\end{equation}
Using the relations
\begin{equation} \label{ck-cantor}
\frac{|J_{i\omega_1^m}|}{|J_{\omega_1^m}|} = \tilde
S_\lambda(\omega_1^m) \qquad \forall \ i\in \mathcal{I}
\end{equation}
we can construct a central Cantor set $\mathscr{C}_\lambda$ generated by
the scaling function $S_\lambda$. From (\ref{ck-scaling-estimate})
it follows that the Cantor set $\mathscr{C}_\lambda$ has box counting
dimension $D(\zeta)$ which satisfies
\begin{equation} \label{ck-box-count}
D(\zeta) = -\ \frac{\log 2}{\log \rho} + O(\zeta) \qquad \mbox{ as
}\ \zeta \to 0.
\end{equation}

We now consider the differentiability of the IFS generating
$\mathscr{C}_\lambda$. By (\ref{ck-scaling-estimate}) and the definition
(\ref{scaling-distance}) of $d_S$ it follows
$$
\rho^n \le d_S(\omega,\tilde \omega) \le \left(
\rho + \frac{\zeta}{1-\theta} \right)^n \qquad n=|\omega \cap
\tilde \omega|
$$
for any $\omega,\tilde \omega \in \mathcal{I}^\infty$. Moreover for any
$\omega \not= \tilde \omega$ it holds
$$
|S_\lambda(\omega) - S_\lambda(\tilde \omega)| \le 2 \zeta \
\frac{\theta^{n+1}}{1-\theta} \qquad n=|\omega \cap \tilde
\omega|.
$$
Hence for $m>n$ we have diffeomorphisms from $A(\omega_1^m)$ into
$A(\tilde \omega_1^m)$ with derivatives bounded by a constant
$C(\omega_1^m, \tilde \omega_1^m) =O(\theta^{n+1})$. These facts
together with relation (\ref{ck-condition}) imply that the Cantor
set $\mathscr{C}_\lambda$ is of class $C^k$ with
\begin{equation} \label{ck-diff}
k = 1+ \frac{\log \theta}{\log \rho} \ge 1.
\end{equation}

Let $0<\varepsilon<1$ be fixed and small enough depending on the
constants $\rho,\theta,\zeta$. Let $\lambda:=(\lambda_s)$ and
$\lambda':=(\lambda'_s)$ denote two different realisations of
the family of random variables. We give a condition on $\lambda$
and $\lambda'$ to have $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathscr{C}_{\lambda'})> \varepsilon$.
We denote
\begin{equation} \label{p-bar}
\bar p=\left[\frac{\log (C \varepsilon\ \zeta^{-1})}{\log(\rho \theta)}\right]
\end{equation}
where $C$ is a positive constant (independent of $\varepsilon$) to be specified later on.

For any $\sigma \in \mathcal{I}^*$, we denote by $J_{\sigma}$ and
$J'_{\sigma}$ the intervals associated to $\sigma$ in
$\mathscr{C}_{\lambda}$ and $\mathscr{C}_{\lambda'}$ respectively.

\begin{lemma} \label{lem:ck-dist}
Assume there is $0\le p\le \bar p$ satisfying
\begin{equation} \label{ipot}
\max\limits_{\omega_1^p\in \mathcal{I}^p}\
d_{\scriptscriptstyle{\mathrm{H}}}(J_{\omega_1^p},J'_{\omega_1^p})
> \varepsilon.
\end{equation}
Then $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathscr{C}_{\lambda'})> \varepsilon$.
\end{lemma}

\noindent \emph{Proof.} Denote by $p$ the smallest integer for
which the above inequality holds and by $\omega_1^p \in \mathcal{I}^p$ the
string realising the maximum. We apply Lemma \ref{lemma:1} with
$I=J_{\omega_1^{p-1}}$ and $I'=J'_{\omega_1^{p-1}}$. The
hypotheses on $I$ and $I'$ follow by the fact that (\ref{ipot}) is
violated up to $p-1$. The gaps $H$ and $H'$ have size at least
$$
\rho^{p-1} >(\rho \theta)^{\bar p} = C \varepsilon\ \zeta^{-1}>2\varepsilon
$$
for $\varepsilon$ small enough if $C\zeta^{-1}>2$.

Finally since $d_{\scriptscriptstyle{\mathrm{H}}}(J_{\omega_1^p},J'_{\omega_1^p}) > \varepsilon$ we have all the
hypotheses of Lemma \ref{lemma:1}. Hence the lemma follows. \qed

\begin{lemma}
Assume that there exists $0\le p \le \bar p$ and a sequence
$\omega_1^p\in \mathcal{I}^p$ such that
$$
|\lambda_{\omega_1^p} - \lambda'_{\omega_1^p}| > (\rho
\theta)^{-p} \ \frac{(4+2\rho^2) \varepsilon}{\zeta}\cdot
$$
Then $d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_{\lambda},\mathscr{C}_{\lambda'}) >\varepsilon$.
\end{lemma}

\noindent \emph{Proof.} Denote by $p$ the smallest integer for
which the above inequality holds. It is enough to assume that for
any $q<p$ condition (\ref{ipot}) is not verified, otherwise the proof follows
immediately from Lemma \ref{lem:ck-dist}.

Let $x$ (respectively $x'$) be the point in the boundary of
$J_{\omega_1^p}$ (respectively $J'_{\omega_1^p}$) which is not in
the boundary of $J_{\omega_2^p}$ (respectively $J'_{\omega_2^p}$).
Let $y$ (respectively $y'$) be the other boundary point of
$J_{\omega_2^p}$ (respectively $J'_{\omega_2^p}$). Since by the
recursive assumption $|y-y'|\le \varepsilon$, we have
$$
|x-x'|\ge |x-y-(x'-y')|-\varepsilon.
$$
Now since $|x-y|=|J_{{\omega_1^p}}|$ and $(x-y)$ and $(x'-y')$
have the same sign, we get
$$
|x-x'|\ge \big| |J_{{\omega_1^p}}|-|J'_{{\omega_1^p}}|\big|-\varepsilon
$$
This can also be written
$$
|x-x'|\ge \big|\tilde S_\lambda({\omega_2^p}) |J_{\omega_2^p}| -
\tilde S_{\lambda'}({\omega_2^p}) |J'_{\omega_2^p}| \big|- \varepsilon
\ge
$$
$$
\ge \big|\tilde S_\lambda({\omega_2^p}) - \tilde
S_{\lambda'}({\omega_2^p}) \big|\
\frac{|J_{\omega_2^p}|+|J'_{\omega_2^p}|}{2} -\frac{\tilde
S_\lambda({\omega_2^p})+ \tilde S_{\lambda'}({\omega_2^p})}{2}\
\big| |J_{\omega_2^p}|-|J'_{\omega_2^p}|\big|-\varepsilon \ge
$$
$$
\ge \big|\tilde S_\lambda({\omega_2^p}) - \tilde
S_{\lambda'}({\omega_2^p}) \big|\
\frac{|J_{\omega_2^p}|+|J'_{\omega_2^p}|}{2}\ -3 \varepsilon \ge \rho^p
\big|\tilde S_\lambda({\omega_2^p}) - \tilde
S_{\lambda'}({\omega_2^p}) \big|\ - 3\varepsilon
$$
since $d_{\scriptscriptstyle{\mathrm{H}}} \left( J_{{\omega_2^p}}, J'_{{\omega_2^p}}\right)\le
\varepsilon$ and $S_\lambda\ge \rho$.
From \eqref{truncated} we get
$$
\tilde S_\lambda({\omega_2^p}) - \tilde S_{\lambda'}({\omega_2^p})
= \zeta \sum_{q=2}^{p} \theta^{q-2} \left(\lambda_{\omega_2^{q}}-\lambda'_{\omega_2^{q}} \right)
$$
and from (\ref{ck-cantor}) we have
$$
\zeta \sum_{q=2}^{p-1} \theta^{q-2} \left(\lambda_{\omega_2^{q}}-\lambda'_{\omega_2^{q}} \right) =
\frac{ (|J_{\omega_1^{p-1}}|-|J'_{{\omega_1^{p-1}}}|)
(|J_{{\omega_2^{p-1}}}|+|J'_{{\omega_2^{p-1}}}|)}{2\
|J_{{\omega_2^{p-1}}}||J'_{{\omega_2^{p-1}}}|}
$$
$$
+\frac{ (|J_{{\omega_1^{p-1}}}|+|J'_{{\omega_1^{p-1}}}|)
(|J'_{{\omega_2^{p-1}}}|-|J_{{\omega_2^{p-1}}}|)}{2\
|J_{{\omega_2^{p-1}}}||J'_{{\omega_2^{p-1}}}|}\cdot
$$
Since $|J_{{\omega_1^{p-1}}}| \le |J_{{\omega_2^{p-1}}}| \le (\rho
+ \frac{\zeta}{1-\theta})^{p-2}$ we get (using again $d_{\scriptscriptstyle{\mathrm{H}}}
\left( J_{{\omega_2^p}}, J'_{{\omega_2^p}}\right)\le \varepsilon$,
and $S_\lambda \ge \rho$)
$$
\left|\ \zeta \sum_{q=2}^{p-1}\ \theta^{q-2} \left(
\lambda_{\omega_2^{q}}-\lambda'_{\omega_2^{q}} \right) \right|
\le 2\ \rho^{-p+2}\ \varepsilon\ .
$$
Hence
$$
|\tilde S_\lambda({\omega_2^p}) - \tilde
S_{\lambda'}({\omega_2^p})| \ge \zeta \theta^{p-2} |\lambda_{{\omega_1^p}}-\lambda'_{{\omega_1^p}}|-2\ \rho^{-p+2}\
\varepsilon .
$$
We conclude that
$$
|x-x'| \ge \zeta(\rho \theta)^p \
|\lambda_{{\omega_1^p}}-\lambda'_{{\omega_1^p}}|-
(3+2\rho^2)\varepsilon.
$$
Therefore the lemma follows by applying Lemma \ref{lemma:1}. \qed

We now want to estimate for a given realisation
$\lambda$ of the family $(\lambda_s)$ the probability of the
event
$$
\mathscr{E}_{\bar p}(\lambda) = \sup_{0\le q\le {\bar p}} (\rho
\theta)^q\ \sup_{\sigma \in \mathcal{I}^{q}}
|\lambda_\sigma-\lambda'_\sigma| \le \frac{(4+2\rho^2)\
\varepsilon}{\zeta}\cdot
$$
By independence of the family $(\lambda_s)$ we get
$$
\mathbb P \left( \mathscr{E}_{\bar p} (\lambda) \right) \le
\prod_{q=0}^{\bar p} \left(C\ (\rho \theta)^{-q}\ \varepsilon \
\zeta^{-1} \right)^{2^{q}}
$$
where
$$
C=(4+2\rho^2) \sup_{x\in[0,1]} f(x)
$$
where $f$ is the density of the random variables $(\lambda_s)$.

These relations imply that
\begin{eqnarray*}
\log \mathbb P \left( \mathscr{E}_{\bar p} (\lambda) \right) & \le &
\sum_{q=0}^{\bar p}\ 2^{q} \left( \log (C \varepsilon\ \zeta^{-1})
-q\log(\rho\theta) \right) \\
& \leq &  2^{\bar p +1}\log(\rho\theta) - (3+{\bar p}) \log(\rho\theta).
\end{eqnarray*}
For a fixed $\delta \in (0,1)$, define
$a_\ell:=2^{\ell(-\delta+\frac D k)}$ and choose $\varepsilon =
2^{-\ell}$. For any $\ell$, there are at most $2^{a_\ell}$
different binary programs $(\mathtt{P}_j)_{1\le j \le 2^{a_\ell}}$ of
length $a_\ell-1$, which generate at most $2^{a_\ell}$ different
sets $\mathtt{C}_j:=\mathtt{C}(\mathtt{P}_j)$. We define
$$
V_{\ell,j}:= \set{\lambda : d_{\scriptscriptstyle{\mathrm{H}}}(\mathscr{C}_\lambda,\mathtt{C}_j) < 2^{-\ell}}.
$$
Then
$$
\set{\lambda : \Delta(\mathscr{C}_\lambda,2^{-\ell})< a_\ell} \subset
\bigcup_{j=1}^{2^{a_\ell}}\ V_{\ell,j}.
$$
If $V_{\ell,j}$ is not empty, there exists $\lambda$ such that
$V_{\ell,j} \subset \mathscr{E}_{\bar p} (\lambda)$. Then
$$
\mathbb P\left( \bigcup_{j=1}^{2^{a_\ell}} V_{\ell,j} \right) \le
2^{a_\ell} \mathbb P\left( \mathscr{E}_{\bar p} (\lambda)\right) \le$$
$$
\le O(1) \exp \left( 2^{\ell(-\delta+\frac D k)} \log 2 +
2^{\bar p +1} \log(\rho\theta) - (3+{\bar p}) \log(\rho\theta)\right)\ .
$$
Using (\ref{ck-box-count}), (\ref{ck-diff}) and (\ref{p-bar}), it
follows that for any $\delta >0$ one can find $\zeta>0$ small
enough such that this is summable in $\ell$. Hence we can apply
Lemma \ref{lemma:2} to complete the proof. \qed

redpajama_set_name: RedPajamaArXiv


Corner Cottage is a delightful, traditional Cotswold stone cottage in Lower Oddington, an idyllic village just a few miles from the attractive market town of Stow-on-the-Wold. With a double bedroom and second twin bedroom, the cottage is suited to couples or a small family. The spare room with day bed is ideal for accommodating a baby's travel cot. Character features at the cottage include original flagstone flooring, stripped pine doors and inglenook fireplace with wood burning stove. The ground floor features a cosy sitting room and well equipped country style kitchen diner with a semi-glazed door leading to a suntrap courtyard with seating.
Lower Oddington is perfectly located to explore the countless delights of the North Cotswolds from historic houses, beautiful gardens, picturesque villages and visitor attractions. Broadway, Chipping Campden and Burford are all within easy distance, each with their own distinctive charm and handsome buildings. Sophisticated Cheltenham and Roman Cirencester are just a little further afield and each can be reached in approximately 40 minutes' drive.
Double bedroom, twin bedroom and family shower room.
Spare room with single day bed.
Being a period property, headroom is restricted when entering the kitchen and spare bedroom.
Built in oven, halogen hob and microwave.
Corner Cottage benefits from two excellent pubs within easy strolling distance, The Fox at Oddington around the corner and the Horse and Groom in neighbouring Upper Oddington easily reached on foot.
Across the fields in the opposite direction and past the beautiful St Nicholas church is Daylesford Organic Farmshop where there is an excellent section of home and garden wares, tasty organic food and a blissful spa where you can indulge in a spot of pampering.
The area is a rambler's paradise as footpaths run through Oddington, connecting to the Diamond Way and the Oxfordshire Way providing ample opportunities for walking.
Historic house and garden enthusiasts will delight in nearby Chastleton House and Sezincote House & Gardens.
The family attractions on offer nearby are guaranteed to keep little ones entertained with Birdland Park & Gardens and the Cotswold Farm Park to name just two.
For additional information on what to do in the area, please click here and see our 'Things to do' page.


text:
Sacura parva är en fiskart som beskrevs av Phillip C. Heemstra och Randall, 1979. Sacura parva ingår i släktet Sacura och familjen havsabborrfiskar. Inga underarter finns listade i Catalogue of Life.

Källor

Havsabborrfiskar
parva

redpajama_set_name: RedPajamaWikipedia


Stacey Floersch of Omaha and Diane Leffler of West Point share a wonderful friendship.
Yet they probably would have never met, except for one big thing they have in common: Both have sons studying for the priesthood for the Archdiocese of Omaha.
Stacey was first introduced to the Leffler family when her son, Paul, broke his leg playing soccer three years ago in his first year in seminary. She received a telephone call from Diane's son, Taylor, also studying at Kenrick-Glennon Seminary in St. Louis.
That sent Stacey straight down to St. Louis, meeting Taylor for the first time. ("Taylor was amazing, he was with Paul the whole time," she said.) Just weeks later, she met Diane at an archdiocesan dinner for the parents of seminarians.
The two hit it off immediately. And like other seminarian parents through the years, they have gotten to know each other well. That's in part due to annual "back-to-school, seminarians-with-their-families" picnics with Archbishop George J. Lucas, a seminarian parents' dinner each fall and a gathering at Christmas, also with the archbishop.
But there is even more to this particular relationship.
Diane, an outgoing woman who laughs easily and often, has been battling pancreatic cancer for the last two years. A member of St. Mary Parish in West Point, she frequently travels to a cancer center in Omaha for chemotherapy treatments.
And Stacey, a quietly generous introvert from St. Robert Bellarmine Parish in Omaha, has become a mainstay of prayer and support, bringing lunch to many of Diane's visits.
"We never talk about her illness at all," Stacey said. "There's always something to talk about," such as the latest goings-on with their sons and daughters.
That includes now-transitional Deacon Taylor Leffler preparing for his June 2 ordination to the priesthood with fellow transitional Deacons Patrick Moser and Padraic Stack. And Paul Floersch, now in Rome for his first year of graduate-school theology.
Stacey recently gave Diane some centerpiece lanterns she and her husband, Mark, used for their second-oldest son's wedding last December, to help Diane and her husband, Dana, decorate for the priest ordination party they plan in West Point. And Diane is there to help with any need, Stacey said.
Stacey and Diane's easy relationship, based on faith and the common bond of seminarian sons, is similar to that which develops naturally among many seminarian parents, though often not as dramatically.
Deacon Moser's mother, Sandy, said she and her husband, Edward, of St. Theresa of Avila Parish in Clearwater, have attended several of the seminarian gatherings in Omaha, about three hours from their home. The common experience of having seminarian sons makes for solid friendships, and they discover parents of seminarians closer to home, as well, such as in O'Neill and West Point.
"It's nice to know they understand what you're going through," she said.
The archdiocesan Vocations Office does its part to encourage these ties by organizing the gatherings, which include the archbishop and Father Andrew Roza, vocations director.
The gatherings give parents a chance to visit with one another, with the archbishop and with their sons' friends in the seminary, Father Roza said. The parents' dinner in particular gives them time just with one another, and even more opportunity to ask questions of both him and the archbishop, he said.
Now there is talk among some parents of starting a monthly rosary group to pray for their sons, Diane and Stacey said. Father Roza said he is in full support.
"Of course, I love that kind of thing," he said.


text:
Ensuring innovation through autonomy at work
By Jens Hauglum Jens Hauglum - Head of Innovation at FINN.no
Co-Authored By Bente Mari Kristiansen Bente Mari Kristiansen, Bjørn Henrik Vangstein Bjørn Henrik Vangstein, Karina Birkeland Lome Karina Birkeland Lome
March 5, 2014 at 5:14pm
Schibsted
idea management
FINN.no is Norway's largest online marketplace. FINN.no is a story of disruption and innovation, and we have a goal of being one of the most innovative companies in the world. This story is about our people. The full story - people, processes and tools - can be read on the MIX-site by following this link.
FINN.no is a Norwegian company founded in 2000. The company has 400 employees and yearly revenues of 200 million USD. FINN.no is owned by Schibsted Media Group, one of Norway's largest media companies founded in 1860. Schibsted's business is divided into two main parts: "Classifieds" and "Media Houses"
FINN.no is a story of disruption and innovation. In the late 1990's Schibsted decided to start a new online-company, outside the established organization, to really take advantage of the new possibilities given by the Internet. The idea was to move the newspaper classified ads online, and by that enable new revenue streams and business models. FINN.no was founded in 2000 to be that spearhead, and was given the mandate to cannibalize the newspapers business model. Now, fourteen years later, online classifieds are a major part of Schibsted's revenue and FINN.no is one of 20+ companies in Schibsted Classified Media.
Image 1: Split of revenues and EBITDA in Schibsted Group between online and offline (i.e. print/newspapers)
Today the marketplace consists of several different categories; cars, real estate, jobs, travel, general merchandise and services/craftsmen. FINN.no is Norway's fourth largest website (measured in unique users) and market leader in almost all categories. Measured in page views, FINN.no is Norway's largest website with over 800 million page views per month.
FINN.no has also succeeded in establishing a revenue model based on people paying to advertise, whereas various competitors offer such listings for free. As a result FINN.no is very profitable with a profit margin above 48%.
Innovation is a strong part of our company's history since FINN.no itself is an innovation. However, when we looked at our large market share in 2006, we saw a strong limitation for further growth. We have also seen stronger competition from global competitors like LinkedIn and Facebook. Because the Internet is such an effective distribution channel, the competition is global and highly dynamic. A startup can become a large competitor within a year, a huge contrast to the old industrial economy. Based on this analysis we decided to gear up our innovation efforts.
Key Innovations & Timeline
The most important measures we have taken to strengthen the people part of our innovation efforts are described in the following:
Since we strongly believe that innovation is about people we measure and benchmark our efforts in building a culture where innovation can thrive.
FINN.no's values are Precision, Drive, Spirit and Tolerance. The values are used actively, both as a feedback tool and as a basis for rewards and recruitment. The values are also directly linked to innovation behaviors:
"Precision" is about learning and improvement
"Drive" is about execution and self-empowerment
"Spirit" is about creativity and fun
"Tolerance" is about accepting diversity, tolerate mistakes and giving feedback
"We have a great diversity here and that demands using the value Tolerance actively. In my sales team I have a heavy rocker and a physiotherapist, not exactly the usual sales background. I find Drive and Precision natural parts of being a good salesperson, but Spirit is also actively used. We do it with humor around here and you can hear bursts of laughter all the time. I started at FINN 12 years ago when we were 25 employees. I remember back then when I thought about what the future would be. Now we are 350 employees but I still feel we have kept much of the same culture"
—Alexander Arvidsson, Sales manager
Twice a year every individual gets feedback based on how they have adhered to these values. Feedback is given by colleagues in the same team and the team manager, both in writing and orally. Oral feedback is given in group sessions facilitated by an external consultant. Every team member gets feedback from the rest of the team on what is good and what should be improved. The value "Tolerance" is used to create a good atmosphere for constructive feedback.
Once a year we organize a party called FINN Awards where prizes are given to teams or individuals in different categories, one being "Innovation of the year". The values are used as a part of the evaluation criteria in every category.
To have an external benchmark on how we succeed in building a healthy corporate culture we have participated in Great Place to Work for the last eight years. GPTW measures elements like autonomy, freedom and influence, important building blocks for an innovative culture. We have succeeded in becoming the Greatest Place to Work twice (2011 and 2012) in Norway, and have been listed top 4 in 2006-2013. 95% of all employees say they are looking forward to go to work every day. This serves as a good benchmark, but also as a tool for strengthening employer branding. Feedback given in GPTW is actively used by the management group to adjust and prioritize actions.
Another effect of the emphasis on people and culture is employer branding. FINN.no has succeeded in becoming one of the most popular IT-companies among students. "Innovation" is also the word being mentioned the most when students in a survey made by Universum (fall 2012) were asked to say one word that comes to mind when hearing FINN.no,
"When we started FINN we brought in people with different backgrounds. Since we were going to establish marketplaces for Real Estate, Cars and Jobs we brought in people with experience from broking, car sales and recruitment. This also had an impact on culture and management. We also were rebellious and bent the rules. One prerequisite given by our owners was that we couldn't hire salespeople. We hired "marketpeople" and used them as sales staff"
—Christian P. Halvorsen - CEO
Autonomy must have direction, without direction individuals and teams will end up working on what they define as important not what is important for the company. We have defined a high-level process to visualize the connections between goals and where teams and individuals have different levels of autonomy. The blue circles are management tasks: monitor status and set goals. When goals are prioritized and understood, teams or individuals can go about finding insights, generate ideas and finding the right actions to implement. When actions are implemented, results can be checked to see if the goal is obtained. If not, a new round of insights, actions and implementation is carried out.
By clarifying that management/leadership is about setting goals/directions and that teams and individuals should define and implement the right actions, you enhance autonomy on team and individual level but also ensure the whole organization works in the same direction.
Personal Drive
Each year we arrange the FINNovation-day, a 24-hour idea hackaton. FINNovation day is all about creativity and playfulness. All employees can attend, last year almost 20% attended. The output can be ideas and concepts that can be implemented, but the purpose of the day is mainly to offer a training ground for skills and behaviors. Either you are trying to "sell" an idea or help nurture and develop an idea. The day starts off with forming teams and elaborate ideas. The teams are free to explore almost everything, both ideas that can fit FINN's current strategy or completely "wild" ideas. The hackaton ends with a presentation and poll in front of all employees, and prices are handed out. The ideas that fit FINN's strategy are then evaluated by the management team.
The most important aspect of the FINNovationday is the freedom to work on ideas that matter for the individual and the possibility to present it to all your colleagues and get an assessment by the management team. The FINNovation day bypass all formal "does and don'ts" and embrace engagement and autonomy.
One concrete idea that really grew into something of a game changer for FINN was our first iPad-app. A two-person team took advantage of the liberal experimentation mandate given them by the management group. Web developer Erlend Schei elaborates:
«While not being significant on FINN's roadmap, we could play a hunch on mobile apps. Exercising our freedom to experiment, we chose to go all in with iOS development with the iPad launch in 2010. Together with my boss, Eyvind Larre, we teamed up, taught ourselves iOS, and hired two summer interns. Today, the apps team consists of 10 persons, and mobile is key in all development. »
To strengthen the innovation culture and to foster an intrapreneurial skillset we have launched a concept called Sandbox.
Sandbox is a concept that allows employees to develop their own products based on data from FINN.no. FINN.no, being an online marketplace, has lots of user data and Sandbox enables the use of some of these datasets. Employees sign a contract with FINN.no allowing them the use of data. When a product is launched, any revenue is split 70/30 (Employee/ FINN.no). Besides from the potential upside, a Sandbox-contract also gives access to a range of support: ads on FINN.no, help from the innovation team, access to server and development-tools and Schibsted's payment platform.
Sandbox may foster competitors to FINN.no, but we believe that the benefits of intrapreneurship overshadow the fear of competition. It is also a useful tool to support autonomy and involvement. If someone has a great idea, but it doesn't fit our current strategy, they can be given the opportunity to launch it as a Sandbox initiative. As a "Sandbox'er" you are a true entrepreneur, and no strings are attached when it comes to processes and tools.
15 employees have signed a Sandbox-contract and last year the first solution was launched and is available in Apple App Store.
"As a developer I have used Sandbox to build a product called GrabIT. It is now available on Apple's AppStore. I believe FINN has a strong culture of a flattened management structure and colleagues eager to help. My five minute drop-in meeting with the SVP of Product Development saved me weeks in waiting time, him an unnecessary meeting and FINN hour of administration, going up and down the organizational hierarchy."
—Jon Georg Berntsen – system developer
To succeed in building an innovation culture, and to learn more about the unknown, experiments are one of the most important building blocks. We also use experiments to strengthen autonomy. If an experiment doesn't require a lot of effort, or jeopardize the customer experience, it can be conducted without authorization. The beauty of an experimental culture is that you optimize learning and limit the fear and shame connected to failure. An experiment is built around a hypotheses, and hypotheses either stand or fall. In any case you have learned something, and this learning is valuable. If people are encouraged to conduct experiments, without formal authorization-processes, but with a requirement to share learning, you can enhance autonomy.
To make use of experiments in a structured way we have tried Lean Startup in several projects:
"In the first lean startup project at FINN we experienced that the fear we had that our major customers wouldn't be willing to experiment was exaggerated. The limited time, effort and cost involved for our partners combined with maximum learning and no commitment to launching the product made it a rather easy sell. We were open about that it was all about learning and that we might scrap the product idea. Another effect was that the speed needed to conduct experiments showed that we needed to improve the interface between sales and development. In the next project we will put more effort in involving sales earlier in the project"
—Adne Skjelstad – Product manager
Some key lessons learnt:
Innovation is a result, not a process
Innovation can be enabled by technology, but must be achieved by people. Even if we are a part of a tech-intensive industry we firmly believe that technology alone cannot achieve what we aim for. FINN has 100+ developers, but even if we attract the best developers our competitive advantage in many ways lies in our ability to build face-to-face relations with our customers and truly understand their needs. The internet is a highly effective distribution channel, but it also enables users to migrate to other solutions quickly. Relations cannot only be made and managed online. In addition to all the company-wide efforts described in the previous chapters, we therefor see our sales staff as a tool to succeed with innovation
The prerequisites for innovation must be understood by managers on all levels. Management principles must support innovation. Previously we had an organizational structure that amplified suboptimal behaviors. In this perspective there was a wide range of management principles and behaviors. This was a good strategy in a growth-phase, but the profound challenges we now face calls for a stronger "FINN first" principle than before
The problem is not the lack of ideas or creativity, but the ability to execute
Idea generation needs direction. If you want ideas with impact you need a clear problem definition and a clear problem owner that can take ownership for execution
We believe that many of the measures we have described are context-related and many of them are intertwined. Other companies will experience other effects and have other lessons to share if they implement the same measures.
Harvard Case Study N9-707-474, April 04 2007 - Schibsted
http://engageinnovate.wordpress.com/2012/06/15/finn-no-gets-innovation/
You need to register in order to submit a comment.
Join the MIX now
Does Your Business Need a Facilities Manager?
By Mike T Deane Mike T Deane
Is Your Business Structure Failing You?
By Emelie Hyde Emelie Hyde
How Happy Employees Lead to a Successful Business
By Angelina Harper Angelina Harper
editor and blogger
Maintaining Company Culture With a Remote Workforce
Useful Digital Marketing Solutions That Help Drive More Sales
Describe a real-world innovation in the way your organization (or one you know) is managed.
MIX Pulse
Creating a Leadership Advantage Announcing the Winners of the Leaders Everywhere Challenge
Announcing the Digital Freedom Challenge How do you promote autonomy without losing control? Share your stories and ideas.
Announcing the Finalists We are proud to announce the eighteen finalists of the Leaders Everywhere Challenge, the second leg of the Harvard Business Review/McKinsey M-Prize for Management Innovation.
Is big the enemy of good? What can we do to keep our organizations agile—even as they grow? Five tested strategies from a fast-growing, inventive and open organization, by Joris Luijke of Atlassian.
Hack the MIX Join our first ever Hack the MIX Hackathon and help us develop the future of the MIX community. Share your ideas now >>
What Innovators Can Learn from Artists Lately a number of business leaders have begun to embrace the arts as an integral part of the human enterprise that ought to be woven into the fabric of every business.
Watch Daniel Pink: What makes people tick at work? Daniel Pink describes what's wrong with how we think about what makes people tick—and how to rethink what helps them soar.

redpajama_set_name: RedPajamaCommonCrawl


text:
namespace UnicornHack.Utils.MessagingECS;

public interface IEntityManager
{
    IMessageQueue Queue
    {
        get;
    }

    bool IsLoading
    {
        get;
    }

    ITransientReference<Entity> CreateEntity();
    void RemoveEntity(Entity entity);
    Entity? FindEntity(int id);
    Entity? LoadEntity(int id);

    TComponent CreateComponent<TComponent>(int componentId)
        where TComponent : Component, new();

    void OnComponentAdded(Component component);
    void OnComponentRemoved(Component component);

    void OnPropertyValueChanged<T>(
        string propertyName, T oldValue, T newValue, int componentId, Component component);

    void OnPropertyValuesChanged(Entity entity, IPropertyValueChanges changes);

    void RemoveFromSecondaryTracker(ITrackable trackable);
}

redpajama_set_name: RedPajamaGithub


Praise For H2Pro TriSmart: ICL's H2Pro TriSmart provides everything required from a wetting agent, believes Stuart Hogg, Course Manager at The West Lancashire Golf Club.
Founded in 1873 and featured in the top 100 golf courses in Great Britain, The West Lancashire Golf Club is one of England's truest seaside tests. There are few golfers who come away from this revered links course, midway between Liverpool and Formby, in any doubt that every aspect of their game has been suitably examined.
Stuart, who has been in greenkeeping for just over thirty years, has been the Course Manager for four years and has worked exclusively at Links courses throughout his career.
"Does the sea bring challenges? No, because having grown up on Links courses I'm used to it. However, we probably dry out a lot quicker, we get wind burn, we get salt burn and we have to be more mindful of height of cuts.
The most recent addition to Stuart's range of ICL products is the H2Pro TriSmart wetting agent, but it was a decision that he did not take lightly.
Containing three water management technologies consisting of surfactant and polymer blends, TriSmart is renowned for providing great water penetration and an even water spread through the rootzone.
Stuart starts the programme at the end of February and applies TriSmart at a rate of 10L/ha every four to five weeks, depending on weather, until the end of July. Last year, he applied TriSmart to all of the greens and surrounds, which equates to an area size of 4 hectares, but due to the successful results the areas for treatment is set to significantly increase.
"With TriSmart I believe I got everything I was looking for in a wetting agent," said Stuart. "Considering the season we encountered; we had improved rooting and I believe that was due to the fact that TriSmart was pulling the soil moisture down a little bit more. I also didn't have to hand-water those areas at all which really helped in reducing irrigation and labour.
Stuart also praised the support he receives from ICL.