The logarithmic regime. We have the following direct consequence of previous theorems

Corollary 3. There exist C0> 1 and two functions F, G :R+→ R+ which are decreasing and converging to 0 at +∞ such that for all C > C0 we have that

N log C ≥ F

 T

log C



and T

log C ≥ G

 N

log C

 . (50)

Proof. Notice first that the function f :]0, 1]→ R : x → xe^1/x is strictly decreas-ing, and its image is [e, +∞). Let C0 := C₁∨ C2, where C₁, C₂ are the constants introduced, respectively, in Theorems 3 and 4. Define the function

F (x) =

1∧ β1 if 0≤ x ≤ K1f (1∧ β1), f⁻¹(x/K1) if x > K1f (1∧ β1),

where K1and β1are the constants provided by Theorem 3. This function is decreasing such that F (+∞) = 0. We want to show that if C > C0, then

N log C ≥ F

 T

log C

 . If N/ log C > 1∧ β1, then

N

log C > max

x∈R+

F (x)≥ F

 T

log C

 .

If instead N/ log C ≤ 1 ∧ β1, then by Theorem 3 we can argue that T

log C ≥ K1

N

log CC^1/N= K₁f

N

log C

 , which implies that

N

log C ≥ f⁻¹

 T

K1log C



= F

 T

log C

 . In the same way it can be shown that

T

log C ≥ G

 N

log C

 ,

Fig. 5. The grey region in this figure represents the set in which the pairs (N/ log C, T/ log C) cannot belong.

where

G(x) =

21∧ γ2 if 0≤ x ≤ K2f (1∧ β1), f⁻¹(x/K2) if x > K2f (1∧ γ2), where K2 and γ2 are the constants provided by Theorem 4.

Remark. The constraint provided by the previous corollary is illustrated in Fig-ure 5 which shows explicitly the region in which the pairs (N/ log C, T/ log C) cannot belong. Observe moreover that the functions F (x) and G(x) in the previous corollary which determine the boundary of this region tend to 0 as the function f (x) = xe^1/x. This is in agreement with the behavior of the logarithmic regime exhibited in the nesting of both deadbeat quantized feedbacks and chaotic quantized feedbacks (see (22) and (28)). This implies that, up to multiplicative constants, our bounds appear to be quite tight and that the examples presented in section 4 cannot be improved much.

5.5. The case when |a| ≤ 2. All previous results have been obtained under the assumption|a| > 2. In fact, part of the results presented in this subsection can be extended to the case|a| ≤ 2. Indeed, in this case, using the second part of Theorem 6, we obtain the estimate

γk

2^k ≤

_r∧k



s=1

k + s− 1 2s− 1

 r s

s r

s NM k∧^NM_e

k∧^NMe

.

By similar arguments used to deal with the case|a| > 2, we obtain

T≥ n(1 − C⁻¹)− C⁻¹2

_r∧n−1



s=1

n + s 2s + 1

 r s

s r

s

×

NM n− 1 ∧^NM_e

n−1∧^NMe  2

|a|

n−1

for all n∈ N. Observing that

r∧n−1

s=1

n + s 2s + 1

 r s

s r

s

≤ 1

√π

n−1 s=1

2n− 1 2s + 1



e^s≤ 1

√π

n−1 s=1

2n− 1 2s + 1

 e^2s+1

≤ 1

√π(1 + e)²ⁿ⁻¹,

we thus obtain

T≥ n(1 − C⁻¹)− C⁻¹ 2

√π(1 + e)²ⁿ⁻¹

NM n− 1 ∧^NM_e

n−1∧^NMe  2

|a|

n−1

≥ n(1 − C⁻¹)− C⁻¹Aⁿ⁻¹

NM n− 1 ∧^NM_e

n−1∧^NM_e

,

where A := ^4(1+e)_|a|√π³ and where the last inequality holds if n≥ 2. The previous in-equality looks exactly like (43). This immediately implies that Theorem 4 also holds true for|a| ≤ 2. We can instead only recover a part of Corollary 3: (50) remains true for small values of γ, as it is easy to see from the proof we gave.

5.6. Stabilizing quantized feedbacks. In this section, we will show that quan-tized control strategies yielding stability or even almost stability, but with only a countable subset of points never entering inside J , require a number of quantization intervals which grows at least logarithmically in C. The result is based on Theorem 7 which is given in the last section.

Theorem 5. If Γ is almost (I, J )-stable and if the set of points in I never entering inside J is at most countable, then there exists β > 0, only depending on a such that

N/ log C≥ β for all C > 1.

Proof. Using (87) we can argue that

n−1 k=1

γk

|a|^k ≤ e^Ne

+∞



k=0

k + 2N− 1 2N− 1

  2

|a|

k

= e^Ne



1−_|a|²2N =

 e^1/e|a|² (|a| − 1)²

N

.

By letting A := ₍^e_|a|−1)^1/e|a|22, from (34) we can argue that P

T_{(I,J )}≥ n

≥ 1 − C⁻¹− A^NC⁻¹≥ 1 − C⁻¹(1 + A)^N. (51)

Since Γ is almost stable, by Proposition 1 we have thatE(T(I,J )) < +∞, which implies that

nlim→∞P

T_{(I,J )}≥ n

= 0.

From this and (51) we can argue that 1− C⁻¹(1 + A)^N≤ 0, which implies that N≥ log C

log(1 + A).

6. Estimation of paths in a class of weighted graphs. For proving our main result, namely Theorem 2, we introduce a class of weighted graphs and propose a method for bounding the number of paths on this graphs. In the last section, we will show how this bound can be used for proving Theorem 2. We use this strategy which considers this graph abstraction because the general result we are going to prove is useful to deal with more general situations, such as quantized controller with memory or the case in which the state of the system is multidimensional (see [10]).

Consider a direct graph G on a vertex set X (which is not necessarily finite or countable). For any choice ofX1, . . . ,Xk ⊂ X we define Fk[x1∈ X1, . . . , xk∈ Xk] to be the set of paths x₁· · · xk ∈ X^∗ on the graphG such that x1∈ X1, . . . , x_k ∈ Xk.

Assume the graph G has the following structure. We assume there exist a finite partition

X = X1∪ X2∪ · · · ∪ XN,

a subsetXP ⊆ X , and a function q : X →]0, 1[ with the following properties.

(A) There exist numbers q1, . . . , qN ∈]0, 1[ such that q(x)≤ qi ∀x ∈ Xi,

q(x) = qi ∀x ∈ XP,i:=XP∩ Xi.

(B) There exist positive numbers D1and α1such that, for every x^∈ X , X^⊆ X , and k≥ 2,

#Fk[x₁= x^, x₂, . . . , x_k−1∈ X , xk ∈ X^]≤ D1

q(x^)

infx^∈X^q(x^)α^k₁⁻². (C) There exist positive numbers D2 and α2 such that, for every x^ ∈ X , i ∈

{1, . . . , N}, and k ≥ 2,

#Fk[x₁= x^, x₂, . . . , x_k−1∈ X \ XP, x_k ∈ Xi]≤ D2α^k₂⁻². Then, if we define

γk,h= sup

x∈XP,h

#Fk[x1= x^, x2, . . . , xk∈ X ], h = 1, . . . , N,

γ_k=

N h=1

γ_k,h, (52)

we have the following result.

Theorem 6. We have the following bounds.

(1) If α1> α2, then

γk

α^k₁ ≤ 2

_r∧k



s=1

k− 1 s− 1

 r s

s r

s NM k∧^NM_e

k∧^NMe

∀k ≥ 1.

(53)

(2) If α₁≤ α2, then

γk

α^k₂ ≤

_r∧k



s=1

k + s− 1 2s− 1

 r s

s r

s NM k∧^NM_e

k∧^NM_e

∀k ≥ 1.

(54)

The constant r∈ {1, . . . , N} is independent of k, but may depend on the specific graph, while M depends only on the constants D1, D2, α1, α2.

The proof of the previous theorem is quite lengthy. For this reason we prefer to divide it into various steps.

Remark. As specified in the previous theorem M depends only on the constants D₁, D₂, α₁, and α₂, and r depends on the specific graph. These conditions can be exchanged and the same bounds can be shown to hold true in which instead r depends only on the constants D₁, D₂, α₁, and α₂, and M depends on the specific graph.

However, this exchange makes the bounds useless in general. Only in the specific situation considered in Proposition 5 does this point of view yield some advantages.

6.1. The proof of Theorem 6: Hierarchies of paths. Assume with no loss of generality that the subsetsX1,X2, . . . ,XN are ordered in such a way that

q1≥ q2≥ · · · ≥ qN. For any choice of integers

0 = N₀< N₁<· · · < Nr−1< N_r= N, we can partitionXP into the subfamilies

XP¹: ={XP,N0+1, . . . ,XP,N1} , XP² :={XP,N1+1, . . . ,XP,N2} , . . . , (55)

XP^r: ={XP,N_r−1+1, . . . ,XP,N_r} and consider, moreover,

XP^l+:=

3r j=l

XP^j,

X^l:= (X \ XP)∪ XP^l, X^l+:= (X \ XP)∪ XP^l+. For each k∈ N, h = 1, . . . , N, and l = 1, . . . , r, r + 1 define

γ_k,h,l:= sup

x^∈XP,h

#Fk[x₁= x^, x₂, . . . , x_k∈ X^l+].

From these definitions it follows thatX_P¹⁺=XP,X¹⁺=X , and X^(r+1)+:=X \ XP. This implies that γ_k,h,1= γ_k,h.

We present now two bounds on γk,h,lwhich will be used in what follows. The first bound is based on the decomposition of the paths inFk[x1 = x^, x2, . . . , xk ∈ X^l+] according to the last exit fromXP^l among the indices j = 2, . . . , k

Fk

x₁= x^, x₂, . . . , x_k∈ X^l+

 _k = 3

j=2 N_l

3

s=N_l−1+1

Fk

x1= x^, x2, . . . , xj−1∈ X^l+, xj ∈ XP,s, xj+1, . . . , xk∈ X^(l+1)+

×3 Fk

x1= x^, x2, . . . , xk ∈ X^(l+1)+

.

Applying property (B) it follows that, for all l = 1, . . . , r,

γk,h,l ≤

k j=2

N_l



s=N_l−1+1

sup

x^∈XP,h

#Fj

x1= x^, x2, . . . , xj−1∈ X^l+, xj∈ XP,s

(56) 

× sup

x^∈XP,s

#Fk−j+1

x_j= x^, x_j+1, . . . , x_k ∈ X^(l+1)+

+ sup

x^∈XP,h

#Fk

x₁= x^, x₂, . . . , x_k∈ X^(l+1)+

≤

k j=2

N_l



s=N_l−1+1

D₁qh

q_sα₁^j−2γ_{k−j+1,s,l+1}+ γ_k,h,l+1.

The second bound is based on the decomposition of the paths in Fk[x₁ = x^, x₂, . . . , x_k ∈ X^l+] according to the first entrance in XP^l+ among the indices j = 2, . . . , k:

Fk

x1= x^, x2, . . . , xk∈ X^l+

⎧ =

⎨

⎩ 3k j=2

3N s = N_l−1+1

Fk

x₁= x^, x₂, . . . , x_j−1∈ X \ XP, x_j∈ XP,s, x_j+1, . . . , x_k ∈ X^l+⎫

⎬

⎭

×3 Fk

x₁= x^, x₂, . . . , x_k ∈ X \ XP

.

Applying property (C) it follows that

γ_k,h,l≤

k j=2

N s=N_l−1+1

sup

x^∈XP,h

Fj

x₁= x^, x₂, . . . , x_j−1 ∈ X \ XP, x_j ∈ XP,s

(57) 

× sup

x^∈XP,s

Fk−j+1

xj = x^, xj+1, . . . , xk ∈ X^l+

+ sup

x∈XP,h

Fk

x1= x^, x2, . . . , xk∈ X \ XP



≤

k j=2

N s=N_l−1+1

D2α^j₂⁻²γk−j+1,s,l+ D2α^k₂⁻¹.

Notice that the previous bound holds true for l = 1, . . . , r, r + 1.

Define δ_k,l:=

N h=N_l−1+1

γ_k,h,l, δ˜_k,l:=

N_l−1

h=N_l−2+1

γ_k,h,l l = 1, . . . , r, r + 1,

which imply that δk,r+1= 0 for all k∈ N. Observe that from (56) we can argue that

δk,l≤

N h=Nl−1+1

⎛

⎝^k

j=2 N_l



s=N_l−1+1

D1

qh

qs

α^j₁⁻²γk−j+1,s,l+1+ γk,h,l+1

⎞

⎠

≤

k j=2

D1

N

h=N_l−1+1qh

qN_l

α^j₁⁻²

N_l



s=N_l−1+1

γk−j+1,s,l+1+

N_l



h=Nl−1+1

γk,h,l+1

+

N h=N_l+1

γ_k,h,l+1≤ D1β_l

k j=2

α^j₁⁻²δ˜_k−j+1,l+1+ ˜δ_k,l+1+ δ_k,l+1

= D1βl k−2



j=0

α^j₁δ˜k−j−1,l+1+ ˜δk,l+1+ δk,l+1 , where we define

β_l:=

N h=N_l−1+1

q_h qN_l

. (58)

On the other hand (57) implies that δ˜_k,l≤ D2(N_l−1− Nl−2)

⎛

⎝^k

j=2

α^j₂⁻²δ_k−j+1,l+ α^k₂⁻¹

⎞

⎠ ,

which using the convention

δ0,l = 1, l = 1, . . . , r, r + 1, is equivalent to

˜δk,l≤ D2ΔNl−1 k+1

j=2

α^j₂⁻²δk−j+1,l= D2ΔNl−1 k−1



j=0

α₂^jδk−j−1,l, where we defined ΔNl:= Nl− Nl−1.

Summarizing we have the following two inequalities holding for k≥ 1:

δk,l ≤ D1βl k−2



j=0

α^j₁˜δk−j−1,l+1+ ˜δk,l+1+ δk,l+1, l = 1, . . . , r,

δ˜k,l ≤ D2ΔNl−1 k−1



j=0

α^j₂δk−j−1,l, l = 1, . . . , r, r + 1.

(59)

Now define the sequences ηk,l, ˜ηk,lfor k = 0, 1, 2, . . . and l = 1, . . . , r, r + 1 by letting ηk,r+1 = δk,r+1 = 0 for k = 0, 1, . . ., and satisfying, for every k ≥ 0, the following recursive relations:

ηk,l= D1βl k−2



j=0

α^j₁η˜k−j−1,l+1+ ˜ηk,l+1+ ηk,l+1, (60)

˜

η_k,l= D₂ΔN_l−1

k−1 j=0

α^j₂η_k−j−1,l.

Notice that from the above recursive relations it follows that η0,l= 1 for every l.

This implies in particular that δk,l ≤ ηk,l for every k and l. In what follows we will estimate ηk,l by using the zeta transforms formalism.

Let

η_l(z) :=

+∞



k=0

η_k,lz^k, η˜_l(z) :=

+∞



k=0

˜ η_k,lz^k.

Then by some standard manipulations from (60) we obtain ηl(z) = D1βl

z

1− α1zη˜l+1(z) + ˜ηl+1(z) + ηl+1(z),

˜

ηl(z) = D2ΔNl−1 z

1− α2zηl(z), (61)

which yields

η_l(z) =



D₁β_l z 1− α1z+ 1



D₂ΔN_l z 1− α2z + 1



η_l+1(z).

By iterating this formula we obtain

η1(z) = 4r l=1



D1βl

z 1− α1z+ 1

 D2ΔNl

z 1− α2z + 1

 , (62)

where we used the fact that η_r+1(z) = 1.

6.2. The proof of Theorem 6: Combinatorial bounds. We now want to estimate the coefficients η_k,1 of η₁(z). We recall that γ_k = δ_k,1 ≤ ηk,1. In order to obtain such bounds we will first need to work out some combinatorics.

Bounds on the coefficients of elementary symmetric polynomials. Con-sider the following polynomial in the indeterminates x and y:

p(x, y) :=

4r l=1

βlx + 1

αly + 1

=

r s=0

s σ=0

¯

pσ,sx^σy^s. (63)

The aim of this part of the section is to determine bounds on the coefficients ¯p_σ,s if we assume that

r l=0

αl≤ α,

r l=0

βl≤ β.

Consider preliminarily the polynomial 4r

l=1

{αly + 1} =

r s=0

p^r_s(α1, . . . , αr)y^s. (64)

The polynomials p^r_s(α1, . . . , αr) are called elementary symmetric polynomials [11], and they can be expressed by the formula

p^r_s(α₁, . . . , α_r) = 

1≤l1<···ls≤r

4s j=1

α_lj.

We have the following first elementary result.

Lemma 3. Assume thatr

l=0αl≤ α. Then p^r_s(α₁, . . . , α_r)≤

r s

α r

s

. (65)

Proof. We will actually prove that bound (65) holds true, and it is attained when αi = α/r for all i = 1, . . . , r. For r = 2 it can be proven directly. For the general case, it is sufficient to notice that

p^r_s(α₁, α₂, . . . , α_r)

= p^r_s⁻²(α3, . . . , αr) + p²₁(α1, α2)p^r_s⁻²₋₁(α3, . . . , αr) + p²₂(α1, α2)p^r_s⁻²₋₂(α3, . . . , αr)

≤ p^rs⁻²(α₃, . . . , α_r) + p²₁_α

1+α₂

2 ,^α1+α₂ ²

p^r_s⁻²₋₁(α₃, . . . , α_r) + p²₂_α1+α2

2 ,^α1+α₂ ²

p^r_s−2⁻²(α3, . . . , αr)

= p^r_s_α1+α2

2 ,^α1+α₂ ², α3, . . . , αr

.

We come back to the problem of finding bounds on the coefficients ¯pσ,s of poly-nomial (63).

Lemma 4. For every 1≤ s ≤ r and 0 ≤ σ ≤ s, the following bound holds:

¯ pσ,s≤

s σ

 β s

σ r s

α r

s

. (66)

Proof. Observe first that p(x, y) =

4r l=1

[βlx + 1]αly + 1

=

r s=0

p^r_s

α1(1 + β1x), . . . , αr(1 + βrx) y^s. Moreover, we have that

p^r_s

α₁(1 + β₁x), . . . , α_r(1 + β_rx)

= 

1≤l1<···ls≤r

4s j=1

α_lj 4s j=1

(1 + β_ljx)

= 

1≤l1<···ls≤r

4s j=1

α_lj

s σ=0

p^s_σ(β_l1, . . . , β_ls)x^σ,

from which we can argue that, using Lemma 3,

¯

p_σ,s= 

1≤l1<···ls≤r

p^s_σ(β_l1, . . . , β_ls) 4s j=1

α_lj ≤

s σ

 β s

σ 

1≤l1<···ls≤r

4s j=1

α_lj

=

s σ

 β s

σ

p^r_s(α1, . . . , αr)≤

s σ

 β s

σ r s

α r

s

.

To apply the result provided by the previous lemma to our problem, we need to have bounds onr

l=1ΔNlandr

l=1βl. While it is evident that

r l=1

ΔN_l= N,

it is less clear how to bound the other sum. This will depend indeed on the way the subfamiliesXPⁱ are selected. It follows from (58) that

(67)

β_l=

r−l



k=0

N_l+k

h=N_l+k−1+1

qh

q_l ≤

r−l



k=0

ΔN_l+kq_Nl+k−1+1

q_Nl =q_Nl−1+1 q_Nl

r−l



k=0

ΔN_l+kq_Nl+k−1+1 q_Nl−1+1 . Choose inductively the numbers Nlas follows:

Nl= max 2

k≥ Nl−1+ 1| qk ≥1

2qN_l−1+1

5 . (68)

In this way we have that qN_l−1+1

qN_l ≤ 2, qN_l+k−1+1

qN_l−1+1 ≤ 2^−k. Inserting in (67), we thus obtain

βl≤ 2

r−l



k=0

ΔNl+k2^−k ∀l = 1, . . . , r, (69)

which implies that

r l=1

β_l ≤ 2

r l=1

r−l



k=0

ΔN_l+k2^−k= 2

r−1



k=0

_r−k



l=1

ΔN_l+k

2^−k≤ 2N

r−1



k=0

2^−k≤ 4N.

Hence it follows from Lemma 3 that in our case the coefficients ¯pσ,s can be bounded as

¯ pσ,s≤

r s

s σ

 ND₂ r

s 4ND₁

s

σ

. (70)

Bounds on the coefficients of the power series. Define the coefficients a^σ,s_k by

 1

1− α1z

σ 1 1− α2z

s

=

+∞



k=0

a^σ,s_k z^k. (71)

The aim of this part of the section is to determine bounds on the coefficients a^σ,s_k . Simple combinatorial manipulation shows that

a^σ,0_k =

k + σ− 1 σ− 1



α^k₁ ∀σ ≥ 1 ∀k ≥ 0.

(72)

In general we have the bound given by the following lemma.

Lemma 5. Assume that α1 > α2. Then, for every s≥ 0, σ ≥ 1, and k ≥ 0, we have

0≤ a^σ,sk ≤

 α₁ α1− α2

s

a^σ,0_k .

Proof. We start by proving that

a^σ,1_k ≤ α₁ α1− α2

a^σ,0_k

by induction on k. It is trivial if k = 0. Assume it to be true for k− 1 (with k ≥ 1), and let us prove it for k. Then

a^σ,1_k =

k h=0

a^σ,0_h α^k₂^−h=

k h=0

h + σ− 1 σ− 1



α^h₁α^k₂^−h

=

k−1 h=0

h + σ− 1 σ− 1



α^h₁α^k₂^−h+

k + σ− 1 σ− 1



α^k₁= α₂a^σ,1_k−1+

k + σ− 1 σ− 1

 α^k₁.

Using the induction we obtain a^σ,1_k ≤ α²α1

α₁− α2a^σ,0_k−1+

k + σ− 1 σ− 1

 α^k₁ =

( α₂ α1− α2

k + σ− 2 σ− 1



+

k + σ− 1 σ− 1

) α^k₁=

( α₂ α1− α2

k

k + σ− 1 + 1

) k + σ− 1 σ− 1

 α^k₁

≤ ( α2

α₁− α2

+ 1

) k + σ− 1 σ− 1



α^k₁= α1

α₁− α2

a^σ,0_k .

Finally assume that the assertion of the lemma holds true for s− 1. Then

a^σ,s_k =

k h=0

a^σ,s_h ⁻¹α^k₂^−h ≤

 α1

α₁− α2

s−1 k

h=0

a^σ,0_h α^k₂^−h=

 α1

α₁− α2

s−1

a^σ,1_h

≤

 α1

α₁− α2

s

a^σ,0_h .

6.3. The proof of Theorem 6: The final step. We now want to use the estimates obtained above for bounding the coefficients η_k,1.

From (62) we can argue that (73)

η1(z) =

r s=0

s σ=0

¯ pσ,s

 1

1− α1z

σ 1 1− α2z

s

z^σ+s=

r s=0

s σ=0

¯ pσ,s

+∞



h=0

a^σ,s_h z^h+σ+s

=

r s=0

s σ=0

+∞



k=σ+s

¯

p_σ,sa^σ,s_k−σ−sz^k=

+∞



k=0 r∧k



s=0 s∧k−s

σ=0

¯

p_σ,sa^σ,s_k−σ−sz^k,

where ¯p_σ,swas defined in (63) and a^σ,s_k in (71). Hence we have

ηk,1=

r∧k



s=0 s∧k−s

σ=0

¯

pσ,sa^σ,s_k−σ−s.

Decompose ηk,1 as follows:

η_k,1= η^_k,1+ η_k,1^ , where

η_k,1^ =

r∧k



s=1 s∧k−s

σ=1

¯

pσ,sa^σ,s_k−σ−s, η^_k,1=

r∧k



s=0

¯ p0,sa^0,s_k−s. (74)

Assume now that α₁> α₂, and fix M := 8D₁

α1 ∨ 2D₂

α1− α2 ∨D₂ α2

. (75)

Inserting bounds of Lemmas 4 and 5, we now obtain η^_k,1

α₁^k =

r∧k



s=1 s∧k−s

σ=1

¯

p_σ,sa^σ,s_k−σ−s α^k₁

≤

r∧k



s=1 s∧k−s

σ=1

s σ

r s

 4ND1

s

σ ND2

r

s α1

α1− α2

s

k− s − 1 σ− 1

α^k₁^−σ−s α^k₁

≤

r∧k



s=1 s∧k−s

σ=1

r s

s σ

s r

s NM

2s

s+σ

k− s − 1 σ− 1



≤

_r∧k



s=1

r s

s r

_{s s∧k−s}

σ=1

s σ

 k− s − 1 σ− 1



r∧k

max

s=1 s∧k−s

max

σ=0

NM 2s

s+σ .

Observe that

s∧k−s

maxσ=0

NM 2s

s+σ

=

NM 2s

s NM 2s

2s∧k

and that by (93),

r∧k

maxs=1

2NM 2s

s5

≤

NM/2 k∧^NM_2e

k∧^NM2e

r∧k

maxs=1

NM 2s

2(^s∧^k2)

≤

NM k∧^NM_e

k∧^NMe

,

which implies

r∧k

maxs=1,^smax^∧k−s

σ=0

NM 2s

s+σ

≤

NM k∧^NM_e

k∧^NMe

.

From this fact and using the combinatorial identity (89), we obtain η_k,1^

α^k₁ ≤

_r∧k



s=1

k− 1 s− 1

 r s

s r

s NM k∧^NM_e

k∧^NMe

. (76)

On the other hand, assuming k≥ 1, similar computations show that

η^_k,1 α^k₁ =

r∧k



s=1

¯ p0,s

a^0,s_k−s α^k₁ =

_r∧k



s=1

r s

 ND2

r

s k− 1 s− 1

 α^−s₂

 α^k₂ α^k₁

≤

_r∧k



s=1

r s

 NM r

s k− 1 s− 1



≤

_r∧k



s=1

k− 1 s− 1

 r s

s r

s max

1≤s≤r∧k

2NM s

s5 ,

which yields η_k,1^

α^k₁ ≤

_r∧k



s=1

k− 1 s− 1

 r s

s r

s NM k∧^NM_e

k∧^NMe

. (77)

Putting together (76) and (77), we obtain the final bound

γ_k α^k₁ ≤η_k,1

α₁^k ≤ 2

_r∧k



s=1

k− 1 s− 1

 r s

s r

s NM k∧^NM_e

k∧^NM_e

,

which proves Theorem 6 in the case when α₁> α₂. Observe that M depends only on the parameters α1, α2, D1, and D2.

In the case when α2≥ α1, we replace the estimate in Lemma 5 with 0≤ a^σ,sk ≤

k + s + σ− 1 s + σ− 1



α^k₂ ∀s + σ ≥ 1 ∀k ≥ 0 (78)

and fix

M = 8D1

α2 ∨2D2

α2

.

Similar computations show that, for k≥ 1, we can estimate γk

α^k₂ ≤ηk,1

α^k₂ ≤

_r∧k



s=1 s∧k−s

σ=0

r s

s σ

 NM 2r

s NM

2s

σ k− 1 s + σ− 1



(79)

≤

_r∧k



s=1

k + s− 1 2s− 1

 r s

s r

s NM k∧^NM_e

k∧^NM_e

.

The proof of Theorem 6 is now complete.

7. Proof of Theorem 2. The aim of this section is to obtain a representation of the language Σ_∗(Γ) by a finite state automaton or equivalently by a graph. This will be called a Markov representation of the language. Then we will show that this representation satisfies conditions (A), (B), and (C) of the previous section, and so we will be in a position to apply the estimates proposed there.

7.1. The Markov representation. Assume Γ : I → I is any piecewise affine map. The graph representation of the language Σ_∗(Γ) can be constructed as follows.

We define as the set of vertices the setV := Σ_∗(Γ) and as set of edgesE the set given by

(ω0ω1· · · ωn−1 → ω0ω1· · · ωn−1ωn)∈ E ⇐⇒ ω0ω1· · · ωn−1ωn∈ Σ∗(Γ).

(80)

Moreover, we introduce the following labeling ξ :E → I ∪ J on the edges:

ξ(ω₀ω₁· · · ωn−1→ ω0ω₁· · · ωn−1ω_n) = ω_n.

Notice that Σ_∗(Γ) coincides with the set of all the labeled words associated with the finite paths on the graph starting from the empty word . This representation of Σ_∗(Γ) will be called a Markov representation. This can be simplified by considering an equivalence relation on the vertices. With each finite word ω0ω1· · · ωn∈ Σ_∗(Γ) we associate its symbolic future

futΣ(ω0ω1· · · ωn) =

ω0ω1· · · ωk| ω0= ωn and ω0ω1· · · ωnω1· · · ωk ∈ Σ∗(Γ) , which is a subset of Σ_∗(Γ). More roughly, the symbolic future of a word ω₀ω₁· · · ωn

is the set of words whose concatenation with ω₀ω₁· · · ωn is in Σ_∗(Γ).

Consider also the geometric future which is

fut(ω0ω1· · · ωn) = Γⁿ(ω0∩ Γ⁻¹ω1∩ . . . ∩ Γ⁻ⁿωn).

The following result is in [5].

Proposition 4. Let ω0ω1· · · ωn and ν0ν1· · · νmbe two words in Σ_∗(Γ). Then (81)

fut(ω0ω1· · · ωn) = fut(ν0ν1· · · νm) ⇐⇒ futΣ(ω0ω1· · · ωn) = futΣ(ν0ν1· · · νm).

Now defineX to be the quotient of the set Σ∗(Γ) by the equivalence relation ω₀^· · · ω^n≡ ω0^· · · ωm^ ⇔ futΣ(ω^₀· · · ωn^) = fut_Σ(ω₀^· · · ωm^).

(82)

The elements of X will be called states and will be denoted by the symbol x. The symbolω0ω₁· · · ωn represents the state consisting of the equivalent class which con-tains the word ω0ω1· · · ωn. States representable by words of length 1 will be called principal states. The equivalence relation definingX ensures that any state x ∈ X has a well-defined geometric future fut(x). In fact, the geometric future fut(x) uniquely determines the state x. Edges and labels can be naturally redefined onX to obtain a new labeled graph denoted byG which is still a Markov representation of Σ_∗(Γ) and so, with the property that the labeled sequences associated with the finite paths on G, starting from empty word, corresponds to all the possible sequences in Σ∗(Γ).

Notice that there is an edge connecting a state x^to another state x^labeled with ω if and only if fut(x^) = Γ(fut(x^))∩ ω. This shows that the Markov representation G has the property that the terminal state of any edge is determined by its initial state and by its label. This means thatG is a deterministic automaton. This implies in particular that there is a one to one correspondence between paths x₁x₂· · · xk on the graphG starting from a principal state and words in Σ_∗(Γ). In order to count the number of words in Σ_∗(Γ) of length k, it will thus be equivalent to count the paths inG of the same length k.

Fig. 6. The map Γ of Example 1 and the graphG describing the language associated with its dynamics.

Example 1. We provide here a simple example which should clarify the concepts introduced so far. Consider the piecewise affine map Γ : [−1, 1] → [−1, 1] defined as follows:

Γ(x) :=

2ax + 1 if − 1 < x < 0, ax− 1 if 0 < x < 1,

where a = ¹⁺₂^√5. The map Γ(x) is shown in Figure 6. Let I0 :=]− 1, 0[, and let I1:=]0, 1[. For this particular choice of a we have that the set of states is finite:

X =

I0, I1, I0I0, I1I1 . The graphG is shown in Figure 6.

7.2. Properties of the Markov representation. Assume Γ : I → I is a piecewise affine map and that J ⊆ I is another invariant interval as in the setting of section. We now want to show that the just introduced Markov representation restricted to Σ_∗(Γ)∩ I^∗(we are using the notation established in section 5.1) satisfies properties (A), (B), and (C) introduced in the previous section. To this aim we define

XP :=

I1, I2, . . . , IN , Xi:=

ω0ω1· · · ωkIi ∈ X | ω0ω1· · · ωk∈ Σ∗(Γ)∩ I^∗

=

x∈ X | fut(x) ⊆ Ii

,

X :=

3N i=1

Xi =

x∈ X | fut(x) ⊆ I \ J , q : X → ]0, 1[ : x → q(x) := P

fut(x) ,

and the graphG which coincides with the graph G restricted to the set of states X . By taking q_i=P[Ii], we have that property (A) holds true. The next two lemmas will show that properties (B) and (C) also hold true with α1=|a|, α2= 2, D1=|a|, and D2= 1.

Lemma 6. Let x^∈ X , X^⊆ X , and let k ≥ 2. Then

#Fk

x1= x^, x2, . . . , xk−1 ∈ X , xk ∈ X^

≤ P

fut(x^) infx^∈X^P

fut(x^)|a|^k−1. Proof. Notice that the intervals of the form

fut(x^)∩ Γ⁻¹fut(x2)∩ · · · ∩ Γ^−(k−2)fut(xk−1)∩ Γ^−(k−1)fut(xk), x2, . . . , xk ∈ X , constitute a family of disjoint subsets of fut(x^). This shows that

P[fut(x^)]≥ 

x2,...,xk−1∈X xk∈X 

P

fut(x^)∩ Γ⁻¹fut(x₂)∩ · · ·

∩ Γ^−(k−2)fut(xk−1)∩ Γ^−(k−1)fut(xk) . Notice, moreover, that Γ^k−1 is affine on each of these intervals and that

Γ^k−1

fut(x^)∩ Γ⁻¹fut(x2)∩ · · · ∩ Γ^−(k−2)fut(xk−1)∩ Γ^−(k−1)fut(xk)

= fut(xk).

This implies that P

fut(x^)∩ Γ⁻¹fut(x₂)∩ · · · ∩ Γ^−(k−2)fut(x_k−1)∩ Γ^−(k−1)fut(x_k)

≥ infx^∈X^P[fut(x^)]

|a|^k−1

if x^x2· · · xk−1xk ∈ Fk[x1 = x^, x2, . . . , xk−1 ∈ X , xk ∈ X^], and it is 0 otherwise.

This yields the result.

Lemma 7. Let x^∈ X , and let i = 1, . . . , N. Then

#Fk[x1= x^, x2, . . . , xk−1∈ X \ XP, xk ∈ Xi]≤ 2^k−2.

Proof. As mentioned above, there is an edge connecting a state x^ to another state x^with label ω if and only if fut(x^) = Γ(fut(x^))∩ ω. Since the map Γ is affine on fut(x^), Γ(fut(x^)) is an interval, and so at most two followers of a state can be nonprincipal. The result follows by applying this argument.

It follows from Lemmas 6 and 7 that the graphG satisfies properties (A), (B), and (C), and hence Theorem 6 holds true in this case. Notice that this yields Theorem 2, since γkdefined in (30) coincides with γkdefined in (30). Indeed, in this case we have that

γk,h= #Fk[x₁=Ih, x2, . . . , xk∈ X ], so that γ_k = 

hγ_k,h coincides with the number of paths of length k in the graph G, starting from a principal state and always remaining in X . This, by the previous discussion, corresponds to the number of distinct subwords in Σ_∗(Γ)∩ I^∗of length k.

7.3. Estimation of the number of paths in the chaotic case. As mentioned

Nel documento The first consequence of the limited information flow constraint is that the signals that the controllers and the systems exchange have to be quantized (pagine 30-46)