Read anywhere, anytime
Description
Subjects
Informations
Published by | profil-zyak-2012 |
Reads | 23 |
Language | English |
Exrait
GROWTH RATE FOR THE EXPECTED VALUE OF A
GENERALIZED RANDOM FIBONACCI SEQUENCE
´ ˆELISE JANVRESSE, BENOIT RITTAUD, THIERRY DE LA RUE
Abstract
A random Fibonacci sequence is deﬁned by the relationg =|g ±g |, wheren n−1 n−2
the ± sign is chosen by tossing a balanced coin for each n. We generalize these
sequencestothecasewhenthecoinisunbalanced(denotingbyptheprobabilityofa
+), andtherecurrencerelationisofthe formg =|λg ±g |. Whenλ≥ 2 andn n−1 n−2
0<p≤ 1, we prove that the expected value of g grows exponentially fast. Whenn
λ =λ = 2cos(π/k) for some ﬁxed integerk≥ 3, we show that the expected valuek
of g grows exponentially fast for p> (2−λ )/4 and give an algebraic expressionn k
for the growth rate. The involved methods extend (and correct) those introduced
in [5].
Key words: binarytree; randomFibonacci sequence; random Fibonacci tree; linear
recurring sequence; Hecke group.
Mathematical Subject Classiﬁcation: 11A55, 15A52 (05c05, 15A35)
1. Introduction
Arandom Fibonacci sequenceisasequence(g ) deﬁnedbyitsﬁrsttwotermsgn n 1
andg (which in the sequel are assumed to be positive) and the recurrencerelation2
g = |g ±g |, where for each n the ± sign is chosen by tossing a balancedn+1 n n−1
coin.
A generalization of this notion consists in choosing the± sign by an unbalanced
coin(say: +withprobabilitypand−withprobabilityq := 1−p). Anotherpossible
generalization consists in ﬁxing two real numbers, λ and μ, and considering the
recurrence relation g =|λg ±μg |, where the ± sign is chosen by tossing an n−1 n−2
balanced (or unbalanced) coin for each n. By considering the modiﬁed sequence
n/2 λ√g˜ :=g /μ , which satisﬁes g˜ =| g˜ ±g˜ |, we can always reduce to then n n n−1 n−2μ
caseμ = 1. In the following, we refer to the random sequencesg =|λg ±g |n n−1 n−2
where the + sign is chosen with probability p and the − sign with probability
q := 1−p as (p,λ)-random Fibonacci sequences.
In [3], we investigated the question of the asymptotic growth rate of almost all
(p,1)-randomFibonaccisequences. Weobtainedanexpressionofthislimitwhichis
simplerthantheonegivenbyDivakarViswanathin[7]andwhichisnotrestrictedto
p= 1/2: It is given by the integral of the natural logarithm over a speciﬁc measure
(depending on p) deﬁned on Stern-Brocot intervals. The corresponding results for
(p,λ)-random Fibonacci sequences, which involve some techniques presented here
butalsocomplementaryconsiderations,istheobjectofanotherpublication(see[2]).
1´ ˆ2 ELISE JANVRESSE, BENOIT RITTAUD, THIERRY DE LA RUE
1/nHere,weareconcernedwiththeevaluationofthelimitvalueof(E(g )) ,wheren
(g ) is a (p,λ)-random Fibonacci sequence andE stands for the expectation.n n
This limit was studied in the particular case p = 1/2 and λ = 1 in [5], where
the growth rate of the expected value of a (1/2,1)-random Fibonacci sequence is
proved to be asymptotically equal to α−1≈ 1.20556943, where α is the only real
3 2zero of α = 2α +1. The proof involves the study of the binary tree T naturally
deﬁned by the set of all (1/2,1)-randomFibonacci sequences (if a nodea hasb as a
child, then the nodeb has two children, labelled bya+b and by|a−b|). The study
ofT is made by considering the biggest subtree ofT (denoted by R) which shows
no redundance, that is in which we never see two diﬀerent edges with the same
valuesa andb (in this order) as parent and child. This restricted treeR has many
combinatorial and number-theoretic aspects which are of interest. Let us mention
that, after the publication of [5], we realized that there was a problem in the last
step of the proof of its main result; this mistake is explained in Remark 1.
In the present paper, we correct and extend the result of [5] to some (p,λ)-
random Fibonacci sequences: For any p∈ [0,1], any λ≥ 2, and any λ of the form
2cos(π/k) (denoted by λ ), where k≥3 is an integer.k
Forλ =λ , the combinatorialpropertiesof the treeR extends in a surprinsinglyk
elegantway,leading to anextremelynaturalgeneralizationofthe resultspreviously
mentioned. In particular, the link made in [3] and [5] between the tree R and
continued fraction expansion remains true for λ = 2cos(π/k) and corresponds tok
so-called Rosen continued fractions, a notion introduced by David Rosen in [6].
We will not resort to continued fractions in the present work, but this aspect is
presented in [2].
An interesting fact to notice is that the values λ and λ > 2 are the only onesk
2for which the group of transformations of the hyperbolic half plane H generated
by the transformations z −→ −1/z and z −→z +λ, said to be a Hecke group, is
discrete (cf. [1]). We will not use that fact in the following, but it suggeststhat it is
highly probable that some link is to be made between random Fibonacci sequences
and hyperbolic geometry; in particular, possible future extensions of the combina-
torial point of view given by the restricted trees deﬁned below could have some
interpretation in hyperbolic geometry for values of λ for which the corresponding
Mo¨bius group is not discrete.
We are grateful to Kevin Hare, of University of Waterloo (Canada), for helpful
comments, and to Jean-Franc¸oisQuint, of CNRS and Universit´eParis-13 (France),
for fruitful discussions on hyperbolic geometry.
2. Results
Our main results are the following theorems.
Theorem 1. Let p ∈ [0,1], k ≥ 3 and m be the expected value of the n-th termn
of a (p,λ )-random Fibonacci sequence.k
• If p>p := (2−λ )/4, thenc k
k−1m pqn+1
−−−→ α (p) 1+ >1,k kn→∞m α (p)n k
where α (p) is the only positive root of the polynomialk
2k 2k−1 2k−2 k−1 k−1 2 2k−2P (X) :=X −λ X −(2p−1)X −λ pq X −p q .k k kGROWTH RATE OF RANDOM FIBONACCI SEQUENCES 3
• If p=p , then (m ) grows at most linearly.c n n
• If p<p , then (m ) is bounded.c n n
h i
1/n1/nNotethatbyJensen’sinequality,wehaveE[g ] ≥E g . Hencethecriticaln n
value for the growth rate of the expected value is smaller than the critical value
when one considers the almost-sure growth rate. It is proved in [2] that the latter
is equal to 1/k, which is strictly larger than p = (2−λ )/4 = (1−cos(π/k))/2.c k
Theorem 2. Let λ≥2, 0<p≤ 1, and m be the expected value of the n-th termn
of a (p,λ)-random Fibonacci sequence. Then
p
2m λ+ λ +4(2p−1)n+1
−−−→ .
n→∞m 2n
In view of the study of (p,λ)-random Fibonacci sequences for other values ofλ,
we also investigate an aspect of the regularity of the behaviour of the growth rate
of such a sequence in the neighbourhood of λ = 2.
Corollary 1. Let 0<p≤1. If we assume that, for any λ in the neighbourhood of
2, the expected value of a (p,λ)-random Fibonacci sequence increases exponentially
fast with growth rate equal to G(λ), then G cannot be analytic at λ = 2.
In the particular case p = 1/2, we can even prove the non-analyticity of the
growth rate on any left neighbourhood of 2.
Corollary 2. Let p = 1/2. Assume that, for any λ ≤ 2, the expected value of a
(1/2,λ)-random Fibonacci sequence increases exponentially fast, with growth rate
′ nequal to G(λ). If G is diﬀerentiable at λ = 2, then G (2) = 1. If G is of class C at
(i)λ = 2, then G (2) = 0 for any i ∈ [2,n]. As a corollary, G cannot be analytic at
λ = 2.
We ﬁrst prove Theorem 2 in Section 3, since the case λ ≥ 2 is much easier.
Section4isdevotedtogeneralfactsaboutthereducedtreeforλ =λ . Itintroducesk
notations and useful tools for the proof of Theorem 1. This theorem is proved in
Sections 5, 6 and 7, by extending the ideas introduced in [5] for the case k =
3 and p = 1/2. Proofs of corollaries 1 and 2 about the non-analyticity in the
neighbourhood of 2 can be found in Section 8. Section 9 contains a discussion
about open questions.
3. Case λ≥ 2
We introduce the treeT (a,b), which shows all diﬀerent possible (p,λ)-randomλ
Fibonacci sequences with ﬁrst positive terms g = a and g = b: The root of the1 2
treeT (a,b) is labelled bya, its unique child is labelled byb, and each node of theλ
tree labelled byβ and with parent labelled byα has exactly two children, the right
one labelled byλβ+α and the left one by|λβ−α|. Whenβ is the label of a node
in T (a,b) with parent labelled by α, it will be convenient to consider the vectorλ
(α,β) as the label of the corresponding edge. We also talk about the right and
left children of an edge labelled (α,β), which are respectively the edges labelled by
(β,λβ +α) and (β,|λβ−α|).
We also introduce the weight of an edge in the tree T (a,b), corresponding toλ
the probability that a (p,λ)-random Fibonacci sequence passes through this edge.´ ˆ4 ELISE JANVRESSE, BENOIT RITTAUD, THIERRY DE LA RUE
1 )
1
ψ2
1 )
q p
ψ3
0 2
.
2 2 .q pq pq p .
1 1 1 3
3 2 2 2 2 2 2 3q pq pq p q pq p q p q p
1 1 1 1 1 3 1 5
Figure 1. The beginning of the treeT (1,1).1
More formally, the initial edge in T (a,b) has weight 1. If an edge has weight w,λ
then its right and left children have respective weight pw and qw. (Recall that
q = 1−p.)
We organize the edges of the tree T (a,b) in rows: The initial edge is the onlyλ
edge in row 2; any child of an edge in row n is in row n+1. For any n ≥ 2, we
denote by ψ the set of edges in row n in T (a,b).n λ
The average of any subsetX of edges ofT (a,b) is deﬁned as the sumM(X) ofλ
all terms of the formβw, where β is the second coordinate of an edge in X and w
is the weight of this edge. Observe that the expected valuem of the n-th term ofn
a (p,λ)-random Fibonacci is given by M(ψ ).n
It will be of interest to consider the sequence (ℓ ) of numbers read along thes
leftmost branch of T (a,b): ℓ :=a, ℓ :=b andℓ :=|λℓ −ℓ | for s≥ 2.λ 1 2 s+1 s s−1
We now turn to the proof of Theorem 2.
Lemma 1. If b≥a and λ≥2, then for any edge in T (a,b) labelled by (α,β), weλ
have β≥α.
Proof. This is immediately proved by induction.
Corollary 3. If b≥a and λ≥ 2, then M(ψ ) =λM(ψ )+(2p−1)M(ψ ).n n−1 n−2
Proof. We deduce from Lemma 1 that absolute values are never used in the com-
putations of labels inT (a,b). Regrouping the contributions of the two children ofλ
an edge in rown−1, and summing over rown−1, we get the result.
The preceding corollary shows that for b≥ a and λ≥ 2, there exists constants
′C andC (depending ona andb) such that
n ′ ′nM(ψ ) =Cα +C α ,n+2GROWTH RATE OF RANDOM FIBONACCI SEQUENCES 5
p p
′2 2λ +4(2p−1))/2 and α := (λ− λ +4(2p−1))/2 are thewhere α := (λ +
2roots of the polynomial X −λX−(2p−1). Observe that, by Lemma 1, if b≥a
then all labels in the treeT (a,b) are larger thanb, henceM(ψ )≥b> 0. Sinceλ n+2
′α> 1 and|α|< 1, we deduce that C > 0, and Theorem 2 is proved when b≥a.
If b < a, we ﬁrst consider the case where the sequence (ℓ ) along the leftmosts
branch is unbounded. Then there exists a ﬁrst S ≥ 2 such that ℓ ≥ ℓ . WeS+1 S
can then consider T (a,b) as the disjoint union of the trees T (ℓ ,λℓ +ℓ ),λ λ s s s−1
2 ≤ s ≤ S, and the tree T (ℓ ,ℓ ). M(ψ ) can be written as a convexλ S S+1 n+2
combination of similar expressions in these trees. Since for each one of these trees,
the labels of the ﬁrst edge are well-ordered, Theorem 2 is valid for them. A simple
computation shows that the result extends to T (a,b).λ
It remainsto consider the casewhere (ℓ ) is bounded. We then considerT (a,b)s λ
as the disjoint union of the leftmost branch and inﬁnitely many trees, namely the
trees T (ℓ ,λℓ +ℓ ), 2 ≤ s, whose ﬁrst-edge labels are well-ordered. For eachλ s s s−1
′s, there exists constantsC andC (depending onℓ and ℓ ) such thats s−1 ss
n−1X
n s n−s+1 ′ ′n−s+1M(ψ ) =q ℓ + q p C α +C α .n+2 n+2 s s
s=0
′ nUsing the fact that C and C are bounded, we obtain that M(ψ ) ∼ Kα fors n+2s
some K > 0, which ends the proof of Theorem 2.
4. Reduced tree in the case λ =λ for some k≥ 3k
From now on, we ﬁx an integer k ≥ 3, and set λ :=λ . We keep the notationsk
concerning the treeT (a,b) introduced in the preceding section.λ
We introduce the two matrices
0 −1 0 1
(1) L := and R := .
1 λ 1 λ
Observe that the right child of an edge labelled (α,β) is labelled by (α,β)R, and
the left child is labelled by (u,|v|) where (u,v) = (α,β)L.
Deﬁnition 1. Any right child in a tree is said to be a 0-th left child. For any
integerm> 0, a child in a tree is said to be an m-th left child iﬀ it is the left child
of an (m−1)-th left child.
Proposition 1. Let (α,β) be the label of an edge in T (a,b). The (k−1)-th leftλk
child of the right child of this edge is also labelled by (α,β).
−1Proof. An elementary calculation shows thatL =PDP , where
iπ/k iπ/ke 0 1 e
D := , P := .−iπ/k −iπ/k0 e 1 e
As a consequence, we get that for any integerj,
!
(j+1)πjπ1 sin sinj k k(2) RL = .(j+1)π (j+2)πsin(π/k) sin sink k
jIn particular, for j ≤k−2,RL has nonnegative entries, and
1 0k−1RL = .
0 −1´ ˆ6 ELISE JANVRESSE, BENOIT RITTAUD, THIERRY DE LA RUE
( 1
π2 1
1
p
π3
2n
2pq pπ4
1 3
2 2 3p q p q p...
3 1 5
2 2 3 3 3 4p q p q p q p q p
2 4 4 2 8
3 2 3 2 4 3 2 4 4 4 5p q p q p q p q p q p q p q p
5 1 7 3 5 7 3 13
Figure 2. The beginning of the treeR (1,1), which is a subtree of T (1,1).3 λ3
Therefore, for j ≤ k−2, the j-th left child of the right child of the edge labelled
jby (α,β) is labelled by (α,β)RL and the (k−1)-th left child of the right child is
labelled by (α,|−β|).
We nowdeﬁne thetreeR (a,b)asthesubtreeofT (a,b)obtainedbyremovingk λk
the left child of the initial edge and all the edges which are (k−1)-th left child.
Proposition2 (LinearityinR (a,b)). Whenever it exists, the left child of an edgek
in R (a,b) labelled by (α,β) is labelled by (α,β)L.k
Proof. By deﬁnition, R (a,b) contains only j-th left children, for 0 ≤ j ≤ k−2.k
jThe proposition is a direct consequence of the fact that for such j’s, RL has
nonnegative entries.
Considering R (a,b) as a subtree of T (a,b), any edge in R (a,b) inherits itsk λ kk
weight from T (a,b). As for T (a,b), we organize the edges of R (a,b) in rows,λ λ kk
and denote by π ⊂ψ the set of edges in rown in R (a,b) (see Figure 2).n n k
In Section 5, we will ﬁrst considerM(π ), which is easier to study thanM(ψ ).n n
Then, the next step (Section 6) will be to estimate M(ψ ) by partitioning then
tree T (a,b) in inﬁnitely many copies of trees R (ℓ ,ℓ ), where (ℓ ) is theλ k s+1 s+2 sk
sequence of numbers read along the leftmost branch of T (a,b): ℓ := a, ℓ := bλ 1 2k
andℓ :=|λ ℓ −ℓ | for s≥2.s+1 k s s−1
Remark 1. Let us explain why there is a mistake in the argument given in [5]
(which deals with the particular case k = 3 and p = 1/2). The average growth
rate is proved to be equal to some explicit value for two linearly independent pairs
of initial values for the random Fibonacci sequence which are: (g ,g ) = (1,ϕ)1 2√
−1and (1,ϕ ), where ϕ = (1+ 5)/2 is the golden ratio. It is then asserted that,
−1since the vectors (1,ϕ) and (1,ϕ ) are linearly independent, any pair (a,b) can beGROWTH RATE OF RANDOM FIBONACCI SEQUENCES 7
−1written as a linear combination of (1,ϕ) and (1,ϕ ) to get the tree T (a,b) as aλ3
−1(1,ϕ) and T (1,ϕ ); The conclusion followslinear combination of the trees Tλ λ3 3
that, since both of these latter trees show the same growth rate, the growth rate of a
random Fibonacci sequence does not depend on the initial values a and b (with the
obvious restriction that ab = 0). In fact, this way of proving the theorem is wrong,
−2 −1 −1as it can be easily seen by writing the equality (1,1) = ϕ (1,ϕ) +ϕ (1,ϕ ).
The tree deduced from this linear combination is a tree with root 1 and child of the
root equal to 1, but it does not correspond to T (1,1) (since, for example, the leftλ3
−3grandchild of the root is equal to 2ϕ instead of 0).
5. Average M(π ) of row n of R (a,b)n k
iFor any X ⊂ T (a,b), and 0 ≤ i ≤ k− 2, we deﬁne X as the subset of Xλk
0made of all its elements which are i-th left children (X thus corresponds to right
k−2 ichildren). With the convention π := π and π = ∅ for i ≤ k−3, we get that22 2
each node of the treeR (a,b) which has only one child is a (k−2)-th left child.k
5.1. A recursive formula for M(π ). The next lemma gives, for any 0 ≤ i ≤n
j jik−2,M(π ) as a function of (M(π )) and (M(π )) .0≤j≤k−2 0≤j≤k−2n n−1 n−2
Lemma 2. For any integer n≥4 we have
0 k−2M(π ) = λpM(π )+pM(π )−pqM(π ),n−1 n−2n n−2
1 0M(π ) = λqM(π )−pqM(π ),n−2n n−1
i i−1 2 i−2M(π ) = λqM(π )−q M(π ), 2≤i≤k−2.n n−1 n−2
Proof. Consider an edge e in π whose parent has weight w and is labelled byn
(α,β).
0 0Case 1: Assume e ∈ π (e is a right child). The contribution of e to M(π ) isn n
0(λβ+α)wp =λp.βw+p.αw. Observethatwhenerunsoverπ , itsparentrunsovern
π and brings a contribution βw to M(π ). Moreover, when e’s parent runsn−1 n−1
0overπ ,e’s grandparentruns overπ and has contributionαw/p toM(π ).n−2 n−2n−1
k−2 k−3i iWhene’s parent runs over∪ π ,e’s grandparent runs over∪ π and hasi=1 n−1 i=0 n−2
k−3 k−2icontributionαw/q to M(∪ π ) =M(π )−M(π ). This proves the ﬁrstn−2i=0 n−2 n−2
equality of Lemma 2.
1 1Case 2: Assume e ∈ π (e is a left child). Its contribution to M(π ) is (λβ−n n
0α)wq =λq.βw−pq.αw/p. Observe thate’s parent is inπ (thus is a right edge),n−1
0and brings a contribution βw to M(π ). Moreover e’s grandparent is in π ,n−2n−1
1has weight w/p, and its contribution to M(π ) is αw/p. When e runs over π ,n−2 n
0its parent runs overπ and its grandparent runs overπ .n−2n−1
iCase 3: Assume e ∈ π for 2 ≤ i ≤ k−2 (e is a left child). The contributionn
i 2of e to M(π ) is (λβ −α)wq = λq.βw−q .αw/q. Observe that e’s parent is inn
i−1 i−1π (thus is a left edge), and brings a contribution βw to M(π ). Moreovern−1 n−1
i−2 ie’s grandparent is in π , has weight w/q, and e is its only left grandchild in π .n−2 n
i−2 iThe contribution of e’s grandparent to M(π ) is αw/q. When e runs over π ,n−2 n
i−1 i−2its parent runs overπ and its grandparent runs overπ . This ends the proofn−1 n−2
of the lemma.
In the proof of the preceding lemma, we only used the structure of the tree
R (a,b) and the linear relation linking the labels of the edges in this tree, but notk
6´ ˆ8 ELISE JANVRESSE, BENOIT RITTAUD, THIERRY DE LA RUE
the speciﬁc value λ = λ . In the next lemmas, this speciﬁc value plays a centralk
role.
Lemma 3. We have for any n≥k+2
k−3 k−2 k−2qM(π )−λM(π ) =pq M(π )n−kn−2 n−1
k−2
Proof. Consider an edge e in π with weightw and label (α,β). Its parent is inn−1
k−3 k−3π and has weight w/q: Thus, it contributes for αw/q to M(π ). Moreover,n−2 n−2
k−2e’s (k− 1)-th parent is in π , has weight w/pq and its label (u,v) is suchn−k
k−2that (u,v)RL = (α,β). Thus, (u,v) = (β,α−λβ) and this edge contributes
k−2for (α−λβ)w/pq to M(π ). The conclusion follows from the fact that whenn−k
k−2 k−3
e runs over π , its parent runs over π and its (k− 1)-th parent runs overn−1 n−2
π . n−k
Lemma 4. We have for any n≥k+2
k−2 k−2 k−2M(π ) =pq M(π )−qM(π )n−kn n−k
j
Proof. Consider an edge e in π with weight w and label (α,β). If e ∈ π ,n−k n−k
k−2j ≤ k − 3, this edge is the ancestor of two edges in π , which have labelsn
k−2 k−2 2 k−2 k−2(α,β)RRL and (α,β)LRL , and weights wp q and wqpq . Their con-
k−2 k−2 k−2tribution to M(π ) is thus βwpq . If e∈π , it is the ancestor of only onen n−k
k−2 k−2 2 k−2edge inπ , having labels (α,β)RRL and weightwp q . Its contribution ton
k−2 2 k−2M(π ) is thus βwp q . The conclusion follows from the fact that any edge inn
k−2π has a unique ancestor in π . n−kn
Lemma 5. We have for any n≥k+2
k−2k−1M(π ) =λM(π )+(2p−1)M(π )+pq M(π )+(q−p)qM(π ).n n−1 n−2 n−k n−2
Proof. Using Lemma 2 and Lemma 3, we get
k−2X
iM(π ) = M(π )n n
i=0
k−2= λpM(π )+pM(π )−pqM(π )n−1 n−2 n−2
0+ λqM(π )−pqM(π )n−2n−1
k−3 k−4X X
i 2 i+ λqM(π )− q M(π )n−1 n−2
i=1 i=0
k−2 2= λM(π )−λqM(π )+(p−pq−q )M(π )n−1 n−2n−1
2 k−2 2 k−3+(q −pq)M(π )+q M(π )n−2 n−2
k−2 k−1= λM(π )+(2p−1)M(π )+(q−p)qM(π )+pq M(π ).n−1 n−2 n−kn−2
In the particular case p = q = 1/2, Lemma 5 gives M(π ) as a function ofn
M(π ) andM(π ). Thenext propositiongivesa simple wayto expressM(π )n−1 n−k n
in terms of (M(π )) in the general case.m m<nGROWTH RATE OF RANDOM FIBONACCI SEQUENCES 9
Proposition 3. We have for any n≥ 2k+2
k−1(3) M(π ) =λM(π )+(2p−1)M(π )+pq λM(π )n n−1 n−2 n−k−1
2 2k−2
+p q M(π )n−2k
Proof. Applying twice Lemma 5, (once forM(π ), then forM(π )), the desiredn n−k
result follows from Lemma 4.
5.2. Study of M(π ).n
Pn−1n jLemma 6. Let n ≥ 2 and let Q(X) = X − c X , where c > 0 for allj jj=0
0 ≤ j ≤ n− 1. Then Q has a unique positive real root α. Moreover, α is of
multiplicity 1 and all the other roots of Q have modulus strictly less than α.
Proof. Since Q(0) = −c < 0, Q has at least one positive real root α. Assume0
iθβe =α is another root of Q such that β ≥α. We have
n−1 n−1
Access to the YouScribe library is required to read this work in full.
Discover the services we offer to suit all your requirements!