text: 31 would have a wider range of thresholds to choose from so as to do a more ﬂexible trade-off between the probability (cid:80) of false alarm and the probability of miss. Though an individual agent dependent bounding would be ideal, but (cid:2) (cid:3) it makes the analysis seemingly intractable. For example, while bounding N φ (k − 1)(θ∗)(cid:62)H(cid:62)j Σ−j 1Hjθ∗ , j=1 n,j 2 − − − where φn,j(k 1) √= Wk 1 n,j, we use the same bound for each of φn,j(k 1) which is in turn given by − ≥ − − φ (k 1) 1 Nrk 1. In such a setting, tracking the row corresponding to a particular agent in the weight n,j N matrix is seemingly intractable. Having said that, if individual agent dependent thresholds could have been used, the extent to which an agent can distinguish between different hypotheses would be different owing to different range of thresholds available to an agent to choose from. The use of time dependent thresholds however does not seem to affect the zone of indifference. It is to be noted ∗ that the zone of the indifference is characterized in terms of the range of θ ’s under the alternate hypothesis for which exponential decay of both the probability of errors can be ensured. To be speciﬁc, in the analysis of the (cid:107) (cid:107) probability of the miss the crucial part of the analysis is the bound for the term t P which is given by t (cid:107) (cid:107) ≤ (t + 1)2c1α0 α2 α2 ∀ ≥ t Pt c3 1t2c1α0−1 + t0 + 2c1α00− 1, t t1. If the thresholds are adjusted, so as to take into account the time-decaying terms c3 (tt12+c11α)20c−11α0 and αt20 , both the → ∞ terms decay to zero as t thereby ensuring that the large deviations exponent upper bound stays the same. However, it is to be noted that at any ﬁnite time, time dependent thresholds would give tighter probability of error bounds, thus improving transients of the approach. The assumption regarding the inter-agent communication network which is instrumental in obtaining the results of this paper is the connectivity of the graph i.e., there exists a path between every two nodes. As long as the graph is connected, the results continue to hold. For example, for a network with N agents, there needs to be at least − − N 1 links for the graph to be connected, which is very sparsely connected as out of the possible N(N 1)/2 − possible links only N 1 links are present. Hence, the algorithms apply to very sparse (but connected) networks. However, it is important to note that the large deviations upper bounds might get worse with increasing sparsity of the inter-agent communication graph. The sparsity of the inter-agent communication graph is in turn reﬂected (cid:107) − (cid:107) by the quantity11 r = W J , where W and J represent the weight matrices associated with the inter-agent communication graph under consideration and a completely connected graph respectively. When r = 0 it basically points to the case that W = J, i.e., the network under consideration is completely connected. The other extreme case r = 1 is the case when W = I, i.e., when there are no links in the network. To sum it up, small values of − 1 r reﬂect the sparseness of the network under consideration. Furthermore, note that with increasing k, i.e., the time lag or equivalently the number of rounds of consensus ∗ between incorporating latest estimates (see (32)), the range of parameter θ for which exponential decay of error probabilities can be ensured increases, the large deviations upper bounds for the probabilities of miss and false alarm also increase. However, k cannot be made arbitrarily large just based on improvement of the large deviations upper bounds, as large deviations analysis is essentially an asymptotic characterization and at the same time with 11It is to be noted that as long as the graph is connected, r < 1. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: would

text: have

text: a

text: wider

text: range

text: of

text: thresholds

text: to

text: choose

text: from

text: so

text: as

text: to

text: do

text: a

text: more

text: ﬂexible

text: trade-off

text: between

text: the

text: probability

text: of

text: false

text: alarm

text: and

text: the

text: probability

text: of

text: miss.

text: Though

text: an

text: individual

text: agent

text: dependent

text: bounding

text: would

text: be

text: ideal,

text: but

text: it

text: makes

text: the

text: analysis

text: seemingly

text: intractable.

text: For

text: example,

text: while

text: bounding

text: N

text: φ

text: (k

text: Σ−j

text: n,j

text: where

text: φn,j(k

text: Wk

text: n,j,

text: we

text: use

text: the

text: same

text: bound

text: for

text: each

text: of

text: φn,j(k

text: which

text: is

text: in

text: turn

text: given

text: by

text: φ

text: (k

text: Nrk

text: In

text: such

text: a

text: setting,

text: tracking

text: the

text: row

text: corresponding

text: to

text: a

text: particular

text: agent

text: in

text: the

text: weight

text: n,j

text: N

text: matrix

text: is

text: seemingly

text: intractable.

text: Having

text: said

text: that,

text: if

text: individual

text: agent

text: dependent

text: thresholds

text: could

text: have

text: been

text: used,

text: the

text: extent

text: to

text: which

text: an

text: agent

text: can

text: distinguish

text: between

text: different

text: hypotheses

text: would

text: be

text: different

text: owing

text: to

text: different

text: range

text: of

text: thresholds

text: available

text: to

text: an

text: agent

text: to

text: choose

text: from.

text: The

text: use

text: of

text: time

text: dependent

text: thresholds

text: however

text: does

text: not

text: seem

text: to

text: affect

text: the

text: zone

text: of

text: indifference.

text: It

text: is

text: to

text: be

text: noted

text: that

text: the

text: zone

text: of

text: the

text: indifference

text: is

text: characterized

text: in

text: terms

text: of

text: the

text: range

text: of

text: θ

text: ’s

text: under

text: the

text: alternate

text: hypothesis

text: for

text: which

text: exponential

text: decay

text: of

text: both

text: the

text: probability

text: of

text: errors

text: can

text: be

text: ensured.

text: To

text: be

text: speciﬁc,

text: in

text: the

text: analysis

text: of

text: the

text: probability

text: of

text: the

text: miss

text: the

text: crucial

text: part

text: of

text: the

text: analysis

text: is

text: the

text: bound

text: for

text: the

text: term

text: t

text: P

text: which

text: is

text: given

text: by

text: t

text: (t

text: α2

text: α2

text: t

text: Pt

text: t

text: If

text: the

text: thresholds

text: are

text: adjusted,

text: so

text: as

text: to

text: take

text: into

text: account

text: the

text: time-decaying

text: terms

text: and

text: both

text: the

text: terms

text: decay

text: to

text: zero

text: as

text: t

text: thereby

text: ensuring

text: that

text: the

text: large

text: deviations

text: exponent

text: upper

text: bound

text: stays

text: the

text: same.

text: However,

text: it

text: is

text: to

text: be

text: noted

text: that

text: at

text: any

text: ﬁnite

text: time,

text: time

text: dependent

text: thresholds

text: would

text: give

text: tighter

text: probability

text: of

text: error

text: bounds,

text: thus

text: improving

text: transients

text: of

text: the

text: approach.

text: The

text: assumption

text: regarding

text: the

text: inter-agent

text: communication

text: network

text: which

text: is

text: instrumental

text: in

text: obtaining

text: the

text: results

text: of

text: this

text: paper

text: is

text: the

text: connectivity

text: of

text: the

text: graph

text: i.e.,

text: there

text: exists

text: a

text: path

text: between

text: every

text: two

text: nodes.

text: As

text: long

text: as

text: the

text: graph

text: is

text: connected,

text: the

text: results

text: continue

text: to

text: hold.

text: For

text: example,

text: for

text: a

text: network

text: with

text: N

text: agents,

text: there

text: needs

text: to

text: be

text: at

text: least

text: N

text: links

text: for

text: the

text: graph

text: to

text: be

text: connected,

text: which

text: is

text: very

text: sparsely

text: connected

text: as

text: out

text: of

text: the

text: possible

text: N(N

text: possible

text: links

text: only

text: N

text: links

text: are

text: present.

text: Hence,

text: the

text: algorithms

text: apply

text: to

text: very

text: sparse

text: (but

text: connected)

text: networks.

text: However,

text: it

text: is

text: important

text: to

text: note

text: that

text: the

text: large

text: deviations

text: upper

text: bounds

text: might

text: get

text: worse

text: with

text: increasing

text: sparsity

text: of

text: the

text: inter-agent

text: communication

text: graph.

text: The

text: sparsity

text: of

text: the

text: inter-agent

text: communication

text: graph

text: is

text: in

text: turn

text: reﬂected

text: by

text: the

text: r

text: W

text: J

text: where

text: W

text: and

text: J

text: represent

text: the

text: weight

text: matrices

text: associated

text: with

text: the

text: inter-agent

text: communication

text: graph

text: under

text: consideration

text: and

text: a

text: completely

text: connected

text: graph

text: respectively.

text: When

text: r

text: it

text: basically

text: points

text: to

text: the

text: case

text: that

text: W

text: J,

text: i.e.,

text: the

text: network

text: under

text: consideration

text: is

text: completely

text: connected.

text: The

text: other

text: extreme

text: case

text: r

text: is

text: the

text: case

text: when

text: W

text: I,

text: i.e.,

text: when

text: there

text: are

text: no

text: links

text: in

text: the

text: network.

text: To

text: sum

text: it

text: up,

text: small

text: values

text: of

text: r

text: reﬂect

text: the

text: sparseness

text: of

text: the

text: network

text: under

text: consideration.

text: Furthermore,

text: note

text: that

text: with

text: increasing

text: k,

text: i.e.,

text: the

text: time

text: lag

text: or

text: equivalently

text: the

text: number

text: of

text: rounds

text: of

text: consensus

text: between

text: incorporating

text: latest

text: estimates

text: (see

text: the

text: range

text: of

text: parameter

text: θ

text: for

text: which

text: exponential

text: decay

text: of

text: error

text: probabilities

text: can

text: be

text: ensured

text: increases,

text: the

text: large

text: deviations

text: upper

text: bounds

text: for

text: the

text: probabilities

text: of

text: miss

text: and

text: false

text: alarm

text: also

text: increase.

text: However,

text: k

text: cannot

text: be

text: made

text: arbitrarily

text: large

text: just

text: based

text: on

text: improvement

text: of

text: the

text: large

text: deviations

text: upper

text: bounds,

text: as

text: large

text: deviations

text: analysis

text: is

text: essentially

text: an

text: asymptotic

text: characterization

text: and

text: at

text: the

text: same

text: time

text: with

text: is

text: to

text: be

text: noted

text: that

text: as

text: long

text: as

text: the

text: graph

text: is

text: connected,

text: r

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 37 We now return to the proof of Theorem 4.1. ∈ Proof of Theorem 4.1. We follow closely the corresponding development in Lemma 5.9 of [49]. Deﬁne τ¯ [0, 1/2) such that, (cid:16) (cid:17) P (cid:107) (cid:107) ∗ lim (t + 1)τ¯ x(t) = 0 = 1, (94) θ →∞ t − ⊗ ∗ where x(t) = θ(t) 1 θ . Note that such a τ¯ exists by Lemma 6.2 (in particular, by taking τ¯ = 0). We now N analyze and ﬁnally show that there exists a τ such that τ¯ < τ < 1/2 for which the claim holds. Now, choose a ∈ τˆ (τ¯, 1/2) and let µ = (τˆ + τ¯)/2. By standard algebraic manipulations, it can be readily seen that the recursion { } for x(t) satisﬁes (cid:107) (cid:107) (cid:107) (cid:107) − (cid:62) ⊗ − (cid:62) − − ∗ x(t + 1) 2 = x(t) 2 2β x (t) (L I ) x(t) 2α x (t)G (θ(t)) Σ 1 (h (θ(t)) h (θ )) t M t (cid:62) ⊗ (cid:62) ⊗ − − ∗ + β2x (t) (L I )2 x(t) + 2α β x (t) (L I ) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) t M t t M − ∗ (cid:62) − (cid:62) − − ∗ + α2 (y(t) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (y(t) h (θ )) t − ∗ (cid:62) − (cid:62) − − ∗ + α2 (h (θ(t)) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) t (cid:62) − − ∗ + 2α x (t)G (θ(t)) Σ 1 (y(t) h(θ )) . (95) t − − ∗ (cid:107)∇ (cid:107) Let J(t) = G (θ(t)) Σ 1 (y(t) h (θ )). From Assumption A3, we have that h (θ (t)) is uniformly bounded n n (cid:107) (cid:107) ≤ from above by k for all n. Hence, we have that G (θ(t)) max ··· k . Now, we consider the term n n=1, ,N n (cid:107) (cid:107) α2 J(t) 2. Since, the noise process under consideration is a temporally independent Gaussian sequence and 2µ < 1, t we have, (cid:88) (cid:107) (cid:107) ∞ (t + 1)2µα2 J(t) 2 < a.s. (96) t ≥ t 0 (cid:2) (cid:3) (cid:62) − − ∗ E |F Let W(t) = α x (t)G (θ(t)) Σ 1 (y(t) h(θ )). It follows that ∗ [W(t) ] = 0. t θ t We also have that E ∗ W2(t)|F ≤ α2 (cid:107)x(t)(cid:107)2 (cid:107)J(t)(cid:107)2. Noting, that the noise under consideration is temporally θ t t independent with ﬁnite second moment, we have, (cid:2) (cid:3) (cid:0) (cid:1) E |F − − ∗ W2(t) = o (t + 1) 2 2τ¯ (97) θ t and hence, (cid:2) (cid:3) (cid:0) (cid:1) E |F − ∗ (t + 1)4µW2(t) = o (t + 1) 2+2τˆ . (98) θ t

label: paragraph

text: We

text: now

text: return

text: to

text: the

text: proof

text: of

text: Theorem

text: Proof

text: of

text: Theorem

text: We

text: follow

text: closely

text: the

text: corresponding

text: development

text: in

text: Lemma

text: of

text: Deﬁne

text: τ¯

text: such

text: that,

label: equation

text: P

text: lim

text: (t

text: 1)τ¯

text: x(t)

text: θ

text: t

text: where

text: x(t)

text: θ(t)

text: θ

text: Note

text: that

text: such

text: a

text: τ¯

text: exists

text: by

text: Lemma

text: (in

text: particular,

text: by

text: taking

text: τ¯

text: We

text: now

text: N

text: analyze

text: and

text: ﬁnally

text: show

text: that

text: there

text: exists

text: a

text: τ

text: such

text: that

text: τ¯

text: τ

text: for

text: which

text: the

text: claim

text: holds.

text: Now,

text: choose

text: a

text: τˆ

text: (τ¯,

text: and

text: let

text: µ

text: (τˆ

text: By

text: standard

text: algebraic

text: manipulations,

text: it

text: can

text: be

text: readily

text: seen

text: that

text: the

text: recursion

text: for

text: x(t)

text: satisﬁes

text: x(t

text: x(t)

text: 2β

text: x

text: (t)

text: (L

text: I

text: x(t)

text: 2α

text: x

text: (t)G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: M

text: t

text: (t)

text: (L

text: I

text: x(t)

text: 2α

text: β

text: x

text: (t)

text: (L

text: I

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: M

text: t

text: t

text: M

text: α2

text: (y(t)

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: t

text: α2

text: (h

text: (θ(t))

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: 2α

text: x

text: (t)G

text: (θ(t))

text: Σ

text: (y(t)

text: h(θ

text: t

text: Let

text: J(t)

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: From

text: Assumption

text: we

text: have

text: that

text: h

text: (θ

text: (t))

text: is

text: uniformly

text: bounded

text: n

text: n

text: from

text: above

text: by

text: k

text: for

text: all

text: n.

text: Hence,

text: we

text: have

text: that

text: G

text: (θ(t))

text: max

text: k

text: Now,

text: we

text: consider

text: the

text: term

text: n

text: ,N

text: n

text: α2

text: J(t)

text: Since,

text: the

text: noise

text: process

text: under

text: consideration

text: is

text: a

text: temporally

text: independent

text: Gaussian

text: sequence

text: and

text: 2µ

text: t

text: we

text: have,

text: (t

text: J(t)

text: a.s.

text: t

text: t

text: E

text: |F

text: Let

text: W(t)

text: α

text: x

text: (t)G

text: (θ(t))

text: Σ

text: (y(t)

text: h(θ

text: It

text: follows

text: that

text: [W(t)

text: t

text: θ

text: t

text: We

text: also

text: have

text: that

text: E

text: α2

text: Noting,

text: that

text: the

text: noise

text: under

text: consideration

text: is

text: temporally

text: θ

text: t

text: t

text: independent

text: with

text: ﬁnite

text: second

text: moment,

text: we

text: have,

text: E

text: |F

text: o

text: (t

text: 2τ¯

text: θ

text: t

text: and

text: hence,

text: E

text: |F

text: (t

text: o

text: (t

text: θ

text: t


text: 43 1 P ≤ − { ∗ } lim sup log ( (z (t) > η)) LE (min λ , 1 ) . (122) →∞ t 0 n t Finally, the above arguments and the threshold choices obtained in (113) and (120) establish that as long as the ∗ true θ satisﬁes the following condition (cid:16) (cid:17) (cid:80) √ h(cid:62) (θN∗ ) Σ−1h (θN∗ ) > N1 + Nr Nn=1 Mn , (123) 2N 2 any η satisfying (cid:16) (cid:17) (cid:80) √ N1 + Nr Nn=1 Mn < η < h(cid:62) (θN∗ ) Σ−1h (θN∗ ). (124) 2 2N P P → → ∞ would guarantee ∗(t), (t) 0 as t . Hence, the assertion is proved. M,θ FA CIGLRT − L 7. PROOF OF MAIN RESULTS : A. Proof of Theorem 4.4 ∀ Proof: The proof follows from the proof of Theorem 12 in [18]. To be speciﬁc, with γ = 0, L(i) = L, i 0 GLU (i denotes time in [18]) and K = I in [18], the algorithm in [18] exactly reduces to the parameter estimate CIGLRT − L update of the algorithm as deﬁned in (28). (cid:13) (cid:13) B. Proof of Theorem 4.5 (cid:13) (cid:13) − ⊗ − − (cid:62) Proof: The following result which characterizes I β (L I ) α G Σ 1G , will be crucial for NM t M t H H the subsequent analysis. We state the result here, while the proof is relegated to Appendix . CIGLRT − L Lemma 7.1. Let the Assumptions B1-B3 hold. Consider the parameter estimate update of the algorithm in (28). Then, we have, (cid:13) (cid:13) (cid:13) (cid:13) − ⊗ − − (cid:62) ≤ − ∀ ≥ I β (L I ) α G Σ 1G 1 c α , t t , (125) NM t M t H H 1 t 1 where (cid:0) (cid:1) (cid:0) (cid:1) (cid:62) ⊗ − (cid:62) ⊗ − (cid:62) c1 = (cid:107)m(cid:107)in x L IM + GHΣ 1GH x = λmin L IM + GHΣ 1GH , (126) x =1 { } t = max t , t , (127) 1 2 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: P

text: lim

text: sup

text: log

text: (z

text: (t)

text: η))

text: LE

text: (min

text: λ

text: t

text: n

text: t

text: Finally,

text: the

text: above

text: arguments

text: and

text: the

text: threshold

text: choices

text: obtained

text: in

text: and

text: establish

text: that

text: as

text: long

text: as

text: the

text: true

text: θ

text: satisﬁes

text: the

text: following

text: condition

text: (θN∗

text: Σ−1h

text: (θN∗

text: Nr

text: Mn

text: any

text: η

text: satisfying

text: Nr

text: Mn

text: η

text: (θN∗

text: Σ−1h

text: (θN∗

text: P

text: P

text: would

text: guarantee

text: ∗(t),

text: (t)

text: as

text: t

text: Hence,

text: the

text: assertion

text: is

text: proved.

text: M,θ

text: FA

text: CIGLRT

text: L

text: PROOF

text: OF

text: MAIN

text: RESULTS

text: A.

text: Proof

text: of

text: Theorem

text: Proof:

text: The

text: proof

text: follows

text: from

text: the

text: proof

text: of

text: Theorem

text: in

text: To

text: be

text: speciﬁc,

text: with

text: γ

text: L(i)

text: L,

text: i

text: GLU

text: (i

text: denotes

text: time

text: in

text: and

text: K

text: I

text: in

text: the

text: algorithm

text: in

text: exactly

text: reduces

text: to

text: the

text: parameter

text: estimate

text: CIGLRT

text: L

text: update

text: of

text: the

text: algorithm

text: as

text: deﬁned

text: in

text: B.

text: Proof

text: of

text: Theorem

text: Proof:

text: The

text: following

text: result

text: which

text: characterizes

text: I

text: β

text: (L

text: I

text: α

text: G

text: Σ

text: will

text: be

text: crucial

text: for

text: NM

text: t

text: M

text: t

text: H

text: H

text: the

text: subsequent

text: analysis.

text: We

text: state

text: the

text: result

text: here,

text: while

text: the

text: proof

text: is

text: relegated

text: to

text: Appendix

text: CIGLRT

text: L

text: Lemma

text: Let

text: the

text: Assumptions

text: hold.

text: Consider

text: the

text: parameter

text: estimate

text: update

text: of

text: the

text: algorithm

text: in

text: Then,

text: we

text: have,

text: I

text: β

text: (L

text: I

text: α

text: G

text: Σ

text: c

text: α

text: t

text: t

text: NM

text: t

text: M

text: t

text: H

text: H

text: t

text: where

text: x

text: L

text: IM

text: GHΣ

text: x

text: λmin

text: L

text: IM

text: GHΣ

text: x

text: t

text: max

text: t

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 44 ∀ ≥ and t , t are positive constants (integers) chosen such that t t , 2 3 2 (cid:0) (cid:1) − (cid:62) ≤ βtλN (L) + αtλmax GHΣ 1GH 1, (128) ∀ ≥ and t t , 3 (cid:0) (cid:1) ⊗ − (cid:62) αtλmin L IM + GHΣ 1GH < 1 (129) respectively. ∈ Under the null hypothesis, we have, for all λ (0, 1), (cid:18) (cid:19) (cid:62) − (cid:62) − − − − − G θ(k(t 1)) z (kt) = e Wk 1G (k(t 1))Σ 1 s(k(t 1)) H . (130) n n θ 2 From (130), we have, (cid:20) (cid:21) P0 (zn(kt) > η) ≤ e−(Nk1(+t−√1N)+r1k)−η1λ E0 e N1(k+(t√−N1)r(cid:88)+k1−)1 λ(cid:88)zn(kt) (cid:32)   − (cid:62) − (=a) e−(Nk1(+t−√1N)+r1k)−η1λ E0 exp 1 + √λNrk−1 k(t 1) N φ(cid:33)n,(cid:33)j((cid:35)k − 1) γj (i)Σ2j 1γj(i) N i=0 j=1 − − (cid:62) − − − −(γj(i) Hjθj(t 1)) Σj 1 (γj(i) Hjθj(t 1))  2 (cid:88) (cid:88)    − (cid:62) − (≤b) e−(Nk1(+t−√1N)+r1k)−η1λ E0 exp  1(cid:88)+ √λ(cid:88)Nrk−1 N φn,j(k −1)k(t 1) γj (i)Σ2j 1γj(i)   N j=1  i=0 − (cid:62) − (≤c) e−(Nk1(+t−√1N)+r1k)−η1λ E(cid:89)0 e(cid:89)xp λ (cid:34)N k(t(cid:32)1) γj (i)Σ2j 1γj(i)(cid:33)(cid:35) j=1 i=0 − (cid:62) − (=d) e−(Nk1(cid:32)(+t−√1N)+r1k)−η1λ N k(t 1) E0 exp λγj (i)Σ2(cid:80)j 1γj(i) (cid:33) j=1 i=0 − − (=e) exp −λη(k(t√ 1) +−1) − (k(t 1) + 1) Nn=1 Mn log(1 − λ) , (131) 1 + Nrk 1 2 N − − (cid:107) − (cid:107) where φ (k 1) denotes the (n, j)-th entry of Wk 1 and r denotes W J . It is to be noted that (a) follows n,j due to the fact that under the null hypothesis the observations made at the agents are of the form y (t) = γ (t), (b) n n follows due to the fact that the inverse covariances are positive deﬁnite and hence the quadratic forms are positive, ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: and

text: t

text: t

text: are

text: positive

text: constants

text: (integers)

text: chosen

text: such

text: that

text: t

text: t

text: βtλN

text: (L)

text: αtλmax

text: GHΣ

text: and

text: t

text: t

text: αtλmin

text: L

text: IM

text: GHΣ

text: respectively.

text: Under

text: the

text: hypothesis,

text: we

text: have,

text: for

text: all

text: λ

text: G

text: θ(k(t

text: z

text: (kt)

text: e

text: Wk

text: (k(t

text: s(k(t

text: H

text: n

text: n

text: θ

text: From

text: we

text: have,

text: (zn(kt)

text: η)

text: e

text: (=a)

text: exp

text: k(t

text: N

text: γj

text: N

text: −(γj(i)

text: Hjθj(t

text: Σj

text: (γj(i)

text: Hjθj(t

text: (≤b)

text: exp

text: N

text: φn,j(k

text: γj

text: N

text: (≤c)

text: λ

text: γj

text: (=d)

text: N

text: k(t

text: exp

text: λγj

text: (=e)

text: exp

text: −λη(k(t√

text: (k(t

text: Mn

text: λ)

text: Nrk

text: N

text: where

text: φ

text: (k

text: denotes

text: the

text: (n,

text: j)-th

text: entry

text: of

text: Wk

text: and

text: r

text: denotes

text: W

text: J

text: It

text: is

text: to

text: be

text: noted

text: that

text: (a)

text: follows

text: n,j

text: due

text: to

text: the

text: fact

text: that

text: under

text: the

text: hypothesis

text: the

text: observations

text: made

text: at

text: the

text: agents

text: are

text: of

text: the

text: form

text: y

text: (t)

text: γ

text: (t),

text: (b)

text: n

text: n

text: follows

text: due

text: to

text: the

text: fact

text: that

text: the

text: inverse

text: covariances

text: are

text: positive

text: deﬁnite

text: and

text: hence

text: the

text: quadratic

text: forms

text: are

text: positive,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 48  P ∗ (z (kt) < η) (cid:88) (cid:88) 1,θ n − = P ∗ −1 N φ (k − 1) k(t 1) θ(cid:62)(k(t − 1))H(cid:62)Σ−1γ (i) (cid:33) 1,θ (k(t 1) + 1) n,j j j j j j=1 i=0 − − ∗ (cid:62) − − − ∗ ∗ (cid:62) (cid:62) − ∗ −(Hj (θj(k(t 1)) θ )) Σj 1 (Hj (θj(k(t 1)) θ )) + (θ ) Hj Σj 1Hjθ < η (cid:88) 2 (cid:88) 2  − (≤a) P ∗ −1 N φ (k − 1) k(t 1) θ(cid:62)(k(t − 1))H(cid:62)Σ−1γ (i) (cid:16) (cid:17) 1,θ (k(t 1) + 1) n,j j j j j j=1 i=0 √  −(Hj (θj(k(t − 1)) − θ∗))(cid:62) Σ−j 1 (Hj (θj(k(t − 1)) − θ∗)) < η − (θ∗)(cid:62) Gθ∗ N1 − Nrk−1 (cid:88) 2 2  − − ∗ (cid:62) − − − ∗ (≤b) P ∗ N φ (k(cid:16)− 1)(Hj (θj(k((cid:17)t 1)) θ )) Σj 1 (Hj (θj(k(t 1)) θ )) 1,θ n,j 2 j=1 √  ∗ (cid:62) ∗ − − (θ ) Gθ 1 Nrk 1 > −η + N (cid:16) (cid:17) 2 4 (cid:88) (cid:88)  √  − ∗ (cid:62) ∗ − − + P ∗  −1 N φ (k − 1) k(t 1) θ(cid:62)(k(t − 1))H(cid:62)Σ−1γ (i(cid:16)) < η − (θ ) G(cid:17)θ N1 Nrk 1 1,θ (k(t 1) + 1) n,j j j j j 2 4 (cid:13) (cid:13) (cid:13) (cid:13)j=1 i=0 (cid:16) (cid:17)√  (≤c) P − (cid:62) (cid:107)θ(k(t − 1)) − θ∗ (cid:107)2 −2Nη + (θ∗)(cid:62) Gθ√∗ 1 − N Nrk−1 (cid:124) ∗ G Σ 1G N (cid:123)(cid:122)> (cid:125) 1,θ H H 2 − 4 1 + N Nrk 1  (cid:16) (cid:17) (cid:88) (cid:88)  (t1) √  − ∗ (cid:62) ∗ − − + P(cid:124) ∗ −1 N φ (k − 1) k(t 1) (θ (k(t − 1))(cid:123)−(cid:122) θ∗)(cid:62) H(cid:62)Σ−1γ (i) < η − (θ ) Gθ N1 Nrk 1 (cid:125) 1,θ (k(t 1) + 1) n,j j j j j 4 8  j=1 i=0 (cid:16) (cid:17) (cid:88) (cid:88)  (t2) √  − ∗ (cid:62) ∗ − − + P(cid:124) ∗ −1 N φ (k − 1) k(t 1) (θ∗)(cid:62)(cid:123)H(cid:122) (cid:62)Σ−1γ (i) < η − (θ ) Gθ N1 Nrk 1 (cid:125), 1,θ (k(t 1) + 1) n,j j j j 4 8 j=1 i=0 (t3) (145) √ | − − | ≤ − where (a) follows from φn,j(k 1) N1 Nrk√1, (b) follows from the union bound and (c) follows√from the | − − | ≤ − − − union bound and the inequality φ (k 1) 1 Nrk 1. Note that, Assumption B5 ensures that 1 Nrk 1 n,j N N is positive. ≤ First, we analyze the term (t1) in (145). We ﬁrst note that, if λ is chosen to be λ c , where 4 (cid:18) (cid:19) (cid:13) (cid:13) (cid:13) (cid:13) 1 c = , (146) 4 GHΣ−1G(cid:62)H c3 (tk1t+2c11)α20c1−α10 + kαt201 + 2c1αα200−1 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: P

text: (z

text: (kt)

text: η)

text: n

text: P

text: −1

text: N

text: φ

text: (k

text: k(t

text: (i)

text: (k(t

text: n,j

text: j

text: j

text: j

text: j

text: −(Hj

text: (θj(k(t

text: θ

text: Σj

text: (Hj

text: (θj(k(t

text: θ

text: (θ

text: Hj

text: Σj

text: η

text: (≤a)

text: P

text: −1

text: N

text: φ

text: (k

text: k(t

text: (i)

text: (k(t

text: n,j

text: j

text: j

text: j

text: j

text: −(Hj

text: (θj(k(t

text: Σ−j

text: (Hj

text: (θj(k(t

text: θ∗))

text: η

text: Gθ∗

text: (≤b)

text: P

text: N

text: φ

text: θ

text: Σj

text: (Hj

text: (θj(k(t

text: θ

text: n,j

text: (θ

text: Gθ

text: Nrk

text: −η

text: N

text: P

text: −1

text: N

text: φ

text: (k

text: k(t

text: η

text: (θ

text: Nrk

text: (k(t

text: n,j

text: j

text: j

text: j

text: j

text: (≤c)

text: P

text: θ∗

text: −2Nη

text: Gθ√∗

text: N

text: G

text: Σ

text: N

text: H

text: H

text: N

text: Nrk

text: −1

text: N

text: φ

text: (k

text: k(t

text: (θ

text: (k(t

text: (i)

text: η

text: (θ

text: Gθ

text: Nrk

text: (k(t

text: n,j

text: j

text: j

text: j

text: j

text: −1

text: N

text: φ

text: (k

text: k(t

text: (i)

text: η

text: (θ

text: Gθ

text: Nrk

text: (k(t

text: n,j

text: j

text: j

text: j

text: where

text: (a)

text: follows

text: from

text: φn,j(k

text: (b)

text: follows

text: from

text: the

text: union

text: bound

text: and

text: (c)

text: follows√from

text: the

text: union

text: bound

text: and

text: the

text: inequality

text: φ

text: (k

text: Nrk

text: Note

text: that,

text: Assumption

text: ensures

text: that

text: Nrk

text: n,j

text: N

text: N

text: is

text: positive.

text: First,

text: we

text: analyze

text: the

text: term

text: in

text: We

text: ﬁrst

text: note

text: that,

text: if

text: λ

text: is

text: chosen

text: to

text: be

text: λ

text: c

text: where

text: c

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 52 APPENDIX A PROOFS OF LEMMAS IN SECTION Proof of Lemma 6.1: The proof follows similarly as the proof of Lemma IV.1 in [40] with appropriate { } modiﬁcations to take into account the state-dependent nature of the innovation gains. Deﬁne the process x(t) as − ⊗ ∗ ∗ { } x(t) = θ(t) 1 θ where θ denotes the true but unknown parameter. The process x(t) satisﬁes the following N recursion: − ⊗ − − x(t + 1) = x(t) β (L I )x(t) + α G (θ(t)) Σ 1 (y(t) h(θ(t))) , (156) t M t which implies that, − ⊗ − − ∗ − − − ∗ x(t + 1) = x(t) β (L I )x(t) + α G (θ(t)) Σ 1 (y(t) h (θ )) α G (θ(t)) Σ 1 (h (θ(t)) h (θ )) . t M t N t N (157) It follows from basic properties of the Laplacian L, that ⊗ ⊗ ∗ ⊗ ∗ (L I ) (1 θ ) = (L1 ) (I θ ) = 0. (158) M N N M Taking norms of both sides of (156), we have, (cid:107) (cid:107) (cid:107) (cid:107) − (cid:62) ⊗ − (cid:62) − − ∗ x(t + 1) 2 = x(t) 2 2β x (t) (L I ) x(t) 2α x (t)G (θ(t)) Σ 1 (h (θ(t)) h (θ )) t M t N (cid:62) ⊗ (cid:62) ⊗ − − ∗ + β2x (t) (L I )2 x(t) + 2α β x (t) (L I ) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) t M t t M N − (cid:62) ⊗ − − ∗ 2α β x (t) (L I ) G (θ(t)) Σ 1 (y(t) h (θ )) t t M N − ∗ (cid:62) − (cid:62) − − ∗ + α2 (y(t) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (y(t) h (θ )) t N N − ∗ (cid:62) − (cid:62) − − ∗ (cid:62) − − ∗ + α2 (h (θ(t)) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) + 2α x (t)G (θ(t)) Σ 1 (y(t) h(θ )) t N N t N − − ∗ (cid:62) − (cid:62) − − ∗ 2α2 (y(t) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) . (159) t N N Consider the orthogonal decomposition, x = x + x ⊥, (160) c c C where x denotes the projection of x to the consensus subspace with c

text: APPENDIX

label: section

text: A

text: PROOFS

text: OF

text: LEMMAS

text: IN

text: SECTION

text: Proof

text: of

text: Lemma

text: The

text: proof

text: follows

text: similarly

text: as

text: the

text: proof

text: of

text: Lemma

text: in

text: with

text: appropriate

text: modiﬁcations

text: to

text: take

text: into

text: account

text: the

text: state-dependent

text: nature

text: of

text: the

text: innovation

text: gains.

text: Deﬁne

text: the

text: process

text: x(t)

text: as

text: x(t)

text: θ(t)

text: θ

text: where

text: θ

text: denotes

text: the

text: true

text: but

text: unknown

text: parameter.

text: The

text: process

text: x(t)

text: satisﬁes

text: the

text: following

text: N

text: recursion:

text: x(t

text: x(t)

text: β

text: (L

text: I

text: )x(t)

text: α

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h(θ(t)))

text: t

text: M

text: t

text: which

text: implies

text: that,

text: x(t

text: x(t)

text: β

text: (L

text: I

text: )x(t)

text: α

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: α

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: M

text: t

text: N

text: t

text: N

text: It

text: follows

text: from

text: basic

text: properties

text: of

text: the

text: Laplacian

text: L,

text: that

text: (L

text: I

text: θ

text: (I

text: θ

text: M

text: N

text: N

text: M

text: Taking

text: norms

text: of

text: both

text: sides

text: of

text: we

text: have,

text: x(t

text: x(t)

text: 2β

text: x

text: (t)

text: (L

text: I

text: x(t)

text: 2α

text: x

text: (t)G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: M

text: t

text: N

text: (t)

text: (L

text: I

text: x(t)

text: 2α

text: β

text: x

text: (t)

text: (L

text: I

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: M

text: t

text: t

text: M

text: N

text: 2α

text: β

text: x

text: (t)

text: (L

text: I

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: t

text: t

text: M

text: N

text: α2

text: (y(t)

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: t

text: N

text: N

text: α2

text: (h

text: (θ(t))

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: 2α

text: x

text: (t)G

text: (θ(t))

text: Σ

text: (y(t)

text: h(θ

text: t

text: N

text: N

text: t

text: N

text: (y(t)

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: N

text: N

text: Consider

text: the

text: orthogonal

text: decomposition,

text: x

text: x

text: x

text: c

text: c

text: C

text: where

text: x

text: denotes

text: the

text: projection

text: of

text: x

text: to

text: the

text: consensus

text: subspace

text: with

text: c


text: 53 C { ∈ R | ⊗ ∈ R } = x MN x = 1 a, for some a M . (161) N From, (3), we have that, E − ∗ ∗ [y(t) h (θ )] = 0. (162) θ N Consider the process (cid:107) (cid:107) V (t) = x(t) 2 . (163) 2 Using conditional independence properties we have, (cid:104) (cid:105) E ∗[V (t + 1)|F ] = V (t) + β2x(cid:62)(t) (L ⊗ I )2 x(t) θ 2 t 2 t M E − ∗ (cid:62) − (cid:62) − − ∗ − (cid:62) ⊗ + α2 ∗ (y(t) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (y(t) h (θ )) 2β x (t) (L I ) x(t) t θ N N t M (cid:13) (cid:13) − (cid:13) (cid:62) − − ∗ (cid:13) (cid:62) ⊗ − − ∗ 2α(cid:13)x (t)G (θ(t)) Σ 1 (h (θ(t)) h (θ )(cid:13)) + 2α β x (t) (L I ) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) t N t t M N − ∗ (cid:62) (cid:62) − 2 + α2 (h (θ(t)) h (θ )) G (θ(t)) Σ 1 . (164) t N ∀ ≥ We use the following inequalities t t , 1 (cid:62) ⊗ (q≤1) || || x (t) (L I )2 x(t) λ2 (L) x ⊥(t) 2; M N C (cid:62) − − ∗ ≥ || || (q≥2) x (t)G (θ(t)) Σ 1 (h (θ(t)) h (θ )) c x(t) 2 0; N 1 (cid:62) ⊗ (q≥3) (cid:107) (cid:107) x (t) (L I ) x(t) λ (L) x ⊥(t) 2 ; M 2 C (cid:62) ⊗ − − ∗ (q≤4) (cid:107) (cid:107) x (t) (L I ) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) c x(t) 2 , (165) M N 2 for c as deﬁned in Assumption A4, and a positive constant c , where (q2) follows from Assumption A4 and (q4) 1 2 (cid:107)∇ (cid:107) follows from Assumption A3 by which we have that h (θ (t)) is uniformly bounded from above by k for n n n (cid:107) (cid:107) ≤ all n, and hence, we have that G (θ(t)) max ··· k . We also have n=1, ,N n (cid:104) (cid:105) E − ∗ (cid:62) − (cid:62) − − ∗ ≤ ∗ (y(t) h (θ )) Σ 1G (θ(t))G (θ(t)) Σ 1 (y(t) h (θ )) c , (166) θ N N 4

text: C

text: R

text: R

text: x

text: MN

text: x

text: a,

text: for

text: some

text: a

text: M

text: N

text: From,

text: we

text: have

text: that,

text: E

text: [y(t)

text: h

text: (θ

text: θ

text: N

text: Consider

text: the

text: process

text: V

text: (t)

text: x(t)

text: Using

text: conditional

text: independence

text: properties

text: we

text: have,

text: E

text: ∗[V

text: (t

text: V

text: (t)

text: (L

text: I

text: x(t)

text: θ

text: t

text: t

text: M

text: E

text: α2

text: (y(t)

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: 2β

text: x

text: (t)

text: (L

text: I

text: x(t)

text: t

text: θ

text: N

text: N

text: t

text: M

text: (t)G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: 2α

text: β

text: x

text: (t)

text: (L

text: I

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: t

text: N

text: t

text: t

text: M

text: N

text: α2

text: (h

text: (θ(t))

text: h

text: (θ

text: G

text: (θ(t))

text: Σ

text: t

text: N

text: We

text: use

text: the

text: following

text: inequalities

text: t

text: t

text: x

text: (t)

text: (L

text: I

text: x(t)

text: λ2

text: (L)

text: x

text: ⊥(t)

text: M

text: N

text: C

text: x

text: (t)G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: c

text: x(t)

text: N

text: x

text: (t)

text: (L

text: I

text: x(t)

text: λ

text: (L)

text: x

text: ⊥(t)

text: M

text: C

text: x

text: (t)

text: (L

text: I

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: c

text: x(t)

text: M

text: N

text: for

text: c

text: as

text: deﬁned

text: in

text: Assumption

text: and

text: a

text: positive

text: constant

text: c

text: where

text: follows

text: from

text: Assumption

text: and

text: follows

text: from

text: Assumption

text: by

text: which

text: we

text: have

text: that

text: h

text: (θ

text: (t))

text: is

text: uniformly

text: bounded

text: from

text: above

text: by

text: k

text: for

text: n

text: n

text: n

text: all

text: n,

text: and

text: hence,

text: we

text: have

text: that

text: G

text: (θ(t))

text: max

text: k

text: We

text: also

text: have

text: ,N

text: n

text: E

text: (y(t)

text: h

text: (θ

text: Σ

text: (θ(t))G

text: (θ(t))

text: Σ

text: (y(t)

text: h

text: (θ

text: c

text: θ

text: N

text: N


text: 54 for some constant c > 0. In (166), we use the fact that the noise process under consideration is Gaussian and 4 (cid:107) (cid:107) ≤ hence has ﬁnite moments. We also use the fact that G (θ(t)) max ··· k , which in turn follows from n=1, ,N n Assumption A3. We further have that, − ∗ (cid:62) − (cid:62) − − ∗ ≤ (cid:107) (cid:107) (h (θ(t)) h (θ )) Σ 1G (θ(t)) G (θ(t)) Σ 1 (h (θ(t)) h (θ )) c x(t) 2 , (167) N N 3 where c > 0 is a constant. It is to be noted that (167) follows from the Lipschitz continuity in Assumption A3 3 (cid:107) (cid:107) ≤ and the fact that G (θ(t)) max ··· k . n=1, ,N n Using (164)-(167), we have, (cid:0) (cid:0) (cid:1)(cid:1) E |F ≤ − − || || ∗[V (t + 1) ] 1 + c α β + α2 V (t) c (β β2) x ⊥(t) 2 + c α2, (168) θ 2 t 5 t t t 2 6 t t C 4 t ∃ ∀ ≥ ≥ for some positive constants c and c . As β2 goes to zero faster than β , t such that t t , β β2. Hence 5 6 t t 2 2 t t ∃ ∃ ≥ t and τ , τ > 1 such that for all t t 2 1 2 2 (cid:0) (cid:1) ≤ c ≤ c c α β + α2 7 = γ , c α2 8 = γˆ (169) 5 t t t (t + 1)τ1 t 4 t (t + 1)τ2 t where c , c > 0 are constants. 7 8 ∀ ≥ By the above construction we obtain, t t , 2 E |F ≤ ∗[V (t + 1) ] (1 + γ )V (t) + γˆ , (170) θ 2 t t 2 t { } { } where the positive weight sequences γ and γˆ are summable, i.e., t t (cid:88) (cid:88) ∞ ∞ γ < , γˆ < . (171) t t (cid:81) t≥0 t≥0 ∞ { } By (171), the product s=t(1 + γs) exist(cid:32)s for all t. No(cid:33)w let W(t) be such that (cid:89) (cid:88) ∞ ∞ ∀ ≥ W(t) = (1 + γ ) V (t) + γˆ , t t . (172) s 2 s 2 s=t s=t ##LTLine## ##LTLine##

text: for

text: some

text: constant

text: c

text: In

text: we

text: use

text: the

text: fact

text: that

text: the

text: noise

text: process

text: under

text: consideration

text: is

text: Gaussian

text: and

text: hence

text: has

text: ﬁnite

text: moments.

text: We

text: also

text: use

text: the

text: fact

text: that

text: G

text: (θ(t))

text: max

text: k

text: which

text: in

text: turn

text: follows

text: from

text: ,N

text: n

text: Assumption

text: We

text: further

text: have

text: that,

text: (h

text: (θ(t))

text: h

text: (θ

text: Σ

text: (θ(t))

text: G

text: (θ(t))

text: Σ

text: (h

text: (θ(t))

text: h

text: (θ

text: c

text: x(t)

text: N

text: N

text: where

text: c

text: is

text: a

text: constant.

text: It

text: is

text: to

text: be

text: noted

text: that

text: follows

text: from

text: the

text: Lipschitz

text: continuity

text: in

text: Assumption

text: and

text: the

text: fact

text: that

text: G

text: (θ(t))

text: max

text: k

text: ,N

text: n

text: Using

text: we

text: have,

text: E

text: |F

text: ∗[V

text: (t

text: c

text: α

text: β

text: α2

text: V

text: (t)

text: c

text: (β

text: x

text: ⊥(t)

text: c

text: θ

text: t

text: t

text: t

text: t

text: t

text: t

text: C

text: t

text: for

text: some

text: positive

text: constants

text: c

text: and

text: c

text: As

text: β2

text: goes

text: to

text: zero

text: faster

text: than

text: β

text: t

text: such

text: that

text: t

text: t

text: β

text: Hence

text: t

text: t

text: t

text: t

text: t

text: and

text: τ

text: τ

text: such

text: that

text: for

text: all

text: t

text: t

text: c

text: c

text: c

text: α

text: β

text: α2

text: γ

text: c

text: α2

text: γˆ

text: t

text: t

text: t

text: (t

text: t

text: t

text: (t

text: t

text: where

text: c

text: c

text: are

text: constants.

text: By

text: the

text: above

text: construction

text: we

text: obtain,

text: t

text: t

text: E

text: |F

text: ∗[V

text: (t

text: γ

text: )V

text: (t)

text: γˆ

text: θ

text: t

text: t

text: t

text: where

text: the

text: positive

text: weight

text: sequences

text: γ

text: and

text: γˆ

text: are

text: summable,

text: i.e.,

text: t

text: t

text: γ

text: γˆ

text: t

text: t

text: By

text: the

text: product

text: γs)

text: for

text: all

text: t.

text: let

text: W(t)

text: be

text: such

text: that

text: W(t)

text: γ

text: V

text: (t)

text: γˆ

text: t

text: t

text: s

text: s

text: s=t

text: s=t

text: ##LTLine##

text: ##LTLine##


text: 55 { } By (172), it can be shown that W(t) satisﬁes, E |F ≤ ∗[W(t + 1) ] W(t). (173) θ t { } ∗ → ∞ Hence, W(t) is a non-negative super martingale and converges a.s. to a bounded random variable W as t . → ∗ → ∞ { } It then follows from (172) that V (t) W as t . Thus, we conclude that the sequences θ (t) are bounded 2 n for all n. Proof of Lemma 6.2: The proof follows exactly the development in theorem IV.1 of [40]. Let x(t) denote the − ⊗ ∗ residual θ(t) 1 θ . N ∈ For (cid:15) (0, 1), deﬁne the set Γ (cid:15) (cid:26) (cid:27) ∈ R ≤ (cid:107) − ⊗ ∗(cid:107) ≤ 1 Γ = θ NM : (cid:15) θ 1 θ . (174) (cid:15) N (cid:15) {F } Let ρ denote the stopping time (cid:15) t { ≥ ∈ } ρ = inf t 0 : θ(t) / Γ , (175) (cid:15) (cid:15) { } where Γ is deﬁned in (174). Let V (cid:15)(t) denote the stopped process (cid:15) { } ∀ V (cid:15)(t) = V (max t, ρ ), t, (176) 2 (cid:15) with V (t) as deﬁned in (163). 2 Then, we have, I I ≤ V (cid:15)(t + 1) = V (t + 1) (ρ > t) + V (ρ ) (ρ t) , (177) 2 (cid:15) 2 (cid:15) (cid:15) I · I I ≤ F where ( ) denotes the indicator function. Due to the fact that (ρ > t) and V (ρ ) (ρ t) are adapted to for (cid:15) 2 (cid:15) (cid:15) t all t, we have, E |F E I I ≤ ∗ [V (cid:15)(t + 1) ] = ∗ [V (t + 1)] (ρ > t) + V (ρ ) (ρ t) , (178) θ t θ 2 (cid:15) 2 (cid:15) (cid:15) ##LTLine##

text: By

text: it

text: can

text: be

text: shown

text: that

text: W(t)

text: satisﬁes,

text: E

text: |F

text: ∗[W(t

text: W(t).

text: θ

text: t

text: Hence,

text: W(t)

text: is

text: a

text: non-negative

text: super

text: martingale

text: and

text: converges

text: a.s.

text: to

text: a

text: bounded

text: random

text: variable

text: W

text: as

text: t

text: It

text: then

text: follows

text: from

text: that

text: V

text: (t)

text: W

text: as

text: t

text: Thus,

text: we

text: conclude

text: that

text: the

text: sequences

text: θ

text: (t)

text: are

text: bounded

text: n

text: for

text: all

text: n.

text: Proof

text: of

text: Lemma

text: The

text: proof

text: follows

text: exactly

text: the

text: development

text: in

text: theorem

text: of

text: Let

text: x(t)

text: denote

text: the

text: residual

text: θ(t)

text: θ

text: N

text: For

text: deﬁne

text: the

text: set

text: Γ

text: R

text: Γ

text: θ

text: NM

text: θ

text: θ

text: N

text: {F

text: Let

text: ρ

text: denote

text: the

text: stopping

text: time

text: t

text: ρ

text: inf

text: t

text: θ(t)

text: Γ

text: where

text: Γ

text: is

text: deﬁned

text: in

text: Let

text: V

text: denote

text: the

text: stopped

text: process

text: V

text: V

text: (max

text: t,

text: ρ

text: t,

text: with

text: V

text: (t)

text: as

text: deﬁned

text: in

text: Then,

text: we

text: have,

text: I

text: I

text: V

text: V

text: (t

text: (ρ

text: t)

text: V

text: (ρ

text: (ρ

text: t)

text: I

text: I

text: I

text: F

text: where

text: denotes

text: the

text: indicator

text: function.

text: Due

text: to

text: the

text: fact

text: that

text: (ρ

text: t)

text: and

text: V

text: (ρ

text: (ρ

text: t)

text: are

text: adapted

text: to

text: for

text: t

text: all

text: t,

text: we

text: have,

text: E

text: |F

text: E

text: I

text: I

text: [V

text: [V

text: (t

text: (ρ

text: t)

text: V

text: (ρ

text: (ρ

text: t)

text: θ

text: t

text: θ

text: ##LTLine##


text: 7 Furthermore, a graph is connected if and only if λ (L) > 0 (see [42] for instance). 2 2. PROBLEM FORMULATION A. System Model and Preliminaries There are N agents deployed in the network. Every agent n at time index t makes a noisy observation y (t). n ∗ The observation y (t) is a M -dimensional vector, a noisy nonlinear function of θ which is a M-dimensional n n ∗ ∈ R P H parameter, i.e., θ M. The observation y (t) comes from a probability distribution under the hypothesis , n 0 0 H whereas, under the composite alternative , the observation is sampled from a probability distribution which is 1 {P } ∗ a member of a parametric family ∗ . We emphasize here that the parameter θ is deterministic but unknown. θ Formally, H ∗ : y (t) = h (θ ) + γ (t) 1 n n n H : y (t) = γ (t), (3) 0 n n { } R where hn(.) is, in general, non-linear function, yn(t) is a Mn-valued observation sequence for the n-th agent, { } where typically M << M and γ (t) is a zero-mean temporally i.i.d Gaussian noise sequence at the n-th agent n n ∈ R × with nonsingular covariance matrix Σn, where Σn Mn Mn. Moreover, the noise sequences at two agents n, l (cid:54) with n = l are independent. ∀ By taking h (0) = 0, n and certain other identiﬁability and regularity conditions outlined below, in the above n ∗ ∗ (cid:54) formulation the null hypothesis corresponds to θ = 0 and the composite alternative to the case θ = 0. Since, the sources of randomness in our formulation are the observations y (t)’s made by the agents in the network, n {F } we deﬁne the natural ﬁltration generated by the random observations, i.e., t (cid:0) (cid:1) F {{ } } − = σ y (s) N t 1 , (4) t n n=1 s=0 which is the sequence of σ-algebras induced by the observation processes, in order to model the overall available { } {F } network information at all times. Finally, a stochastic process x(t) is said to be -adapted if the σ-algebra t F σ (x(t)) is a subset of at each t. t B. Preliminaries : Generalized Likelihood Ratio Tests We start by reviewing some concepts from the classical theory of Generalized Likelihood Ratio Tests (GLRT). Consider, for instance, a generalized target detection problem in which the absence of target is modeled by a H H simple hypothesis , whereas, its presence corresponds to a composite alternative , as it is parametrized by a 0 (cid:2) (cid:3) 1 (cid:80) continuous vector parameter (perhaps modeling its location and other attributes) which is unknown apriori. Let y(t) (cid:62) · · · (cid:62) (cid:62) denote the collection of the data from the agents, i.e., y(t) = y (t) y (t) , at time t, which is N M 1 N n=1 n dimensional. In a centralized setup, where there is a fusion center having access to the entire y(t) at all times t,

text: Furthermore,

text: a

text: graph

text: is

text: connected

text: if

text: and

text: only

text: if

text: λ

text: (L)

text: (see

text: for

text: instance).

text: PROBLEM

text: FORMULATION

text: A.

text: System

text: Model

text: and

text: Preliminaries

text: There

text: are

text: N

text: agents

text: deployed

text: in

text: the

text: network.

text: Every

text: agent

text: n

text: at

text: time

text: index

text: t

text: makes

text: a

text: noisy

text: observation

text: y

text: (t).

text: n

text: The

text: observation

text: y

text: (t)

text: is

text: a

text: M

text: -dimensional

text: vector,

text: a

text: noisy

text: nonlinear

text: function

text: of

text: θ

text: which

text: is

text: a

text: M-dimensional

text: n

text: n

text: R

text: P

text: H

text: parameter,

text: i.e.,

text: θ

text: M.

text: The

text: observation

text: y

text: (t)

text: comes

text: from

text: a

text: probability

text: distribution

text: under

text: the

text: hypothesis

text: n

text: H

text: whereas,

text: under

text: the

text: composite

text: alternative

text: the

text: observation

text: is

text: sampled

text: from

text: a

text: probability

text: distribution

text: which

text: is

text: {P

text: a

text: member

text: of

text: a

text: parametric

text: family

text: We

text: emphasize

text: here

text: that

text: the

text: parameter

text: θ

text: is

text: deterministic

text: but

text: unknown.

text: θ

text: Formally,

text: H

text: y

text: (t)

text: h

text: (θ

text: γ

text: (t)

text: n

text: n

text: n

text: H

text: y

text: (t)

text: γ

text: (t),

text: n

text: n

text: R

text: where

text: hn(.)

text: is,

text: in

text: general,

text: non-linear

text: function,

text: yn(t)

text: is

text: a

text: Mn-valued

text: observation

text: sequence

text: for

text: the

text: n-th

text: agent,

text: where

text: typically

text: M

text: M

text: and

text: γ

text: (t)

text: is

text: a

text: zero-mean

text: temporally

text: i.i.d

text: Gaussian

text: noise

text: sequence

text: at

text: the

text: n-th

text: agent

text: n

text: n

text: R

text: with

text: nonsingular

text: covariance

text: matrix

text: Σn,

text: where

text: Σn

text: Mn

text: Mn.

text: Moreover,

text: the

text: noise

text: sequences

text: at

text: two

text: agents

text: n,

text: l

text: with

text: n

text: l

text: are

text: independent.

text: By

text: taking

text: h

text: n

text: and

text: certain

text: other

text: identiﬁability

text: and

text: regularity

text: conditions

text: outlined

text: below,

text: in

text: the

text: above

text: n

text: formulation

text: the

text: hypothesis

text: corresponds

text: to

text: θ

text: and

text: the

text: composite

text: alternative

text: to

text: the

text: case

text: θ

text: Since,

text: the

text: sources

text: of

text: randomness

text: in

text: our

text: formulation

text: are

text: the

text: observations

text: y

text: (t)’s

text: made

text: by

text: the

text: agents

text: in

text: the

text: network,

text: n

text: {F

text: we

text: deﬁne

text: the

text: natural

text: ﬁltration

text: generated

text: by

text: the

text: random

text: observations,

text: i.e.,

text: t

text: F

text: σ

text: y

text: (s)

text: N

text: t

text: t

text: n

text: which

text: is

text: the

text: sequence

text: of

text: σ-algebras

text: induced

text: by

text: the

text: observation

text: processes,

text: in

text: order

text: to

text: model

text: the

text: overall

text: available

text: {F

text: network

text: information

text: at

text: all

text: times.

text: Finally,

text: a

text: stochastic

text: process

text: x(t)

text: is

text: said

text: to

text: be

text: -adapted

text: if

text: the

text: σ-algebra

text: t

text: F

text: σ

text: (x(t))

text: is

text: a

text: subset

text: of

text: at

text: each

text: t.

text: t

text: B.

text: Preliminaries

text: Generalized

text: Likelihood

text: Ratio

text: Tests

text: We

text: start

text: by

text: reviewing

text: some

text: concepts

text: from

text: the

text: classical

text: theory

text: of

text: Generalized

text: Likelihood

text: Ratio

text: Tests

text: (GLRT).

text: Consider,

text: for

text: instance,

text: a

text: generalized

text: target

text: detection

text: problem

text: in

text: which

text: the

text: absence

text: of

text: target

text: is

text: modeled

text: by

text: a

text: H

text: H

text: simple

text: hypothesis

text: whereas,

text: its

text: presence

text: corresponds

text: to

text: a

text: composite

text: alternative

text: as

text: it

text: is

text: parametrized

text: by

text: a

text: continuous

text: vector

text: parameter

text: (perhaps

text: modeling

text: its

text: location

text: and

text: other

text: attributes)

text: which

text: is

text: unknown

text: apriori.

text: Let

text: y(t)

text: denote

text: the

text: collection

text: of

text: the

text: data

text: from

text: the

text: agents,

text: i.e.,

text: y(t)

text: y

text: (t)

text: y

text: (t)

text: at

text: time

text: t,

text: which

text: is

text: N

text: M

text: N

text: n

text: dimensional.

text: In

text: a

text: centralized

text: setup,

text: where

text: there

text: is

text: a

text: fusion

text: center

text: having

text: access

text: to

text: the

text: entire

text: y(t)

text: at

text: all

text: times

text: t,


text: 67 (cid:88) (cid:89) (cid:88) (cid:89) − − t (cid:107) (cid:107) ≤ t 1 − t t 1 − [(cid:18)P ] (cid:19)c (1 c α )2(cid:18)+ α(cid:19)2 (1 c α )2 t ii 3 (cid:88)1 u v 1 u i=1 u=t1 v=t1 u=v+1 − ≤ t + 1 2c1α0 t 1 u + 1 2c1α0 c (cid:18) 1 (cid:19) + α2 3 t (cid:88) u t u=t1+1 − t + 1 2c1α0 t 1 1 = c3 (cid:18) 1 t (cid:19) + α02 t(cid:88)2c1α0(u + 1)2−2c1α0 u=t1+1 − t + 1 2c1α0 α2 t 2 1 = c3 (cid:18) 1 t (cid:19) + t20 + α02 (cid:90) t2c1α0(u + 1)2−2c1α0 u=t1+1 − (≤a) (cid:18) t + 1(cid:19) 2c1α0 α2 α2 (cid:18) t 1 (cid:19)1 c3 1 t + t20 + t2c10α0 t1 (s + 1)2−2c1α0 ds − ≤ c t1 + 1 2c1α0 + α02 + α02 t2c1α0−1 . (246) 3 t t2 t2c1α0 2c1α0 1 ≥ The above implies that, for all t t , 1 (cid:88) t (cid:107) (cid:107) t [P ] t ii i=1 (≤b) (t + 1)2c1α0 α2 α2 c3 1t2c1α0−1 + t0 + 2c1α00− 1. (247) − where in (a) and (b), we use the fact that 2c α 1 > 1 by Assumption B6. The proof follows by noting that 1 0 the RHS of (247) is a non-increasing function of t. APPENDIX C PROOF OF THEOREMS IN SECTION Proof of Theorem 5.2: The proof for the large deviations upper bound of the probability of false alarm proposed in Theorem 5.2 exactly (cid:13) (cid:13) (cid:13) (cid:13) CIGLRT − L follows the derivation of the large deviations upper bound of the probability of false alarm of . − − − (cid:62) It follows from (130)-(134). The characterization of I β L α G Σ 1G exactly follows from 7.1. By N t t H H restricting 7.1 to the observation model described in which satisﬁes Assumptions B1-B5 and B7, we have that on ∀ ≥ choosing a t such that t t , 2 2 h2 β λ (L) + α < 1. (248) t N t σ2 − − − (cid:62) This guarantees that all the eigenvalues of I β L α G Σ 1G are positive. From 7.1, we have that there N t t H H ≥ exists t , such that for all t t 1 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: t

text: t

text: t

text: t

text: c

text: α

text: c

text: α

text: t

text: ii

text: u

text: v

text: u

text: t

text: t

text: u

text: c

text: α2

text: t

text: u

text: t

text: t

text: t

text: t

text: t

text: α2

text: t

text: t

text: (≤a)

text: t

text: α2

text: α2

text: t

text: t

text: (s

text: ds

text: c

text: t

text: The

text: above

text: implies

text: that,

text: for

text: all

text: t

text: t

text: t

text: t

text: [P

text: t

text: ii

text: (≤b)

text: (t

text: α2

text: α2

text: where

text: in

text: (a)

text: and

text: (b),

text: we

text: use

text: the

text: fact

text: that

text: α

text: by

text: Assumption

text: The

text: proof

text: follows

text: by

text: noting

text: that

text: the

text: RHS

text: of

text: is

text: a

text: non-increasing

text: function

text: of

text: t.

text: APPENDIX

text: C

text: PROOF

text: OF

text: THEOREMS

text: IN

text: SECTION

text: Proof

text: of

text: Theorem

text: The

text: proof

text: for

text: the

text: large

text: deviations

text: upper

text: bound

text: of

text: the

text: probability

text: of

text: false

text: alarm

text: proposed

text: in

text: Theorem

text: exactly

text: CIGLRT

text: L

text: follows

text: the

text: derivation

text: of

text: the

text: large

text: deviations

text: upper

text: bound

text: of

text: the

text: probability

text: of

text: false

text: alarm

text: of

text: It

text: follows

text: from

text: The

text: characterization

text: of

text: I

text: β

text: L

text: α

text: G

text: Σ

text: exactly

text: follows

text: from

text: By

text: N

text: t

text: t

text: H

text: H

text: restricting

text: to

text: the

text: observation

text: model

text: described

text: in

text: which

text: satisﬁes

text: Assumptions

text: and

text: we

text: have

text: that

text: on

text: choosing

text: a

text: t

text: such

text: that

text: t

text: t

text: β

text: λ

text: (L)

text: α

text: t

text: N

text: t

text: σ2

text: This

text: guarantees

text: that

text: all

text: the

text: eigenvalues

text: of

text: I

text: β

text: L

text: α

text: G

text: Σ

text: are

text: positive.

text: From

text: we

text: have

text: that

text: there

text: N

text: t

text: t

text: H

text: H

text: exists

text: t

text: such

text: that

text: for

text: all

text: t

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: DEFEATING THE BEN-ZVI, BLACKBURN, AND TSABAN ATTACK ON THE ALGEBRAIC ERASER IRIS ANSHEL, DEREK ATKINS, DORIAN GOLDFELD, AND PAUL E. GUNNELLS Abstract. The Algebraic Eraser Diﬃe–Hellman (AEDH) protocol was introduced in 2005 and published in 2006 by I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux as a protocol suitable for use on platforms with constrained computational resources, such as FPGAs, ASICs, and wireless sensors. It is a group-theoretic cryptographic protocol that allows two users to construct a shared secret via a Diﬃe–Hellman-type scheme over an insecure channel. Building on the refuted 2012 permutation-based attack of Kalka–Teichner–Tsaban (KKT), Ben-Zvi, Blackburn, and Tsaban (BBT) present a heuristic attack, published November 13, 2015, that attempts to recover the AEDH shared secret. In their paper BBT reference the AEDH protocol as presented to ISO for certiﬁcation (ISO 29167-20) by SecureRF. The ISO 29167-20 draft contains two proﬁles using the Algebraic Eraser. One proﬁle is unaﬀected by this attack; the second proﬁle is subject to their attack provided the attack runs in real time. This is not the case in most practical deployments. The BBT attack is simply a targeted attack that does not attempt to break the method, sys- tem parameters, or recover any private keys. Rather, its limited focus is to recover the shared secret in a single transaction. In addition, the BBT attack is based on several conjectures that are assumed to hold when parameters are chosen according to standard distributions, which can be mitigated, if not avoided. This paper shows how to choose special distributions so that these conjectures do not hold making the BBT attack ineﬀective for braid groups with suﬃciently many strands. Further, the BBT attack assumes that certain data is available to an attacker, but there are realistic deployment scenarios where this is not the case, making the attack fail completely. In summary, the BBT attack is ﬂawed (with respect to the SecureRF ISO draft) and, at a minimum, over-reaches as to its applicability. 1. Introduction The Algebraic Eraser Diﬃe–Hellman protocol (AEDH, originally AEKAP) was introduced in 2005 and published in 2006 by Anshel, Anshel, Goldfeld, and Lemieux [1] as a protocol suitable for use on computationally constrained resource platforms, e.g., FPGAs, ASICs, and wireless sensors. More speciﬁcally, AEDH is a Group-Theoretic public-key system designed as a computationally eﬃcient solution for low-power or passive embedded systems and devices associated with, among other things, the Internet of Things (IoT). In November, 2015, Ben-Zvi, Blackburn, and Tsaban (BBT), leveraging the refuted 2012 permutation-based attack of Kalka, Teichner, and Tsaban (KTT) [3],1 published a paper [2] claiming a successful attack against AEDH. In the abstract of [2] it is pointed out that certain implementations of AEDH are proposed as an underlying technology for ISO/IEC 29167-20. Date: May 28, 2020. 1991 Mathematics Subject Classiﬁcation. 20F36, 94A60. Key words and phrases. Algebraic eraser, colored Burau key agreement protocol, group theoretic cryptog- raphy, braid groups. 1KKT acknowleged the successful refutation. 1 ##LTLine##

text: DEFEATING

text: THE

text: BEN-ZVI,

text: BLACKBURN,

text: AND

text: TSABAN

text: ATTACK

text: ON

text: THE

text: ALGEBRAIC

text: ERASER

text: IRIS

text: ANSHEL,

text: DEREK

text: ATKINS,

text: DORIAN

text: GOLDFELD,

text: AND

text: PAUL

text: E.

text: GUNNELLS

text: Abstract.

text: The

label: abstract

text: Algebraic

text: Eraser

text: Diﬃe–Hellman

text: (AEDH)

text: protocol

text: was

text: introduced

text: in

text: and

text: published

text: in

text: by

text: I.

text: Anshel,

text: M.

text: Anshel,

text: D.

text: Goldfeld,

text: and

text: S.

text: Lemieux

text: as

text: a

text: protocol

text: suitable

text: for

text: use

text: on

text: platforms

text: with

text: constrained

text: computational

text: resources,

text: such

text: as

text: FPGAs,

text: ASICs,

text: and

text: wireless

text: sensors.

text: It

text: is

text: a

text: group-theoretic

text: cryptographic

text: protocol

text: that

text: allows

text: two

text: users

text: to

text: construct

text: a

text: shared

text: secret

text: via

text: a

text: Diﬃe–Hellman-type

text: scheme

text: over

text: an

text: insecure

text: channel.

text: Building

text: on

text: the

text: refuted

text: permutation-based

text: attack

text: of

text: Kalka–Teichner–Tsaban

text: (KKT),

text: Ben-Zvi,

text: Blackburn,

text: and

text: Tsaban

text: (BBT)

text: present

text: a

text: heuristic

text: attack,

text: published

text: November

text: that

text: attempts

text: to

text: recover

text: the

text: AEDH

text: shared

text: secret.

text: In

text: their

text: paper

text: BBT

text: reference

text: the

text: AEDH

text: protocol

text: as

text: presented

text: to

text: ISO

text: for

text: certiﬁcation

text: (ISO

text: by

text: SecureRF.

text: The

text: ISO

text: draft

text: contains

text: two

text: proﬁles

text: using

text: the

text: Algebraic

text: Eraser.

text: One

text: proﬁle

text: is

text: unaﬀected

text: by

text: this

text: attack;

text: the

text: second

text: proﬁle

text: is

text: subject

text: to

text: their

text: attack

text: provided

text: the

text: attack

text: runs

text: in

text: real

text: time.

text: This

text: is

text: not

text: the

text: case

text: in

text: most

text: practical

text: deployments.

text: The

text: BBT

text: attack

text: is

text: simply

text: a

text: targeted

text: attack

text: that

text: does

text: not

text: attempt

text: to

text: break

text: the

text: method,

text: sys-

text: tem

text: parameters,

text: or

text: recover

text: any

text: private

text: keys.

text: Rather,

text: its

text: limited

text: focus

text: is

text: to

text: recover

text: the

text: shared

text: secret

text: in

text: a

text: single

text: transaction.

text: In

text: addition,

text: the

text: BBT

text: attack

text: is

text: based

text: on

text: several

text: conjectures

text: that

text: are

text: assumed

text: to

text: hold

text: when

text: parameters

text: are

text: chosen

text: according

text: to

text: standard

text: distributions,

text: which

text: can

text: be

text: mitigated,

text: if

text: not

text: avoided.

text: This

text: paper

text: shows

text: how

text: to

text: choose

text: special

text: distributions

text: so

text: that

text: these

text: conjectures

text: do

text: not

text: hold

text: making

text: the

text: BBT

text: attack

text: ineﬀective

text: for

text: braid

text: groups

text: with

text: suﬃciently

text: many

text: strands.

text: Further,

text: the

text: BBT

text: attack

text: assumes

text: that

text: certain

text: data

text: is

text: available

text: to

text: an

text: attacker,

text: but

text: there

text: are

text: realistic

text: deployment

text: scenarios

text: where

text: this

text: is

text: not

text: the

text: case,

text: making

text: the

text: attack

text: fail

text: completely.

text: In

text: summary,

text: the

text: BBT

text: attack

text: is

text: ﬂawed

text: (with

text: respect

text: to

text: the

text: SecureRF

text: ISO

text: draft)

text: and,

text: at

text: a

text: minimum,

text: over-reaches

text: as

text: to

text: its

text: applicability.

text: Introduction

text: The

text: Algebraic

text: Eraser

text: Diﬃe–Hellman

text: protocol

text: (AEDH,

text: originally

text: AEKAP)

text: was

text: introduced

text: in

text: and

text: published

text: in

text: by

text: Anshel,

text: Anshel,

text: Goldfeld,

text: and

text: Lemieux

text: as

text: a

text: protocol

text: suitable

text: for

text: use

text: on

text: computationally

text: constrained

text: resource

text: platforms,

text: e.g.,

text: FPGAs,

text: ASICs,

text: and

text: wireless

text: sensors.

text: More

text: speciﬁcally,

text: AEDH

text: is

text: a

text: Group-Theoretic

text: public-key

text: system

text: designed

text: as

text: a

text: computationally

text: eﬃcient

text: solution

text: for

text: low-power

text: or

text: passive

text: embedded

text: systems

text: and

text: devices

text: associated

text: with,

text: among

text: other

text: things,

text: the

text: Internet

text: of

text: Things

text: (IoT).

text: In

text: November,

text: Ben-Zvi,

text: Blackburn,

text: and

text: Tsaban

text: (BBT),

text: leveraging

text: the

text: refuted

text: permutation-based

text: attack

text: of

text: Kalka,

text: Teichner,

text: and

text: Tsaban

text: (KTT)

text: published

text: a

text: paper

text: claiming

text: a

text: successful

text: attack

text: against

text: AEDH.

text: In

text: the

text: abstract

text: of

text: it

text: is

text: pointed

text: out

text: that

text: certain

text: implementations

text: of

text: AEDH

text: are

text: proposed

text: as

text: an

text: underlying

text: technology

text: for

text: ISO/IEC

text: Date:

text: May

text: Mathematics

text: Subject

text: Classiﬁcation.

text: Key

text: words

text: and

text: phrases.

text: Algebraic

text: eraser,

text: colored

text: Burau

text: key

text: agreement

text: protocol,

text: group

text: theoretic

text: cryptog-

text: raphy,

text: braid

text: groups.

text: acknowleged

text: the

text: successful

text: refutation.

text: ##LTLine##


text: L.H.C. Borges, F.A. Barone : Traces of Lorentz symmetry breaking in a Hydrogen atom at ground state: 9 to CNPq for ﬁnancial support. The authors would like to thank J.A. Helay¨el-Neto for reading the paper. References 1. D. Colladay and V. Alan Kostelecky´, Phys. Rev. D 55, 6760 (1997). 2. D. Colladay and V. Alan Kostelecky´, Phys Rev. D 58, 116002 (1998). 3. A. Kostelecky and N. Russell, Rev. Mod. Phys. 83, 11 (2011) [arXiv:0801.0287]. 4. L.H.C.Borges, F. A. Barone and J.A. Helay¨el-Neto, Eur. Phys. J. C 74, 2937 (2014). 5. R. Bluhm, V.A. Kostelecky´ and N. Russell, Phys. Rev. Lett. 82, 2254 (1999). 6. G.M. Shore, Nucl. Phys. B 717, 86 (2005). 7. M.M Ferreira Jr. and F.M.O. Moucherk, Nucl. Phys. A 790, 635c (2007). 8. V.A. Kostelecky´ and A.J. Vargas, Phys. Rev. D 92, 056002 (2015). 9. R. Bluhm, Nucl. Inst. Meth. Phys. Res. B 221, 6 (2004). 10. R. Bluhm, AIP Conf. Proc. 564, 101 (2001). 11. D. Colladay and P. McDonald, J. Math Phys. 43, 3554 (2002). 12. R. Bluhm, V.A. Kostelecky and N. Russell, [arXiv:hep- ph/0003223] (2000). 13. O.G. Kharlanov and V.Ch. Zhukovsky, J. Math. Phys. 48, 092302 (2007). 14. N. Russell, Phys. Scr. 72, C38 (2005). 15. H. Mu¨ller, S. Herrmann, A. Saenz and A. Peters, Phys. Rev D 70, 076004 (2004). 16. H. Belich, T. Costa-Soares, M.M. Ferreira Jr., J.A. Helay¨el-Neto and F.M.O. Moucherek, Phys. Rev. D 74, 065009 (2006). 17. Shan-quan Lan and F. Wu, Phys. Rev. D 87, 125022 (2013). 18. H. Mu¨ller, C. Braxmaier, S. Herrmann and A. Peters, Phys. Rev. D 67, 056006 (2003). 19. D.F. Phillips, M.A. Humphrey, E.M. Mattison, R.E. Stoner, R.F.C. Vessot and R. L. Walsworth, Phys. rev. D 63, 111101(R) (2001). 20. B.K. El-Menouﬁ and G. A. White, [arXiv:1505.01754] (2015). 21. T.J. Yoder and G.S. Adkins, Phys. Rev. D 86, 116005 (2012). 22. D. Colladay and V. Alan Kostelecky´, Phys Rev. D 58, 116002 (1998). 23. Nouredine Zettili, Quantum Mechanics: Concepts and Ap- plications, John Wiley & Sons, Chichester (2001). 24. Claude Cohen-Tannoudji, Bernard Diu, Frank Laloe, Quantum Mechanics, volume two, John Wiley & Sons, (1982). 25. J.J. Sakurai, Modern Quantum Mechanics, Addison- Wesley Publishing Company, Massachusetts (1994). 26. http:physics.net.gov 27. G.B. Arfken and H.J. Weber, Mathematical Methods for Physicists, Academic Press (1995). 28. J.D. Jackson, Classical Electrodynamics, 3a ed., John Wi- ley & Sons, Inc., New York (1999).

text: L.H.C.

label: author

text: Borges,

text: F.A.

text: Barone

text: Traces

label: title

text: of

text: Lorentz

text: symmetry

text: breaking

text: in

text: a

text: Hydrogen

text: atom

text: at

text: ground

text: state:

text: to

text: CNPq

text: for

text: ﬁnancial

text: support.

text: The

text: authors

text: would

text: like

text: to

text: thank

text: J.A.

text: Helay¨el-Neto

text: for

text: reading

text: the

text: paper.

text: References

label: reference

text: D.

text: Colladay

text: and

text: V.

text: Alan

text: Kostelecky´,

text: Phys.

text: Rev.

text: D

text: D.

text: Colladay

text: and

text: V.

text: Alan

text: Kostelecky´,

text: Phys

text: Rev.

text: D

text: A.

text: Kostelecky

text: and

text: N.

text: Russell,

text: Rev.

text: Mod.

text: Phys.

text: L.H.C.Borges,

text: F.

text: A.

text: Barone

text: and

text: J.A.

text: Helay¨el-Neto,

text: Eur.

text: Phys.

text: J.

text: C

text: R.

text: Bluhm,

text: V.A.

text: Kostelecky´

text: and

text: N.

text: Russell,

text: Phys.

text: Rev.

text: Lett.

text: G.M.

text: Shore,

text: Nucl.

text: Phys.

text: B

text: M.M

text: Ferreira

text: Jr.

text: and

text: F.M.O.

text: Moucherk,

text: Nucl.

text: Phys.

text: A

text: V.A.

text: Kostelecky´

text: and

text: A.J.

text: Vargas,

text: Phys.

text: Rev.

text: D

text: R.

text: Bluhm,

text: Nucl.

text: Inst.

text: Meth.

text: Phys.

text: Res.

text: B

text: R.

text: Bluhm,

text: AIP

text: Conf.

text: Proc.

text: D.

text: Colladay

text: and

text: P.

text: McDonald,

text: J.

text: Math

text: Phys.

text: R.

text: Bluhm,

text: V.A.

text: Kostelecky

text: and

text: N.

text: Russell,

text: [arXiv:hep-

text: O.G.

text: Kharlanov

text: and

text: V.Ch.

text: Zhukovsky,

text: J.

text: Math.

text: Phys.

text: N.

text: Russell,

text: Phys.

text: Scr.

text: H.

text: Mu¨ller,

text: S.

text: Herrmann,

text: A.

text: Saenz

text: and

text: A.

text: Peters,

text: Phys.

text: Rev

text: D

text: H.

text: Belich,

text: T.

text: Costa-Soares,

text: M.M.

text: Ferreira

text: Jr.,

text: J.A.

text: Helay¨el-Neto

text: and

text: F.M.O.

text: Moucherek,

text: Phys.

text: Rev.

text: D

text: Shan-quan

text: Lan

text: and

text: F.

text: Wu,

text: Phys.

text: Rev.

text: D

text: H.

text: Mu¨ller,

text: C.

text: Braxmaier,

text: S.

text: Herrmann

text: and

text: A.

text: Peters,

text: Phys.

text: Rev.

text: D

text: D.F.

text: Phillips,

text: M.A.

text: Humphrey,

text: E.M.

text: Mattison,

text: R.E.

text: Stoner,

text: R.F.C.

text: Vessot

text: and

text: R.

text: L.

text: Walsworth,

text: Phys.

text: rev.

text: D

text: B.K.

text: El-Menouﬁ

text: and

text: G.

text: A.

text: White,

text: T.J.

text: Yoder

text: and

text: G.S.

text: Adkins,

text: Phys.

text: Rev.

text: D

text: D.

text: Colladay

text: and

text: V.

text: Alan

text: Kostelecky´,

text: Phys

text: Rev.

text: D

text: Nouredine

text: Zettili,

text: Quantum

text: Mechanics:

text: Concepts

text: and

text: Ap-

text: plications,

text: John

text: Wiley

text: Sons,

text: Chichester

text: Claude

text: Cohen-Tannoudji,

text: Bernard

text: Diu,

text: Frank

text: Laloe,

text: Quantum

text: Mechanics,

text: volume

text: two,

text: John

text: Wiley

text: Sons,

text: J.J.

text: Sakurai,

text: Modern

text: Quantum

text: Mechanics,

text: Addison-

text: Wesley

text: Publishing

text: Company,

text: Massachusetts

text: http:physics.net.gov

text: G.B.

text: Arfken

text: and

text: H.J.

text: Weber,

text: Mathematical

text: Methods

text: for

text: Physicists,

text: Academic

text: Press

text: J.D.

text: Jackson,

text: Classical

text: Electrodynamics,

text: ed.,

text: John

text: Wi-

text: ley

text: Sons,

text: Inc.,

text: New

text: York


text: 2 TYLER HOFFMAN AND BENJAMIN STEINHURST Table 1. n f[2] f[3] n n 1 0 0 2 01 001 3 010 0010 4 01001 0010001 5 01001010 00100010010 we demonstrate the existence of the fractals and most importantly calculate the ≤ ≤ Hausdorﬀ dimension of any given i-Fibonacci fractal with drawing angle 0 α π 2 (Section ). The ﬁnal theorem of the paper will be the continuity of the fractal construction as a function of the drawing angle, Proposition 12 and Theorem 6. We thank Zachary Littrell for his aid in reviewing our code and Spencer Hamblen for his reoccurring timely assistance. McDaniel College kindly provided support for this project through a Student-Faculty Collaboration Grant. 2. Fibonacci Words (cid:48) The (classical) n th Fibonacci word is the word f deﬁned over the alphabet { } n 0, 1 that is generated by the concatenation rule f = f − f − with initial values n n 1 n 2 f = 1 and f = 0. Later we will discuss the inﬁnite word f. More information 0 1 on the sequence can be found in the On-line Encyclopedia of Integer Sequences for sequence number A003849 [6]. Since the ﬁrst F digits of f m > n are ﬁxed n m it is possible to deﬁne f∞ as the inﬁnite Fibonacci word. We however show the existence of f∞ metrically in Proposition 3. − The i Fibonacci word is constructed according the the same rules as a classical − − Fibonacci word however the initial values are f = 0 and f = 0i 11. We use 0i 1 − 1 2 − to represent a string of 0’s of length i 1. Table 1 lists the ﬁrst ﬁve i Fibonacci words for n = 2, the standard Fibonacci words, and n = 3. While concatenation is the basic construction technique for Fibonacci words we will deﬁne a substitution rule that will produce f[i] from f[i] as well. The n 1 main utility is that the application of a substitution rule is a local operation while concatenation is global operation. This perspective will be more useful in the discussion of the curves in the next section. It should be noted that while our Ξ[i] substitution is similar to the σ substitution used in [7], it is not the same. (cid:26) Deﬁnition 1. Deﬁne Ξ[i] to be the substitution rule: → − 0 0i 11 Ξ[i] : − → − 0i 11 0i 110 − over words comprised of blocks of the form 0 and 0i 11. − Since Ξ[i] transforms a sequence of blocks 0 and 0i 11 into another sequence of − blocks of 0 and 0i 11 the transformation can be iterated. − Proposition 1. Let f[i] be an i Fibonacci word then Ξ[i](f[i]) = f[i] . n n n+1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: TYLER

text: HOFFMAN

text: AND

text: BENJAMIN

text: STEINHURST

text: Table

text: n

label: table

text: n

text: n

text: we

text: demonstrate

text: the

text: existence

text: of

text: the

text: fractals

text: and

text: most

text: importantly

text: calculate

text: the

text: Hausdorﬀ

text: dimension

text: of

text: any

text: given

text: i-Fibonacci

text: fractal

text: with

text: drawing

text: angle

text: α

text: π

text: (Section

text: The

text: ﬁnal

text: theorem

text: of

text: the

text: paper

text: will

text: be

text: the

text: continuity

text: of

text: the

text: fractal

text: construction

text: as

text: a

text: function

text: of

text: the

text: drawing

text: angle,

text: Proposition

text: and

text: Theorem

text: We

text: thank

text: Zachary

text: Littrell

text: for

text: his

text: aid

text: in

text: reviewing

text: our

text: code

text: and

text: Spencer

text: Hamblen

text: for

text: his

text: reoccurring

text: timely

text: assistance.

text: McDaniel

text: College

text: kindly

text: provided

text: support

text: for

text: this

text: project

text: through

text: a

text: Student-Faculty

text: Collaboration

text: Grant.

text: Fibonacci

text: Words

text: The

text: (classical)

text: n

text: th

text: Fibonacci

text: word

text: is

text: the

text: word

text: f

text: deﬁned

text: over

text: the

text: alphabet

text: n

text: that

text: is

text: generated

text: by

text: the

text: concatenation

text: rule

text: f

text: f

text: f

text: with

text: initial

text: values

text: n

text: n

text: n

text: f

text: and

text: f

text: Later

text: we

text: will

text: discuss

text: the

text: inﬁnite

text: word

text: f.

text: More

text: information

text: on

text: the

text: sequence

text: can

text: be

text: found

text: in

text: the

text: On-line

text: Encyclopedia

text: of

text: Integer

text: Sequences

text: for

text: sequence

text: number

text: Since

text: the

text: ﬁrst

text: F

text: digits

text: of

text: f

text: m

text: n

text: are

text: ﬁxed

text: n

text: m

text: it

text: is

text: possible

text: to

text: deﬁne

text: f∞

text: as

text: the

text: inﬁnite

text: Fibonacci

text: word.

text: We

text: however

text: show

text: the

text: existence

text: of

text: f∞

text: metrically

text: in

text: Proposition

text: The

text: i

text: Fibonacci

text: word

text: is

text: constructed

text: according

text: the

text: the

text: same

text: rules

text: as

text: a

text: classical

text: Fibonacci

text: word

text: however

text: the

text: initial

text: values

text: are

text: f

text: and

text: f

text: We

text: use

text: to

text: represent

text: a

text: string

text: of

text: of

text: length

text: i

text: Table

text: lists

text: the

text: ﬁrst

text: ﬁve

text: i

text: Fibonacci

text: words

text: for

text: n

text: the

text: standard

text: Fibonacci

text: words,

text: and

text: n

text: While

text: concatenation

text: is

text: the

text: basic

text: construction

text: technique

text: for

text: Fibonacci

text: words

text: we

text: will

text: deﬁne

text: a

text: substitution

text: rule

text: that

text: will

text: produce

text: f[i]

text: from

text: f[i]

text: as

text: well.

text: The

text: n

text: main

text: utility

text: is

text: that

text: the

text: application

text: of

text: a

text: substitution

text: rule

text: is

text: a

text: local

text: operation

text: while

text: concatenation

text: is

text: global

text: operation.

text: This

text: perspective

text: will

text: be

text: more

text: useful

text: in

text: the

text: discussion

text: of

text: the

text: curves

text: in

text: the

text: next

text: section.

text: It

text: should

text: be

text: noted

text: that

text: while

text: our

text: Ξ[i]

text: substitution

text: is

text: similar

text: to

text: the

text: σ

text: substitution

text: used

text: in

text: it

text: is

text: not

text: the

text: same.

text: Deﬁnition

text: Deﬁne

text: Ξ[i]

text: to

text: be

text: the

text: substitution

text: rule:

text: Ξ[i]

text: over

text: words

text: comprised

text: of

text: blocks

text: of

text: the

text: form

text: and

text: Since

text: Ξ[i]

text: transforms

text: a

text: sequence

text: of

text: blocks

text: and

text: into

text: another

text: sequence

text: of

text: blocks

text: of

text: and

text: the

text: transformation

text: can

text: be

text: iterated.

text: Proposition

text: Let

text: f[i]

text: be

text: an

text: i

text: Fibonacci

text: word

text: then

text: Ξ[i](f[i])

text: f[i]

text: n

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: HAUSDORFF DIMENSION OF FIBONACCI FRACTALS 3 Since f[i] is unambiguous in how it is written as a single block of 0 we will always 1 assume that f[i] is broken down into these blocks in the way that it arises as the n output of this process. − Proof. We proceed by induction. Note that f[i] = 0 and Ξ[i](0) = 0i 11 = f[i]. 1 2 Similarly that Ξ[i](f[i]) = f[i] can be checked manually. Suppose the proposition − 1 − 2 holds for n 1 and n 2 and we will show it holds for n. Since Ξ[i] acts locally by replacing blocks and f = f − f − can be split into two sub-collections of blocks n n 1 n 2 the action of Ξ[i] can be split over f − and f − so that n 1 n 2 Ξ[i](f[i]) = Ξ[i](f[i−] f[i−] ) = Ξ[i](f[i−] )Ξ[i](f[i−] ) = f[i]f[i−] = f[i] . n n 1 n 2 n 1 n 2 n n 1 n+1 (cid:3) − The following properties of the i Fibonacci words will be useful later. They are cited here without proof. Proposition 2. [12, Proposition 5] The following properties hold for all i-Fibonacci words f[i]. n ≥ (1) The subword ”11” can never be found in an i-Fibonacci word with i 2. (2) The word f[i] can be decomposed as p ab where p is a palindrome and ab n n n depend on the parity of n only. (3) For even n, ab = 10 and for odd n, ab = 01 (4) The i-Fibonacci word has a ﬁve-partite structure f[i] = f[i−] f[i−] f[i−] l[i−] l[i−] , n n 3 n 3 n 6 n 3 n 3 where l[i] = p[i]ba (i.e. the last two letters are swapped). n n ≥ Proposition 3. The inﬁnite i-Fibonacci words exist for any given i 2 and are f[i] = lim →∞ f[i]. n n − Proof. The limit is taken in the sense of the standard 2 adic metric on the space − of ﬁnite and inﬁnite words. That is d (w, v) = 2 n where n is the number of initial 2 symbols that w and v share. By the deﬁnition of f[i] as concatenations, for each i n the sequence is Cauchy in this metric. Thus there is a limit word that is denoted (cid:3) f[i] It was mentioned earlier that the inﬁnite Fibonacci words could also be consid- ered as ﬁxed points of the concatenation rule. This metric proof of the existence is equivalent to that argument by the deﬁnition of the metric measuring distance between two words by measuring the length of the longest shared preﬁx of those two words.

text: HAUSDORFF

text: DIMENSION

text: OF

text: FIBONACCI

text: FRACTALS

text: Since

text: f[i]

text: is

text: unambiguous

text: in

text: how

text: it

text: is

text: written

text: as

text: a

text: single

text: block

text: of

text: we

text: will

text: always

text: assume

text: that

text: f[i]

text: is

text: broken

text: down

text: into

text: these

text: blocks

text: in

text: the

text: way

text: that

text: it

text: arises

text: as

text: the

text: n

text: output

text: of

text: this

text: process.

text: Proof.

text: We

text: proceed

text: by

text: induction.

text: Note

text: that

text: f[i]

text: and

text: f[i].

text: Similarly

text: that

text: Ξ[i](f[i])

text: f[i]

text: can

text: be

text: checked

text: manually.

text: Suppose

text: the

text: proposition

text: holds

text: for

text: n

text: and

text: n

text: and

text: we

text: will

text: show

text: it

text: holds

text: for

text: n.

text: Since

text: Ξ[i]

text: acts

text: locally

text: by

text: replacing

text: blocks

text: and

text: f

text: f

text: f

text: can

text: be

text: split

text: into

text: two

text: sub-collections

text: of

text: blocks

text: n

text: n

text: n

text: the

text: action

text: of

text: Ξ[i]

text: can

text: be

text: split

text: over

text: f

text: and

text: f

text: so

text: that

text: n

text: n

text: Ξ[i](f[i])

text: Ξ[i](f[i−]

text: f[i−]

text: Ξ[i](f[i−]

text: )Ξ[i](f[i−]

text: f[i]f[i−]

text: f[i]

text: n

text: n

text: n

text: n

text: n

text: n

text: n

text: The

text: following

text: properties

text: of

text: the

text: i

text: Fibonacci

text: words

text: will

text: be

text: useful

text: later.

text: They

text: are

text: cited

text: here

text: without

text: proof.

text: Proposition

text: Proposition

text: The

text: following

text: properties

text: hold

text: for

text: all

text: i-Fibonacci

text: words

text: f[i].

text: n

text: The

text: subword

text: ”11”

text: can

text: never

text: be

text: found

text: in

text: an

text: i-Fibonacci

text: word

text: with

text: i

text: The

text: word

text: f[i]

text: can

text: be

text: decomposed

text: as

text: p

text: ab

text: where

text: p

text: is

text: a

text: palindrome

text: and

text: ab

text: n

text: n

text: n

text: depend

text: on

text: the

text: parity

text: of

text: n

text: only.

text: For

text: even

text: n,

text: ab

text: and

text: for

text: odd

text: n,

text: ab

text: The

text: i-Fibonacci

text: word

text: has

text: a

text: ﬁve-partite

text: structure

text: f[i]

text: f[i−]

text: f[i−]

text: f[i−]

text: l[i−]

text: l[i−]

text: n

text: n

text: n

text: n

text: n

text: n

text: where

text: l[i]

text: p[i]ba

text: (i.e.

text: the

text: last

text: two

text: letters

text: are

text: swapped).

text: n

text: n

text: Proposition

text: The

text: inﬁnite

text: i-Fibonacci

text: words

text: exist

text: for

text: any

text: given

text: i

text: and

text: are

text: f[i]

text: lim

text: f[i].

text: n

text: n

text: Proof.

text: The

text: limit

text: is

text: taken

text: in

text: the

text: sense

text: of

text: the

text: standard

text: adic

text: metric

text: on

text: the

text: space

text: of

text: ﬁnite

text: and

text: inﬁnite

text: words.

text: That

text: is

text: d

text: (w,

text: v)

text: n

text: where

text: n

text: is

text: the

text: number

text: of

text: initial

text: symbols

text: that

text: w

text: and

text: v

text: share.

text: By

text: the

text: deﬁnition

text: of

text: f[i]

text: as

text: concatenations,

text: for

text: each

text: i

text: n

text: the

text: sequence

text: is

text: Cauchy

text: in

text: this

text: metric.

text: Thus

text: there

text: is

text: a

text: limit

text: word

text: that

text: is

text: denoted

text: f[i]

text: It

text: was

text: mentioned

text: earlier

text: that

text: the

text: inﬁnite

text: Fibonacci

text: words

text: could

text: also

text: be

text: consid-

text: ered

text: as

text: ﬁxed

text: points

text: of

text: the

text: concatenation

text: rule.

text: This

text: metric

text: proof

text: of

text: the

text: existence

text: is

text: equivalent

text: to

text: that

text: argument

text: by

text: the

text: deﬁnition

text: of

text: the

text: metric

text: measuring

text: distance

text: between

text: two

text: words

text: by

text: measuring

text: the

text: length

text: of

text: the

text: longest

text: shared

text: preﬁx

text: of

text: those

text: two

text: words.


text: HAUSDORFF DIMENSION OF FIBONACCI FRACTALS 5 Next we want a function that determines what the end behavior of any given subword is in terms of its angle. − Proposition 5. Let w be a word composed of the blocks 0 and 0i 11. Then a(w) = − ◦ ◦ a(Ξ[i] 3(w)). Furthermore, a(w) = a(Ξ[i] 6(w)). Proof. Consider the third substitution on each of two basic blocks: − − (Ξ[i])3(0) = 0i 1100i 11 − − − − (Ξ[i])3(0i 11) = 0i 1100i 110i 110. Thus we can see by processing the words according to the drawing rule that a(Ξ[i]◦3(0) = −a(0). Similarly a(Ξ[i]◦3(0i−11)) = −a(0i−11). By the additivity of the angle function over concatenation of words when Ξ[i] is applied another three ◦ times to the sign of the overall angle is again negated. Thus a(Ξ[i] 6(0)) = a(0) − (cid:3) and the same for 0i 11 as well. F From Table 3 it is clear that as n increases the curve [i] pass through several n global shapes. It is clear that their local structure is similar but for the global structure to be the same and for the orientation of the curve to be the same again it is necessary to consider only when n mod 6 = k. Notice that Proposition 5 gives another reason for considering every sixth curve as well. For purely historical reasons from [7] we consider k = 5 for even i. For odd i we consider k = 3 as it is visually the most similar. Equivalent analyses could be conducted for any choice (cid:16) (cid:17) (cid:16) (cid:17) of k. The following proposition is the ﬁrst that makes reference to this choice. − Proposition 6. When i is even a f[i] = α and when i is odd a f[i] = 0. 6k+5 (cid:16) (cid:17) 6k+3 (cid:16) (cid:17) − Proof. By Proposition 5 a(f[i]) = a(f[i] ). So a f[i] = a(f[i]) = α for even i n n+6 6k+5 5 (cid:3) and a f[i] = a(f[i]) = 0 for odd i. 6k+3 3 Finally, we verify that there exists no overlap between any two blocks of the ﬁve-partite structure for a later proof of Proposition 10. F Deﬁnition 3. The bounding box of a given curve [i] is the smallest rectangle n enclosing the curve. F Example 1. Refer to Figure 1 depicting [2] where the dotted red rectangle is the 11 bounding box formed by vertices A, B, C, and D. F F Proposition 7. Consider for even i [i] and for odd i [i] . Then the ﬁrst and 6k+5 6k+3 last vertices of these curves are co-located with two adjacent vertices of the bounding box.

text: HAUSDORFF

text: DIMENSION

text: OF

text: FIBONACCI

text: FRACTALS

text: Next

text: we

text: want

text: a

text: function

text: that

text: determines

text: what

text: the

text: end

text: behavior

text: of

text: any

text: given

text: subword

text: is

text: in

text: terms

text: of

text: its

text: angle.

text: Proposition

text: Let

text: w

text: be

text: a

text: word

text: composed

text: of

text: the

text: blocks

text: and

text: Then

text: a(w)

text: a(Ξ[i]

text: Furthermore,

text: a(w)

text: a(Ξ[i]

text: Proof.

text: Consider

text: the

text: third

text: substitution

text: on

text: each

text: of

text: two

text: basic

text: blocks:

text: Thus

text: we

text: can

text: see

text: by

text: processing

text: the

text: words

text: according

text: to

text: the

text: drawing

text: rule

text: that

text: Similarly

text: By

text: the

text: additivity

text: of

text: the

text: angle

text: function

text: over

text: concatenation

text: of

text: words

text: when

text: Ξ[i]

text: is

text: applied

text: another

text: three

text: times

text: to

text: the

text: sign

text: of

text: the

text: overall

text: angle

text: is

text: again

text: negated.

text: Thus

text: a(Ξ[i]

text: and

text: the

text: same

text: for

text: as

text: well.

text: F

text: From

text: Table

text: it

text: is

text: clear

text: that

text: as

text: n

text: increases

text: the

text: curve

text: [i]

text: pass

text: through

text: several

text: n

text: global

text: shapes.

text: It

text: is

text: clear

text: that

text: their

text: local

text: structure

text: is

text: similar

text: but

text: for

text: the

text: global

text: structure

text: to

text: be

text: the

text: same

text: and

text: for

text: the

text: orientation

text: of

text: the

text: curve

text: to

text: be

text: the

text: same

text: again

text: it

text: is

text: necessary

text: to

text: consider

text: only

text: when

text: n

text: mod

text: k.

text: Notice

text: that

text: Proposition

text: gives

text: another

text: reason

text: for

text: considering

text: every

text: sixth

text: curve

text: as

text: well.

text: For

text: purely

text: historical

text: reasons

text: from

text: we

text: consider

text: k

text: for

text: even

text: i.

text: For

text: odd

text: i

text: we

text: consider

text: k

text: as

text: it

text: is

text: visually

text: the

text: most

text: similar.

text: Equivalent

text: analyses

text: could

text: be

text: conducted

text: for

text: any

text: choice

text: of

text: k.

text: The

text: following

text: proposition

text: is

text: the

text: ﬁrst

text: that

text: makes

text: reference

text: to

text: this

text: choice.

text: Proposition

text: When

text: i

text: is

text: even

text: a

text: f[i]

text: α

text: and

text: when

text: i

text: is

text: odd

text: a

text: f[i]

text: Proof.

text: By

text: Proposition

text: a(f[i])

text: a(f[i]

text: So

text: a

text: f[i]

text: a(f[i])

text: α

text: for

text: even

text: i

text: n

text: and

text: a

text: f[i]

text: a(f[i])

text: for

text: odd

text: i.

text: Finally,

text: we

text: verify

text: that

text: there

text: exists

text: no

text: overlap

text: between

text: any

text: two

text: blocks

text: of

text: the

text: ﬁve-partite

text: structure

text: for

text: a

text: later

text: proof

text: of

text: Proposition

text: F

text: Deﬁnition

text: The

text: bounding

text: box

text: of

text: a

text: given

text: curve

text: [i]

text: is

text: the

text: smallest

text: rectangle

text: n

text: enclosing

text: the

text: curve.

text: F

text: Example

text: Refer

text: to

text: Figure

text: depicting

text: where

text: the

text: dotted

text: red

text: rectangle

text: is

text: the

text: bounding

text: box

text: formed

text: by

text: vertices

text: A,

text: B,

text: C,

text: and

text: D.

text: F

text: F

text: Proposition

text: Consider

text: for

text: even

text: i

text: [i]

text: and

text: for

text: odd

text: i

text: [i]

text: Then

text: the

text: ﬁrst

text: and

text: last

text: vertices

text: of

text: these

text: curves

text: are

text: co-located

text: with

text: two

text: adjacent

text: vertices

text: of

text: the

text: bounding

text: box.