text: A SKEW-PRODUCT WITHOUT FIXED-CURVES 57 2 (cid:0) (cid:1) Mk+1 Rω(θ) gk,θ I f (cid:0) (cid:1) m,θ k+1,Rω(θ) mk+1 Rω(θ) γ|i+1| (Rω(θ)) f − m 1,θ − 2− 2 λm(θ) IW τm(θ) 2 m,θ I mk(θ) k,θ (cid:0) Mk(θ) (cid:1) Figure 6. A symbolic representation of the maps f and f − ∈ ∗ \ m,θ∗ ∩ WmIB1,θ in Subcase 1.3 of Proposition 7.4 (θ B (i ) B (i ) ∗ ⊂ ∗ \{ ∗} i α|i| m and B (i ) B (k ) k ). The map f − and the corre- i α|kI| I m 1,θ sponding intervals and are drawn in blue. The map IWk,θ k+1,Rω(θ) f , the interval and the point γ (R (θ)) are drawn in m,θ m,θ |i+1| ω red. (cid:16) (cid:17) ∈ | | | | | | with (cid:96) = b (θ, led (θ, m)) WFD and (cid:96) > i > k . Then, by Lemma 3.6(g) and R ∗ ⊂ R ∗m\ (cid:20)(cid:20)(cid:20) ∗ Deﬁnition 6.2, ((cid:96) ) Int (k ) k and IW I ⊂ I = . m,θ (cid:96),θ k,θ ∈ ∗ ⊂ B Moreover, s(cid:0)ince θ (cid:1) Bα|k|(k ) m,≥Deﬁnition 7.2, Lemmas 4.3(b) and 4.5(b), and the deﬁnition of the maps g for i 0 (Deﬁnition 4.2) give (cid:40) i,θ IW ⊂ I f − f − ( ) m 1,θ m,θ m 1,θ k,θ I ≥ ∈ ∗ ⊂ if k < 0 or k 0 and θ B (k ) , {k+1,Rω(θ) } ≥ ∈ ∗ \ αk+1 ∗ γ (R (θ)) if k 0 and θ B [k ] B (k ). k+1 ω αk αk+1 (cid:107) − (cid:107) Now, as before, we≥will us(cid:13)(cid:13)e L∈em(cid:12) ma 9.∗5\to boun(cid:12)d∗ fm(cid:13)(cid:13),θ fm−1,θ . We start with the simplest case: k 0 and(cid:13)(cid:13) θ (cid:12)Bαk[k ] Bαk+1((cid:12)k ) . B(cid:13)(cid:13)y Lemma 10.1, (cid:107) − (cid:107) (cid:12) − (cid:12) fm,θ fm−1,θ = (cid:12) fm,θ IW fm−1,θ IW (cid:12) m,θ m,θ | | − ≤ − − = γ (R (θ)) γ (R (θ)) 2 b (θ,m 1) . |i+1| ω |k+1| ω ≥ ∈ ∗ Now we assume that k < 0 or k 0 and θ B (k ) . In this case Lemma 10.2 αk+1 applies. By Lemmas 10.2, 3.6(d) and Deﬁnition 3.4(R.2) and Remark 3.5(R.2), and ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A

text: SKEW-PRODUCT

text: WITHOUT

text: FIXED-CURVES

text: Rω(θ)

text: gk,θ

text: I

text: f

text: m,θ

text: Rω(θ)

text: (Rω(θ))

text: f

text: m

text: 2−

text: λm(θ)

text: IW

text: τm(θ)

text: m,θ

text: I

text: mk(θ)

text: k,θ

label: caption

text: Mk(θ)

text: Figure

text: A

text: symbolic

text: representation

text: of

text: the

text: maps

text: f

text: and

text: f

text: m,θ∗

text: in

text: Subcase

text: of

text: Proposition

text: (θ

text: B

text: (i

text: B

text: (i

text: i

text: α|i|

text: m

text: and

text: B

text: (i

text: B

text: (k

text: k

text: The

text: map

text: f

text: and

text: the

text: corre-

text: i

text: α|kI|

text: I

text: m

text: sponding

text: intervals

text: and

text: are

text: drawn

text: in

text: blue.

text: The

text: map

text: IWk,θ

text: f

text: the

text: interval

text: and

text: the

text: point

text: γ

text: (R

text: (θ))

text: are

text: drawn

text: in

text: m,θ

text: m,θ

text: ω

text: red.

text: with

text: b

text: (θ,

text: led

text: (θ,

text: m))

text: WFD

text: and

text: i

text: k

text: Then,

text: by

text: Lemma

text: and

text: R

text: R

text: ∗m\

text: Deﬁnition

text: Int

text: (k

text: k

text: and

text: IW

text: I

text: I

text: m,θ

text: k,θ

text: B

text: Moreover,

text: θ

text: Bα|k|(k

text: m,≥Deﬁnition

text: Lemmas

text: and

text: and

text: the

text: deﬁnition

text: of

text: the

text: maps

text: g

text: for

text: i

text: (Deﬁnition

text: give

text: i,θ

text: IW

text: I

text: f

text: f

text: m

text: m,θ

text: m

text: k,θ

text: I

text: if

text: k

text: or

text: k

text: and

text: θ

text: B

text: (k

text: γ

text: (R

text: (θ))

text: if

text: k

text: and

text: θ

text: B

text: [k

text: B

text: (k

text: ω

text: αk

text: Now,

text: as

text: before,

text: we≥will

text: ma

text: We

text: start

text: with

text: the

text: simplest

text: case:

text: k

text: θ

text: Lemma

text: fm,θ

text: fm,θ

text: IW

text: IW

text: m,θ

text: m,θ

text: γ

text: (R

text: (θ))

text: γ

text: (R

text: (θ))

text: b

text: (θ,m

text: ω

text: ω

text: Now

text: we

text: assume

text: that

text: k

text: or

text: k

text: and

text: θ

text: B

text: (k

text: In

text: this

text: case

text: Lemma

text: applies.

text: By

text: Lemmas

text: and

text: Deﬁnition

text: and

text: Remark

text: and

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 58 LL. ALSEDA`, F. MAN˜OSAS, AND L. MORALES 2 (cid:0) (cid:1) Mi+1 Rω(θ) g i,θ I (cid:0) (cid:1) fm−1,θ I i+1,Rω(θ) k+1,Rω(θ) mi+1 Rω(θ) γ|k+1| (Rω(θ)) f m,θ − 2− 2 2 I IW mi(θ) = λm−1(θ) i,θ = m−1,θ Mi(θ) = τm−1(θ) Figure 7. A symbolic representation of the maps f and f − ∈ ∗ ⊂ ∗ \ ∗ m,θ m 1,θ in Case 2 (θ B (i ) B (k ) B [k ]) of Proposition 7.4. α|i| k α|k| IW TI he map fm−1,θ and the corresponding intervals m−1,θ and are drawn in blue. The map f and the corresponding k+1,Rω(θ)I IW I m,θ intervals i,θ = m−1,θ and i+1,Rω(θ) are drawn in red. Lemma 9.5 we have ∈ I ⊂ I γ (R (θ)) , |i+1| ω ∈ Ii+1,Rω(θ) k+1,Rω(θ) ∈ IW f − (x) for every x . m 1,θ k+1,Rω(θ) m,θ and (cid:107) − (cid:107) | − | fm,θ fm−1,θ = sup (cid:12)(cid:12)fm,θ(x) fm−1,θ(x) (cid:12)(cid:12) ∈IW x m,θ − = sup γ (R (θ)) f − (x) ∈IW |i+1| ω m 1,θ x m,θ | | ≤ · −| | · − − 2 2 k = 2 2 b (θ,m 1) . This ends the proof of the proposition in this case. ∈ ∗ ⊂ ∗ \ ∗ Case 2. θ B (i ) B (k ) B [k ] (see Figure 7 for a symbolic representa- α|i| k α|k| tion (cid:12)of this case). (cid:12) (cid:12) (cid:12) I In this case we will use Lemma 9.5 with . Thus, we need to compare the maps i,θ fm,θ I and fm−1,θ I . i,θ i,θ ∗ ⊂ B ∗ ⊂ B Directly from the deﬁnitions we get k < 0, Bα|i|[i ] m and Bα|k|[k ] m−1. Consequently, by Lemma 5.2(b) and Deﬁnition 6.2, ∈ B ∈ B \B ⊂ WDB ⊂ WB θ m and θ m−1 m−1 m−1 m−1. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: LL.

text: ALSEDA`,

text: F.

text: MAN˜OSAS,

text: AND

text: L.

text: MORALES

text: Rω(θ)

text: g

text: i,θ

text: I

text: I

text: Rω(θ)

text: (Rω(θ))

text: f

text: m,θ

text: 2−

text: I

text: IW

text: mi(θ)

text: i,θ

text: Mi(θ)

text: Figure

text: A

text: symbolic

text: representation

text: of

text: the

text: maps

text: f

text: and

text: f

text: m,θ

text: m

text: in

text: Case

text: (θ

text: B

text: (i

text: B

text: (k

text: B

text: [k

text: of

text: Proposition

text: α|i|

text: k

text: α|k|

text: IW

text: TI

text: he

text: map

text: and

text: the

text: corresponding

text: intervals

text: and

text: are

text: drawn

text: in

text: blue.

text: The

text: map

text: f

text: and

text: the

text: corresponding

text: IW

text: I

text: m,θ

text: intervals

text: i,θ

text: and

text: are

text: drawn

text: in

text: red.

text: Lemma

text: we

text: have

text: I

text: I

text: γ

text: (R

text: (θ))

text: ω

text: IW

text: f

text: (x)

text: for

text: every

text: x

text: m

text: m,θ

text: and

text: fm,θ

text: sup

text: ∈IW

text: x

text: m,θ

text: sup

text: γ

text: (R

text: (θ))

text: f

text: (x)

text: ∈IW

text: ω

text: m

text: x

text: m,θ

text: k

text: b

text: (θ,m

text: This

text: ends

text: the

text: proof

text: of

text: the

text: proposition

text: in

text: this

text: case.

text: Case

text: θ

text: B

text: (i

text: B

text: (k

text: B

text: [k

text: (see

text: Figure

text: for

text: a

text: symbolic

text: representa-

text: α|i|

text: k

text: α|k|

text: tion

text: this

text: case).

text: I

text: In

text: this

text: case

text: we

text: will

text: use

text: Lemma

text: with

text: Thus,

text: we

text: need

text: to

text: compare

text: the

text: maps

text: i,θ

text: fm,θ

text: I

text: and

text: I

text: i,θ

text: i,θ

text: B

text: B

text: Directly

text: from

text: the

text: deﬁnitions

text: we

text: get

text: k

text: Bα|i|[i

text: m

text: and

text: Bα|k|[k

text: Consequently,

text: by

text: Lemma

text: and

text: Deﬁnition

text: B

text: B

text: \B

text: WDB

text: WB

text: θ

text: m

text: and

text: θ

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: On Explore-Then-Commit Strategies ∗ Aurélien Garivier Institut de Mathématiques de Toulouse; UMR5219 Université de Toulouse; CNRS UPS IMT, F-31062 Toulouse Cedex 9, France aurelien.garivier@math.univ-toulouse.fr Emilie Kaufmann Univ. Lille, CNRS, Centrale Lille, Inria SequeL UMR 9189, CRIStAL - Centre de Recherche en Informatique Signal et Automatique de Lille F-59000 Lille, France emilie.kaufmann@univ-lille1.fr Tor Lattimore University of Alberta 116 St & 85 Ave, Edmonton, AB T6G 2R3, Canada tor.lattimore@gmail.com Abstract We study the problem of minimising regret in two-armed bandit problems with Gaussian rewards. Our objective is to use this simple setting to illustrate that strategies based on an exploration phase (up to a stopping time) followed by exploitation are necessarily suboptimal. The results hold regardless of whether or not the difference in means between the two arms is known. Besides the main message, we also reﬁne existing deviation inequalities, which allow us to design fully sequential strategies with ﬁnite-time regret guarantees that are (a) asymptotically optimal as the horizon grows and (b) order-optimal in the minimax sense. Furthermore we provide empirical evidence that the theory also holds in practice and discuss extensions to non-gaussian and multiple-armed case. 1 Introduction It is now a very frequent issue for companies to optimise their daily proﬁts by choosing between one of two possible website layouts. A natural approach is to start with a period of A/B Testing (exploration) during which the two versions are uniformly presented to users. Once the testing is complete, the company displays the version believed to generate the most proﬁt for the rest of the month (exploitation). The time spent exploring may be chosen adaptively based on past observations, but could also be ﬁxed in advance. Our contribution is to show that strategies of this form are much worse than if the company is allowed to dynamically select which website to display without restrictions for the whole month. ∗ This work was partially supported by the CIMI (Centre International de Mathématiques et d’Informatique) Excellence program while Emilie Kaufmann visited Toulouse in November 2015. The authors acknowledge the support of the French Agence Nationale de la Recherche (ANR), under grants ANR-13-BS01-0005 (project SPADRO) and ANR-13-CORD-0020 (project ALICIA). 30th Conference on Neural Information Processing Systems (NIPS 2016), Barcelona, Spain. ##LTLine## ##LTLine##

text: On

label: title

text: Explore-Then-Commit

text: Strategies

label: author

text: Aurélien

text: Garivier

text: Institut

text: de

text: Mathématiques

text: de

text: Toulouse;

text: Université

text: de

text: Toulouse;

text: CNRS

text: UPS

text: IMT,

text: Toulouse

text: Cedex

text: France

text: aurelien.garivier@math.univ-toulouse.fr

font: XBLTAJ+NimbusMonL-Regu

text: Emilie

text: Kaufmann

text: Univ.

text: Lille,

text: CNRS,

text: Centrale

text: Lille,

text: Inria

text: SequeL

text: UMR

text: CRIStAL

text: Centre

text: de

text: Recherche

text: en

text: Informatique

text: Signal

text: et

text: Automatique

text: de

text: Lille

text: Lille,

text: France

text: Tor

text: Lattimore

text: University

text: of

text: Alberta

text: St

text: Ave,

text: Edmonton,

text: AB

text: Canada

text: tor.lattimore@gmail.com

text: Abstract

text: We

label: abstract

text: study

text: the

text: problem

text: of

text: minimising

text: regret

text: in

text: two-armed

text: bandit

text: problems

text: with

text: Gaussian

text: rewards.

text: Our

text: objective

text: is

text: to

text: use

text: this

text: simple

text: setting

text: to

text: illustrate

text: that

text: strategies

text: based

text: on

text: an

text: exploration

text: phase

text: (up

text: to

text: a

text: stopping

text: time)

text: followed

text: by

text: exploitation

text: are

text: necessarily

text: suboptimal.

text: The

text: results

text: hold

text: regardless

text: of

text: whether

text: or

text: not

text: the

text: difference

text: in

text: means

text: between

text: the

text: two

text: arms

text: is

text: known.

text: Besides

text: the

text: main

text: message,

text: we

text: also

text: reﬁne

text: existing

text: deviation

text: inequalities,

text: which

text: allow

text: us

text: to

text: design

text: fully

text: sequential

text: strategies

text: with

text: ﬁnite-time

text: regret

text: guarantees

text: that

text: are

text: (a)

text: asymptotically

text: optimal

text: as

text: the

text: horizon

text: grows

text: and

text: (b)

text: order-optimal

text: in

text: the

text: minimax

text: sense.

text: Furthermore

text: we

text: provide

text: empirical

text: evidence

text: that

text: the

text: theory

text: also

text: holds

text: in

text: practice

text: and

text: discuss

text: extensions

text: to

text: non-gaussian

text: and

text: multiple-armed

text: case.

text: Introduction

text: It

text: is

text: now

text: a

text: very

text: frequent

text: issue

text: for

text: companies

text: to

text: optimise

text: their

text: daily

text: proﬁts

text: by

text: choosing

text: between

text: one

text: of

text: two

text: possible

text: website

text: layouts.

text: A

text: natural

text: approach

text: is

text: to

text: start

text: with

text: a

text: period

text: of

text: A/B

text: Testing

text: (exploration)

text: during

text: which

text: the

text: two

text: versions

text: are

text: uniformly

text: presented

text: to

text: users.

text: Once

text: the

text: testing

text: is

text: complete,

text: the

text: company

text: displays

text: the

text: version

text: believed

text: to

text: generate

text: the

text: most

text: proﬁt

text: for

text: the

text: rest

text: of

text: the

text: month

text: (exploitation).

text: The

text: time

text: spent

text: exploring

text: may

text: be

text: chosen

text: adaptively

text: based

text: on

text: past

text: observations,

text: but

text: could

text: also

text: be

text: ﬁxed

text: in

text: advance.

text: Our

text: contribution

text: is

text: to

text: show

text: that

text: strategies

text: of

text: this

text: form

text: are

text: much

text: worse

text: than

text: if

text: the

text: company

text: is

text: allowed

text: to

text: dynamically

text: select

text: which

text: website

text: to

text: display

text: without

text: restrictions

text: for

text: the

text: whole

text: month.

text: This

text: work

text: was

text: partially

text: supported

text: by

text: the

text: CIMI

text: (Centre

text: International

text: de

text: Mathématiques

text: et

text: d’Informatique)

text: Excellence

text: program

text: while

text: Emilie

text: Kaufmann

text: visited

text: Toulouse

text: in

text: November

text: The

text: authors

text: acknowledge

text: the

text: support

text: of

text: the

text: French

text: Agence

text: Nationale

text: de

text: la

text: Recherche

text: (ANR),

text: under

text: grants

text: (project

text: SPADRO)

text: and

text: (project

text: ALICIA).

text: Conference

text: on

text: Neural

text: Information

text: Processing

text: Systems

text: (NIPS

text: Barcelona,

text: Spain.

text: ##LTLine##

text: ##LTLine##


text: (cid:32) (cid:115) (cid:18) (cid:19) (cid:33) (cid:112)≥ For the second term we apply Lemma 1.(c) to obtain, whenever Tε2 e2, P ∃ ≤ 2 T ≤ − ≤ 30e log(ε2T) 16e T s T : µˆ + log µ ε + . µ 1,s s s 1 ε2 ε2 − ≥ ≥ Finally, if T(∆ ε)2 2(cid:114)and Tε2 e2, RUCB(T)(cid:16)≤ ∆E [N(cid:17)(T)] (cid:16) (cid:17) (cid:32) (cid:112) (cid:33) µ µ 2 ≤ 2 log T(∆2−ε)2 2 π log T(∆2−ε)2 2 30e log(ε2T) 16e − + − + − + ∆ + ∆ + ∆ (1 ε/∆)2 ∆ (1 ε/∆)2 ∆ (1 ε/∆)2 ε2 ε2 − The asymptotic result follows by taking the limit as T tends to inﬁnity and choosing ε = log 18 (T) while the minimax result follows by ﬁnding the minimum of the ﬁnite-time bound given above and ≤ the naive RUCB(T) T∆. µ G Deviation Inequalities As was already the case in the proof of Theo(cid:26)rem 1, we(cid:27)heavily rely on the following well-known ∼ N (cid:0) (cid:1) inequality on the tail of a Gaussian distribution: if X (0, 1), then for all x > 0 P ≥ ≤ √1 − (X x) min 1, exp x2/2 . x 2π Lemma 1 gathers some more speciﬁc results that are useful in our regret analyses, and that we believe to be o(cid:80)f a certain interest on their own. Lemma(cid:20)1. Le(cid:26)t ε > 0 and ∆ > (cid:27)0 (cid:21)and W , W , . . . be standard i.i.d. Gaussian random variables and 1 2 µˆ = t W /t. Then the following hold: t s=1 s (a). E min t : sup |µˆ | ≥ ε(cid:32) ≤ 1(cid:115)+ 9/ε2(cid:18) (cid:19) (cid:33) (cid:16) (cid:17) (cid:113) (cid:0) (cid:1) ≥ (cid:88)s s t (b). if T∆2 ≥ 2 then T(cid:32) P µˆ + 2 (cid:115)log T (cid:18)≥(cid:19)∆ ≤ 2 lo(cid:33)g T∆2 2 (cid:112)+ 2 π log T∆2 2 + 2 + 1 n n n ∆2 ∆2 ∆2 n=1 ≥ P ∃ ≤ 2 T ≤ ≤ 30e log(ε2T) 16e (c). if Tε2 e2 then s T : µˆ + log + ε 0 + s s s ε2T ε2T The proof of Lemma 1 follows from standard peeling techniques and inequalities for Gaussian sums of random variables. So far we do not know if this statement holds for subgaussian random variables where slightly weaker results may be shown by adding log log terms to the conﬁdence interval, but unfortunately by doing this one sacriﬁces minimax optimality. (cid:88) Proof of Lemma 1.(a). We use a standard peeling argument and the maximal inequality. ∞ P ∃ ≥ | | ≥ ≤ P ∃ ∈ | | ≥ ( s t : µˆ ε) (cid:88) ( s [kt, (k + 1)t] : µˆ ε) s s k=1 ∞ ≤ P ∃ (cid:18)≤ |(cid:19) | ≥ (cid:18) (cid:19) (cid:88) ( s (k + 1)t : sµˆ (cid:88)ktε) s k=1 ∞ ∞ ≤ (cid:18)− (kt(cid:19)ε)2 − ktε2 (cid:88) 2 exp = 2 exp 2(k + 1)t 2 (1 + 1/k) k=1 k=1 ∞ ≤ −ktε2 2 exp 4 k=1 17 ##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: For

text: the

text: second

text: term

text: we

text: apply

text: Lemma

text: to

text: obtain,

text: whenever

text: P

text: T

text: T

text: s

text: T

text: µˆ

text: log

text: µ

text: ε

text: µ

text: s

text: s

text: ε2

text: ε2

text: Finally,

text: if

text: T(∆

text: ∆E

text: µ

text: µ

text: log

text: π

text: log

text: ε2

text: ε2

text: The

text: asymptotic

text: result

text: follows

text: by

text: taking

text: the

text: limit

text: as

text: T

text: tends

text: to

text: inﬁnity

text: and

text: choosing

text: ε

text: log

text: (T)

text: while

text: the

text: minimax

text: result

text: follows

text: by

text: ﬁnding

text: the

text: minimum

text: of

text: the

text: ﬁnite-time

text: bound

text: given

text: above

text: and

text: the

text: naive

text: RUCB(T)

text: T∆.

text: µ

text: G

text: Deviation

text: Inequalities

text: As

text: was

text: already

text: the

text: case

text: in

text: the

text: proof

text: of

text: rely

text: on

text: the

text: following

text: well-known

text: N

text: inequality

text: on

text: the

text: tail

text: of

text: a

text: Gaussian

text: distribution:

text: if

text: X

text: then

text: for

text: all

text: x

text: P

text: √1

text: (X

text: x)

text: min

text: exp

text: x

text: 2π

text: Lemma

text: gathers

text: some

text: more

text: speciﬁc

text: results

text: that

text: are

text: useful

text: in

text: our

text: regret

text: analyses,

text: and

text: that

text: we

text: believe

text: to

text: be

text: a

text: certain

text: interest

text: on

text: their

text: own.

text: ε

text: and

text: W

text: W

text: be

text: standard

text: i.i.d.

text: Gaussian

text: random

text: variables

text: and

text: µˆ

text: t

text: W

text: /t.

text: Then

text: the

text: following

text: hold:

text: t

text: s

text: (a).

text: E

text: min

text: t

text: sup

text: |µˆ

text: s

text: t

text: (b).

text: if

text: then

text: P

text: µˆ

text: T

text: π

text: log

text: n

text: n

text: n

text: ∆2

text: ∆2

text: ∆2

text: P

text: T

text: (c).

text: if

text: then

text: s

text: T

text: µˆ

text: log

text: ε

text: s

text: s

text: s

text: The

text: proof

text: of

text: Lemma

text: follows

text: from

text: standard

text: peeling

text: techniques

text: and

text: inequalities

text: for

text: Gaussian

text: sums

text: of

text: random

text: variables.

text: So

text: far

text: we

text: do

text: not

text: know

text: if

text: this

text: statement

text: holds

text: for

text: subgaussian

text: random

text: variables

text: where

text: slightly

text: weaker

text: results

text: may

text: be

text: shown

text: by

text: adding

text: log

text: log

text: terms

text: to

text: the

text: conﬁdence

text: interval,

text: but

text: unfortunately

text: by

text: doing

text: this

text: one

text: sacriﬁces

text: minimax

text: optimality.

text: Proof

text: of

text: Lemma

text: We

text: use

text: a

text: standard

text: peeling

text: argument

text: and

text: the

text: maximal

text: inequality.

text: P

text: P

text: s

text: t

text: µˆ

text: ε)

text: s

text: [kt,

text: (k

text: µˆ

text: ε)

text: s

text: s

text: P

text: s

text: (k

text: sµˆ

text: s

text: exp

text: exp

text: exp

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: (cid:40) (cid:18) (cid:19)(cid:41) (cid:88) (cid:88) (cid:88) Therefore ∞ ∞ ∞ E ≤ P (cid:26)≥ ≤ (cid:27) (cid:90) −k(cid:26)tε2 (cid:27) [τ] 1 + (cid:88) (τ t) 1 + min 1, 2 exp 4 t=1 t=1 k=1 ∞ ∞ (cid:90) 2 ≤ 2 = 1 + min 1, − 1 + min 1, − dt exp (tε2/4) 1 exp (tε2/4) 1 t=1 ∞ 0 ≤ 4 log(4) 8 4 log(4) 8 ≤ 9 1 + + dt = 1 + + 1 + . ε2 3 exp (tε2/4) ε2 3ε2 ε2 4/ε2 log(4) (cid:112) (cid:0) (cid:1) Proof of Lemm(cid:32)a 1.(b).(cid:115)Let ν b(cid:18)e the(cid:19)solutio(cid:33)n of 2 log(T/n)(cid:32)/n = ∆, that(cid:115)is ν = 2(cid:18)W (cid:19)∆(cid:33)2T/2 /∆2. (cid:88) (cid:88) Then T P 2 T ≥ ≤ T P ≥ − 2 T µˆ + log ∆ ν + µˆ ∆ log . n n n (cid:18) (cid:19)(cid:100) (cid:101) n n n n=1 n= ν ≥ As for all n ν 2 T ≤ 2 T ν ν log log = ∆2 , (cid:32) n (cid:115) n (cid:18)ν (cid:19)(cid:33) ν n (cid:18) n (cid:18) (cid:114) (cid:19)(cid:19) (cid:88) (cid:88) ∞ T P µˆ ≥ ∆ −(cid:32) 2 log(cid:18) T (cid:114) ≤(cid:19) (cid:33) P µˆ ≥ ∆ 1 − ν (cid:100) (cid:101) (cid:88)n n n (cid:100) (cid:101) n n n= ν n= ν ∞ ≤ −n∆2 − ν 2 (cid:88)(cid:100) (cid:101) exp (cid:18) 2 (cid:0) 1 n(cid:1) (cid:19) n= ν ∞ √ √ −∆2 − = (cid:90) exp (cid:18) (cid:0)n ν 2 (cid:1) (cid:19) (cid:100) (cid:101) 2 n= ν ∞ √ √ ≤ (cid:90) (cid:16) −∆2 (cid:17) − (cid:18) 2 (cid:19) 1 + exp x ν dx 2 ν ∞ √ 2 y −y2 = 1 + + ν exp dy ∆ √ ∆ 2 0 2 2πν = 1 + + . ∆2 ∆ (cid:88) (cid:32)≤ (cid:115) (cid:18) (cid:19) (cid:33) (cid:32) ≥ (cid:18) (cid:19) (cid:115) (cid:18) (cid:19)(cid:33) Hence, as ν 2 log(∆2T/2)/∆2 whenever T∆2 2, T P 2 T ≥ ≤ 2 T∆2 T∆2 µˆ + log ∆ log + 1 + π log + 1 . n n n ∆2 2 2 n=1 ∈ N Proof of Lemma 1.(c). Let x > 0 and n , then by the reﬂection principle (eg., Mörters and Peres [2010]) it holds that (cid:26) (cid:114) (cid:27) (cid:18) (cid:19) P ∃ ≤ ≤ P ≤ ≤ 1 n − x2 ( s n : sµˆ + x 0) = 2 (nµˆ + x 0) 2 min , 1 exp (7) s n x 2π 2n We prepare to use the peeling technique with a carefully chosen grid. Let log(ε2T) η = − and G = [ηk, ηk+1[ . log(ε2T) 1 k 18 ##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## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Therefore

text: E

text: P

text: [τ]

text: (τ

text: t)

text: min

text: exp

text: min

text: min

text: dt

text: exp

text: exp

text: dt

text: ε2

text: exp

text: ε2

text: ε2

text: Proof

text: of

text: ν

text: of

text: ν

text: Then

text: T

text: P

text: T

text: T

text: P

text: T

text: µˆ

text: log

text: ν

text: µˆ

text: log

text: n

text: n

text: n

text: n

text: n

text: n

text: n=

text: ν

text: As

text: for

text: all

text: n

text: ν

text: T

text: T

text: ν

text: ν

text: log

text: log

text: ∆2

text: n

text: n

text: ν

text: n

text: n

text: T

text: P

text: µˆ

text: T

text: P

text: µˆ

text: ν

text: n

text: n

text: n

text: n

text: n=

text: ν

text: n=

text: ν

text: −n∆2

text: ν

text: exp

text: n=

text: ν

text: −∆2

text: exp

text: ν

text: n=

text: ν

text: −∆2

text: exp

text: x

text: ν

text: dx

text: ν

text: y

text: ν

text: exp

text: dy

text: 2πν

text: ∆2

text: Hence,

text: as

text: ν

text: whenever

text: T

text: P

text: T

text: µˆ

text: log

text: log

text: π

text: log

text: n

text: n

text: n

text: ∆2

text: N

text: Proof

text: of

text: Lemma

text: Let

text: x

text: and

text: n

text: then

text: by

text: the

text: reﬂection

text: principle

text: (eg.,

text: Mörters

text: and

text: Peres

text: it

text: holds

text: that

text: P

text: P

text: n

text: s

text: n

text: sµˆ

text: x

text: (nµˆ

text: x

text: min

text: exp

text: s

text: n

text: x

text: 2π

text: We

text: prepare

text: to

text: use

text: the

text: peeling

text: technique

text: with

text: a

text: carefully

text: chosen

text: grid.

text: Let

text: η

text: and

text: G

text: [ηk,

text: k

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: ##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: − ≥ ≥ Tbohuenodreedma7s. If T(2∆ 3εT )2 2(cid:0) and T(cid:1)ε2T e2,(cid:112)the regret of the ∆-UCB algorithm is upper ≤ log(cid:34) 2T(cid:112)∆2 π log (2T∆2) (cid:35) R∆-UCB(T) − + − µ 2∆(1 3ε /(2∆))2 2∆(1 3ε /∆)2 T T 30e log(ε2 T) 80 2 + ∆ T + + − + 5∆. ε2 ε2 (2∆ 3ε )2 T T T √ ≤ − ∀ ∈ H ≤ Moreover lim sup →∞ R∆-UCB(T)/ log(T) (2∆) 1 and µ , R∆-UCB(T) 328 T + 5∆. T µ ∆ µ The proof may be found in Appendix . Unknown Gaps. In the classical bandit setting where ∆ is unknown, UCB by Katehakis and Robbins ∼ [1995] is known to be asymptotically optimal: RUCB(T) 2 log(T)/∆, which matches the lower µ bound of Lai and Robbins [1985]. Non-asymptotic regret bounds are given for example by Auer et al. [2002], Cappé et al. [2013]. Unfortunately, UCB is not optimal in the minimax sense, which is so far only achieved by algorithms that are not asymptotically optimal [Audibert and Bubeck, 2009, Lattimore, 2015]. Here, with only two arms, we are able to show that Algorithm 5 below is simultaneously minimax order-optimal and asymptotically optimal. The strategy is essentially the same as suggested by Lai [1987], but with a fractionally smaller conﬁdence bound. The proof of ∗ Theorem 8 is given in Appendix . Empirically the smaller conﬁdence bonus used by UCB leads to a signiﬁcant improvement relative to UCB. (cid:115) 1: input: T (cid:18) (cid:19) ∈ { } 2: for t 1, . . . , T do − 2 T 3: A = arg max µˆ (t 1) + − log − t ∈{ } i N (t 1) N (t 1) i 1,2 i i 4: end for ∗ Algorithm 5: UCB ∈ − ≥ ≥ ∗ Theorem 8. For all ε (0, ∆), if T(∆ ε)2 2 and Tε2 e2, the regret of the UCB strategy is upper bounded as (cid:16) (cid:17) (cid:113) (cid:0) (cid:1) (cid:32) (cid:112) (cid:33) (cid:0) (cid:1) (cid:0) (cid:1) (cid:0) (cid:1) RµUCB∗(T) ≤ 2∆log1 −T∆2ε 2 2 + 2 ∆π 1lo−g εT∆222 + ∆ 30e log(εε22T) + 16e + ∆ 1 −2 ε 2 + ∆. ∆ ∆ ∆ √ ∈ H ≤ Moreover, lim sup →∞ Rπ(T)/ log(T) = 2/∆ and for all µ , Rπ(T) 33 T + ∆. T (cid:112) µ (cid:112) µ Note that if there are K > 2 arms, then the strategy above is still asymptotically optimal, but suffers a minimax regret of Ω( TK log(K)), which is a factor of log(K) suboptimal. 5 Numerical Experiments We represent here the regret of the ﬁve strategies presented in this article on a bandit problem with ∆ = 1/5, for different values of the horizon. The regret is estimated by 4.105 Monte-Carlo replications. In the legend, the estimated slopes of ∆Rπ(T) (in logarithmic scale) are indicated after the policy names. 7 ##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: If

text: and

text: regret

text: of

text: the

text: ∆-UCB

text: algorithm

text: is

text: upper

text: π

text: log

text: R∆-UCB(T)

text: µ

text: 3ε

text: 3ε

text: T

text: T

text: T)

text: T

text: ε2

text: ε2

text: 3ε

text: T

text: T

text: T

text: H

text: Moreover

text: lim

text: sup

text: R∆-UCB(T)/

text: log(T)

text: and

text: µ

text: R∆-UCB(T)

text: T

text: T

text: µ

text: µ

text: The

text: proof

text: may

text: be

text: found

text: in

text: Appendix

text: Unknown

text: Gaps.

text: In

text: the

text: classical

text: bandit

text: setting

text: where

text: is

text: unknown,

text: UCB

text: by

text: Katehakis

text: and

text: Robbins

text: is

text: known

text: to

text: be

text: asymptotically

text: optimal:

text: RUCB(T)

text: log(T)/∆,

text: which

text: matches

text: the

text: lower

text: µ

text: bound

text: of

text: Lai

text: and

text: Robbins

text: Non-asymptotic

text: regret

text: bounds

text: are

text: given

text: for

text: example

text: by

text: Auer

text: et

text: al.

text: Cappé

text: et

text: al.

text: Unfortunately,

text: UCB

text: is

text: not

text: optimal

text: in

text: the

text: minimax

text: sense,

text: which

text: is

text: so

text: far

text: only

text: achieved

text: by

text: algorithms

text: that

text: are

text: not

text: asymptotically

text: optimal

text: [Audibert

text: and

text: Bubeck,

text: Lattimore,

text: Here,

text: with

text: only

text: two

text: arms,

text: we

text: are

text: able

text: to

text: show

text: that

text: Algorithm

text: below

text: is

text: simultaneously

text: minimax

text: order-optimal

text: and

text: asymptotically

text: optimal.

text: The

text: strategy

text: is

text: essentially

text: the

text: same

text: as

text: suggested

text: by

text: Lai

text: but

text: with

text: a

text: fractionally

text: smaller

text: conﬁdence

text: bound.

text: The

text: proof

text: of

text: Theorem

text: is

text: given

text: in

text: Appendix

text: Empirically

text: the

text: smaller

text: conﬁdence

text: bonus

text: used

text: by

text: UCB

text: leads

text: to

text: a

text: signiﬁcant

text: improvement

text: relative

text: to

text: UCB.

text: input:

text: T

text: for

text: t

text: T

text: do

text: T

text: A

text: arg

text: max

text: µˆ

text: (t

text: log

text: t

text: i

text: N

text: (t

text: N

text: (t

text: i

text: i

text: i

text: end

text: for

text: Algorithm

text: UCB

text: Theorem

text: For

text: all

text: ε

text: if

text: T(∆

text: and

text: the

text: regret

text: of

text: the

text: UCB

text: strategy

text: is

text: upper

text: bounded

text: as

text: RµUCB∗(T)

text: −T∆2ε

text: ∆π

text: −2

text: ε

text: H

text: Moreover,

text: lim

text: sup

text: Rπ(T)/

text: log(T)

text: and

text: for

text: all

text: µ

text: Rπ(T)

text: T

text: T

text: µ

text: µ

text: Note

text: that

text: if

text: there

text: are

text: K

text: arms,

text: then

text: the

text: strategy

text: above

text: is

text: still

text: asymptotically

text: optimal,

text: but

text: suffers

text: a

text: minimax

text: regret

text: of

text: Ω(

text: TK

text: log(K)),

text: which

text: is

text: a

text: factor

text: of

text: log(K)

text: suboptimal.

text: Numerical

text: Experiments

text: We

text: represent

text: here

text: the

text: regret

text: of

text: the

text: ﬁve

text: strategies

text: presented

text: in

text: this

text: article

text: on

text: a

text: bandit

text: problem

text: with

text: for

text: different

text: values

text: of

text: the

text: horizon.

text: The

text: regret

text: is

text: estimated

text: by

text: Monte-Carlo

text: replications.

text: In

text: the

text: legend,

text: the

text: estimated

text: slopes

text: of

text: ∆Rπ(T)

text: (in

text: logarithmic

text: scale)

text: are

text: indicated

text: after

text: the

text: policy

text: names.

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: 11 ∞ ∩ ∩ It follows that ν ,x(A B) = 1 and hence A B is not empty. Now, by ∈ ∈ deﬁnition, we ﬁnd a sequence (x ) ∈N E and (y ) ∈N E with the property ≤ ≤ i i X ∈ Ni i Y that r (x , x ) r r (y , y ) for all i, j . Fix these two sequences. X i j {ij ∈YN}i →j (cid:55)→ Deﬁne the map τ˜ : y : i X, y x , then τ˜ is a sub-isometry deﬁned i i i → on a dense subset of Y and therefore extends to a sub-isometry τ : Y X. Finall(cid:90)y observe that by(cid:90)deﬁnition of the sequences (x ) ∈N and (y ) ∈N: (cid:88) i i i i ◦ − ◦ 1 n f dµY τ 1 = f τd(cid:88)µY = nl→im∞(cid:90)n f(τ(yi)) i=1 (4.10) n 1 = lim f(x ) = f dµ . n→∞ n i X i=1 ∈ ◦ − for all functions f C (X), i.e. µ τ 1 = µ and therefore τ is a measure- b Y X preserving sub-isometry as required. As a direct consequence of Theorem 4.4, we can deduce the following known statement (see 3.1.15 (a) and (b) in [14]). 2 ≤ Proposition 4.6. The relation of Deﬁnition 3.3 is a closed partial order M metric on . 1 Proof. This proof follows directly from Proposition 4.4: While the reﬂexivity and transitivity are obvious, the antisymmetry follows by the fact that Φ(x) = ∈ Φ(y) for all increasing Φ Π implies x = y. This follows since the algebra + generated by increasing Φ is dense in the set of all polynomials and this suﬃces to deduce x = y (see Proposition 2.6 in [11]). The closedness follows since the monomials generate the Gromov-weak topol- ogy. One may think that for “small” spaces (with few points) one only needs to look at low order polynomials. The next example shows that this is not the case. Nevertheless we think that the characterization result, Theorem 4.4, might be ≤ helpful algorithmically to determine whether x y holds. metric { } Example 4.7. We consider x = ( a, b , r(a, b) = 1, (δ + δ )/2) and y = { } a b ( c, d, e , r(c, d) = 1, r(c, e) = r(d, e) = 2, (δ + δ + δ )/3). Then, on the c d e one hand, one can not ﬁnd a measure preserving sub-isometry but on the other hand it is not obvious that the distance matrix distributions do not dominate each other. In particular one needs to consider the distance matrix distribution (cid:54)≤ of order m= 10 to see that νm,x νm,y: If we look at the sequence of points   (cid:124) (cid:123)(cid:122) (cid:125) (cid:124) (cid:123)(cid:122) (cid:125) x := a, . . . , a, b, . . . , b (4.11) m m and den(cid:32)oteąby R := Rm,x((cid:33)x) the corresponding distance matrix, then ∞ 2 νm,x [R , ) = . (4.12) ≤ ≤ i,j 22m 1 i<j m ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: It

text: follows

text: that

text: ν

text: ,x(A

text: B)

text: and

text: hence

text: A

text: B

text: is

text: not

text: empty.

text: Now,

text: by

text: deﬁnition,

text: we

text: ﬁnd

text: a

text: sequence

text: (x

text: ∈N

text: E

text: and

text: (y

text: ∈N

text: E

text: with

text: the

text: property

text: i

text: i

text: X

text: Ni

text: i

text: Y

text: that

text: r

text: (x

text: x

text: r

text: r

text: (y

text: y

text: for

text: all

text: i,

text: j

text: Fix

text: these

text: two

text: sequences.

text: X

text: i

text: j

text: {ij

text: ∈YN}i

text: →j

text: Deﬁne

text: the

text: map

text: τ˜

text: y

text: i

text: X,

text: y

text: x

text: then

text: τ˜

text: is

text: a

text: sub-isometry

text: deﬁned

text: i

text: i

text: i

text: on

text: a

text: dense

text: subset

text: of

text: Y

text: and

text: therefore

text: extends

text: to

text: a

text: sub-isometry

text: τ

text: Y

text: X.

text: observe

text: that

text: of

text: the

text: sequences

text: (x

text: ∈N

text: and

text: (y

text: ∈N:

text: i

text: i

text: i

text: i

text: n

text: f

text: dµY

text: τ

text: f

text: f(τ(yi))

text: n

text: lim

text: f(x

text: f

text: dµ

text: n→∞

text: n

text: i

text: X

text: for

text: all

text: functions

text: f

text: C

text: (X),

text: i.e.

text: µ

text: τ

text: µ

text: and

text: therefore

text: τ

text: is

text: a

text: measure-

text: b

text: Y

text: X

text: preserving

text: sub-isometry

text: as

text: required.

text: As

text: a

text: direct

text: consequence

text: of

text: Theorem

text: we

text: can

text: deduce

text: the

text: following

text: known

text: statement

text: (see

text: (a)

text: and

text: (b)

text: in

text: Proposition

text: The

text: relation

text: of

text: Deﬁnition

text: is

text: a

text: closed

text: partial

text: order

text: M

text: metric

text: on

text: Proof.

text: This

text: proof

text: follows

text: directly

text: from

text: Proposition

text: While

text: the

text: reﬂexivity

text: and

text: transitivity

text: are

text: obvious,

text: the

text: antisymmetry

text: follows

text: by

text: the

text: fact

text: that

text: Φ(x)

text: Φ(y)

text: for

text: all

text: increasing

text: Φ

text: Π

text: implies

text: x

text: y.

text: This

text: follows

text: since

text: the

text: algebra

text: generated

text: by

text: increasing

text: Φ

text: is

text: dense

text: in

text: the

text: set

text: of

text: all

text: polynomials

text: and

text: this

text: suﬃces

text: to

text: deduce

text: x

text: y

text: (see

text: Proposition

text: in

text: The

text: closedness

text: follows

text: since

text: the

text: monomials

text: generate

text: the

text: Gromov-weak

text: topol-

text: ogy.

text: One

text: may

text: think

text: that

text: for

text: “small”

text: spaces

text: (with

text: few

text: points)

text: one

text: only

text: needs

text: to

text: look

text: at

text: low

text: order

text: polynomials.

text: The

text: next

text: example

text: shows

text: that

text: this

text: is

text: not

text: the

text: case.

text: Nevertheless

text: we

text: think

text: that

text: the

text: characterization

text: result,

text: Theorem

text: might

text: be

text: helpful

text: algorithmically

text: to

text: determine

text: whether

text: x

text: y

text: holds.

text: metric

text: Example

text: We

text: consider

text: x

text: a,

text: b

text: r(a,

text: b)

text: (δ

text: δ

text: and

text: y

text: a

text: b

text: c,

text: d,

text: e

text: r(c,

text: d)

text: r(c,

text: e)

text: r(d,

text: e)

text: (δ

text: δ

text: δ

text: Then,

text: on

text: the

text: c

text: d

text: e

text: one

text: hand,

text: one

text: can

text: not

text: ﬁnd

text: a

text: measure

text: preserving

text: sub-isometry

text: but

text: on

text: the

text: other

text: hand

text: it

text: is

text: not

text: obvious

text: that

text: the

text: distance

text: matrix

text: distributions

text: do

text: not

text: dominate

text: each

text: other.

text: In

text: particular

text: one

text: needs

text: to

text: consider

text: the

text: distance

text: matrix

text: distribution

text: of

text: order

text: m=

text: to

text: see

text: that

text: νm,x

text: νm,y:

text: If

text: we

text: look

text: at

text: the

text: sequence

text: of

text: points

text: x

text: a,

text: a,

text: b,

text: b

text: m

text: m

text: and

text: R

text: the

text: corresponding

text: distance

text: matrix,

text: then

text: νm,x

text: [R

text: i,j

text: i<j

text: m

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: 16 ≤ (a) It is true that x ¯z, i = 1, 2. i metric (b) We have the following identity: dλ (x , x ) = dλ (x ,¯z) + dλ (¯z, x ). (4.32) Eur 1 2 Eur 1 Eur 2 ∈ M ≤ ≤ (c) Let w = [X , r , µ ] with x w, i = 1, 2. If w ¯z, then 3 3 3 1 i metric metric we have w = ¯z. × → (cid:55)→ Proof. (a) Consider the mapping π : X X X , (x , x ) x , i = 1, 2. i 1 2 i 1 2 i This mapping is measure-preserving on the correponding image set and a sub- isometry. (b) We use(cid:90)T(cid:12)heorem 4.10 to calcula(cid:12)te: (cid:12) (cid:12) (cid:12) (cid:12) (cid:90) − − − (cid:48) (cid:48) dλ (x , x ) = e λr1(x,y) e λr2(x,y) Q(d(x, x ))Q(d(y, y )) Eur 1 2 (cid:90) − − − − ∧ − (cid:48) (cid:48) = e λr1(x,y) + e λr2(x,y) 2e λr1(x,y) e λr2(x,y)Q(d(x, x ))Q(d(y, y )) − − − − ∨ (cid:48) (cid:48) = e λr1(x,y) + e λr2(x,y) 2e λr1(x,y) r2(x,y)Q(d(x, x ))Q(d(y, y )) = dλ (x ,¯z) + dλ (¯z, x ). Eur 1 Eur 2 (4.33) (c) Note that Theorem 4.10 gives − dλ (¯z, w) = dλ (x ,¯z) dλ (x , w), (4.34) Eur Eur 1 Eur 1 − dλ (¯z, w) = dλ (x ,¯z) dλ (x , w). (4.35) Eur Eur 2 Eur 2 This implies (cid:0) (cid:1) (cid:0) (cid:1) 1 − 1 dλ (¯z, w) = dλ (x ,¯z) + dλ (x ,¯z) dλ (x , w) + dλ (x , w) . (4.36) Eur 2 Eur 1 Eur 2 2 Eur 1 Eur 2 Now we can use the result in (b) and the triangle inequality to get ≤ 1 − 1 dλ (¯z, w) dλ (x , x ) dλ (x , x ) = 0. (4.37) Eur 2 Eur 1 2 2 Eur 1 2 And therefore w = ¯z. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: (a)

text: It

text: is

text: true

text: that

text: x

text: ¯z,

text: i

text: i

text: metric

text: (b)

text: We

text: have

text: the

text: following

text: identity:

text: dλ

label: equation

text: (x

text: x

text: dλ

text: (x

text: ,¯z)

text: dλ

text: (¯z,

text: x

text: Eur

text: Eur

text: Eur

text: M

text: (c)

text: Let

text: w

text: [X

text: r

text: µ

text: with

text: x

text: w,

text: i

text: If

text: w

text: ¯z,

text: then

text: i

text: metric

text: metric

text: we

text: have

text: w

text: ¯z.

text: Proof.

text: (a)

text: Consider

text: the

text: mapping

text: π

text: X

text: X

text: X

text: (x

text: x

text: x

text: i

text: i

text: i

text: i

text: This

text: mapping

text: is

text: measure-preserving

text: on

text: the

text: correponding

text: image

text: set

text: and

text: a

text: sub-

text: isometry.

text: (b)

text: We

text: to

text: dλ

text: (x

text: x

text: e

text: e

text: Q(d(x,

text: x

text: ))Q(d(y,

text: y

text: Eur

text: e

text: e

text: e

text: x

text: ))Q(d(y,

text: y

text: e

text: e

text: x

text: ))Q(d(y,

text: y

text: dλ

text: (x

text: ,¯z)

text: dλ

text: (¯z,

text: x

text: Eur

text: Eur

text: (c)

text: Note

text: that

text: Theorem

text: gives

text: dλ

text: (¯z,

text: w)

text: dλ

text: (x

text: ,¯z)

text: dλ

text: (x

text: w),

text: Eur

text: Eur

text: Eur

text: dλ

text: (¯z,

text: w)

text: dλ

text: (x

text: ,¯z)

text: dλ

text: (x

text: w).

text: Eur

text: Eur

text: Eur

text: This

text: implies

text: dλ

text: (¯z,

text: w)

text: dλ

text: (x

text: ,¯z)

text: dλ

text: (x

text: ,¯z)

text: dλ

text: (x

text: w)

text: dλ

text: (x

text: w)

text: Eur

text: Eur

text: Eur

text: Eur

text: Eur

text: Now

text: we

text: can

text: use

text: the

text: result

text: in

text: (b)

text: and

text: the

text: triangle

text: inequality

text: to

text: get

text: dλ

text: (¯z,

text: w)

text: dλ

text: (x

text: x

text: dλ

text: (x

text: x

text: Eur

text: Eur

text: Eur

text: And

text: therefore

text: w

text: ¯z.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 22 Ua,b = (Ua,b) ≥ taking values in ultrametric measure spaces, denoted by U; t t 0 it is relat√ed to the total mass process (Xa,b) ≥ which solves the SDE dX = t t 0 ∈ R t bX dt + aX dB . Here a > 0 is the diﬀusivity and b is the criticality of t t t the oﬀspring distribution. The inﬁnitesimal genera(cid:88)tor of Ua,b is given as in [10]: ∇ a ◦ La,bΦm,φ(u) = Φm,2¯φ(u) + bmΦm,φ + Φm,φ θk,l(u) . (6.12) (cid:80) u¯ ≤ (cid:0)≤ ≤ (cid:1) 1 k l m ∇ The notation for ¯ φ = ≤ ≤ ∂ φ and θ (r) := r 1{ (cid:54) (cid:54) } + 1 k<l m ∂rkl k,l i,j i,j i=l,j=l r 1{ } + r 1{ } is taken from [12]. k,j i=l i,k j=l It is well-known that for the total mass process one may couple two processes with diﬀerent criticality and same initial condition. More precisely, when a > 0 ∈ R and b1 < b2 , then we may deﬁne≥Xa,b1 and Xa,b2 o≤n a joint probability space such that almost surely for all t 0 we have Xa,b1 Xa,b2. One way to t t prove that result is the classical comparison theorem for SDEs. The following analogue for the tree-valued Feller diﬀusion holds true. ∈ U ∈ R Proposition 6.12. Let u . For a > 0 and b1 < b2 let Ua,bi be a solution of the (La,bi, δu)-martingale problem, i = 1, 2. We have for all t > 0 almost surely, ≤ Ua,b1 Ua,b2 . (6.13) t measure t This result tells that the tree for Ua,b1 is really a subtree of Ua,b2 for any ≥ t t t 0. Proof. Recall from [8] that there are Galton-Watson processes such that rescal- ing them leads to the processes Ua,b1 and Ua,b2. For example one may choose oﬀspring distribution Poiss(1 + b /N) and Poiss(1 + b /N), respectively. It is 1≤ 2 well-known that Poiss(1 + b /N) Poiss(1 + b /N) stochastically, so we may 1 2 couple the two processes such that the oﬀspring distribution of the b process is 1 always at most that of the b process. Now, Proposition 3 in [15] tells us that 2 this coupling persists in the limit. Remark 6.13. Of course the drift term bX dt which appears in the last proposi- t tion may be changed to more general terms. For example one may also compare a process with linear drift and that with an additional quadratic death rate. This process is known as the logistic Feller diﬀusion. The same proof strategy allows to show that the process with the quadratic death rate can be coupled and be embedded in the process without that rate. This tells us that the geneal- ogy of the logistic Feller diﬀusion can really be obtained by leaving out some individuals in the genealogical tree of the population without the death rate. This is suggested in [17]. The right way to do remove individuals in a symmetric ♣ model, however, still remains unclear. Besides the proof of Proposition 6.12 there is more indication for the result to hold. In [21]’s Remark 2.3 (b) it is mentioned that for solutions of martingale problems in partially ordered state spaces there is a generator criterion to deduce ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Ua,b

text: (Ua,b)

text: taking

text: values

text: in

text: ultrametric

text: measure

text: spaces,

text: denoted

text: by

text: U;

text: t

text: t

text: it

text: is

text: relat√ed

text: to

text: the

text: total

text: mass

text: process

text: (Xa,b)

text: which

text: solves

text: the

text: SDE

text: dX

text: t

text: t

text: R

text: t

text: bX

text: dt

text: aX

text: dB

text: Here

text: a

text: is

text: the

text: diﬀusivity

text: and

text: b

text: is

text: the

text: criticality

text: of

text: t

text: t

text: t

text: the

text: oﬀspring

text: distribution.

text: The

text: inﬁnitesimal

text: of

text: Ua,b

text: is

text: given

text: as

text: in

text: a

text: La,bΦm,φ(u)

text: bmΦm,φ

text: Φm,φ

text: θk,l(u)

text: u¯

text: k

text: l

text: m

text: The

text: notation

text: for

text: φ

text: φ

text: and

text: θ

text: (r)

text: r

text: k<l

text: m

text: ∂rkl

text: k,l

text: i,j

text: i,j

text: i=l,j=l

text: r

text: r

text: is

text: taken

text: from

text: k,j

text: i=l

text: i,k

text: j=l

text: It

text: is

text: well-known

text: that

text: for

text: the

text: total

text: mass

text: process

text: one

text: may

text: couple

text: two

text: processes

text: with

text: diﬀerent

text: criticality

text: and

text: same

text: initial

text: condition.

text: More

text: precisely,

text: when

text: a

text: R

text: and

text: then

text: we

text: may

text: and

text: o≤n

text: a

text: joint

text: probability

text: space

text: such

text: that

text: almost

text: surely

text: for

text: all

text: t

text: we

text: have

text: One

text: way

text: to

text: t

text: t

text: prove

text: that

text: result

text: is

text: the

text: classical

text: comparison

text: theorem

text: for

text: SDEs.

text: The

text: following

text: analogue

text: for

text: the

text: tree-valued

text: Feller

text: diﬀusion

text: holds

text: true.

text: U

text: R

text: Proposition

text: Let

text: u

text: For

text: a

text: and

text: let

text: Ua,bi

text: be

text: a

text: solution

text: of

text: the

text: (La,bi,

text: δu)-martingale

text: problem,

text: i

text: We

text: have

text: for

text: all

text: t

text: almost

text: surely,

text: t

text: measure

text: t

text: This

text: result

text: tells

text: that

text: the

text: tree

text: for

text: is

text: really

text: a

text: subtree

text: of

text: for

text: any

text: t

text: t

text: t

text: Proof.

text: Recall

text: from

text: that

text: there

text: are

text: Galton-Watson

text: processes

text: such

text: that

text: rescal-

text: ing

text: them

text: leads

text: to

text: the

text: processes

text: and

text: For

text: example

text: one

text: may

text: choose

text: oﬀspring

text: distribution

text: b

text: /N)

text: and

text: b

text: /N),

text: respectively.

text: It

text: is

text: 1≤

text: well-known

text: that

text: b

text: /N)

text: b

text: /N)

text: stochastically,

text: so

text: we

text: may

text: couple

text: the

text: two

text: processes

text: such

text: that

text: the

text: oﬀspring

text: distribution

text: of

text: the

text: b

text: process

text: is

text: always

text: at

text: most

text: that

text: of

text: the

text: b

text: process.

text: Now,

text: Proposition

text: in

text: tells

text: us

text: that

text: this

text: coupling

text: persists

text: in

text: the

text: limit.

text: Remark

text: Of

text: course

text: the

text: drift

text: term

text: bX

text: dt

text: which

text: appears

text: in

text: the

text: last

text: proposi-

text: t

text: tion

text: may

text: be

text: changed

text: to

text: more

text: general

text: terms.

text: For

text: example

text: one

text: may

text: also

text: compare

text: a

text: process

text: with

text: linear

text: drift

text: and

text: that

text: with

text: an

text: additional

text: quadratic

text: death

text: rate.

text: This

text: process

text: is

text: known

text: as

text: the

text: logistic

text: Feller

text: diﬀusion.

text: The

text: same

text: proof

text: strategy

text: allows

text: to

text: show

text: that

text: the

text: process

text: with

text: the

text: quadratic

text: death

text: rate

text: can

text: be

text: coupled

text: and

text: be

text: embedded

text: in

text: the

text: process

text: without

text: that

text: rate.

text: This

text: tells

text: us

text: that

text: the

text: geneal-

text: ogy

text: of

text: the

text: logistic

text: Feller

text: diﬀusion

text: can

text: really

text: be

text: obtained

text: by

text: leaving

text: out

text: some

text: individuals

text: in

text: the

text: genealogical

text: tree

text: of

text: the

text: population

text: without

text: the

text: death

text: rate.

text: This

text: is

text: suggested

text: in

text: The

text: right

text: way

text: to

text: do

text: remove

text: individuals

text: in

text: a

text: symmetric

text: model,

text: however,

text: still

text: remains

text: unclear.

text: Besides

text: the

text: proof

text: of

text: Proposition

text: there

text: is

text: more

text: indication

text: for

text: the

text: result

text: to

text: hold.

text: In

text: Remark

text: (b)

text: it

text: is

text: mentioned

text: that

text: for

text: solutions

text: of

text: martingale

text: problems

text: in

text: partially

text: ordered

text: state

text: spaces

text: there

text: is

text: a

text: generator

text: criterion

text: to

text: deduce

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 25 time 1 2 3 4 t (3, 4) 3 t (2, 1) 2 t (2, 3) 1 1 2 3 4 Figure 1: Graphical construction of the TVMM (i.e. the tree on the right side): At times t1,t2,t3 we sample to individuals (x11,x12), (x21,x22), (x31,x32) and draw an arrow from xj1 to xj. 2 Proof. We will only sketch the proof. For details about Kingman-coalescents see for example [2]. U Step 1. In this step we give the connection of γ,N and a Kingman N-coalescent with coalescing rate γ. ≥ ≤ ≤ { } For ﬁxed t 0, we set A (i) := A − (i, t), 0 h t and [N] := 1, . . . , N . { ∈ } h t h Then A (i) : i [N] can be described as a family of processes in [N]N that h { − } starts in A (i) = i and has the following dynamic: Whenever ηγ( t h ) = 1 0 (see Remark 6.14), we pick independent and uniformly without replacement two (cid:54) individuals i = j and have the following transition: → ∀ ∈ { ∈ } A −(k) A (k) = i, k l [n] : A −(l) = j . (6.24) h h h (cid:0) (cid:1) It is now straightforward to see that the time it takes to decrease the num- ber of diﬀerent labels by 1, given there are k diﬀerent labels, is exponential · distributed with parameter γ k and that the two labels (the one that replaces 2 and the one that is replaced) are sampled uniformly without replacement under all existing labels. If we deﬁne { ∈ } κ (h) = j [N] : A (j) = A (i) , (6.25) i h h { } this implies κ = ( κ (h), . . . , κ (h) ) ≤ ≤ is a Kingman N-coalescent (up 1 N 0 h t to time t). If we know deﬁne (cid:88) V { } 1 N N = [ 1, . . . , N , rκ, δ ], (6.26) t t N k k=1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: time

text: t

text: t

text: t

text: Figure

text: Graphical

text: construction

text: of

text: the

text: TVMM

text: (i.e.

text: the

text: tree

text: on

text: the

text: right

text: side):

text: At

text: times

text: we

text: sample

text: to

text: individuals

text: and

text: draw

text: an

text: arrow

text: from

text: to

text: xj.

text: Proof.

text: We

text: will

text: only

text: sketch

text: the

text: proof.

text: For

text: details

text: about

text: Kingman-coalescents

text: see

text: for

text: example

text: U

text: Step

text: In

text: this

text: step

text: we

text: give

text: the

text: connection

text: of

text: γ,N

text: and

text: a

text: Kingman

text: N-coalescent

text: with

text: coalescing

text: rate

text: γ.

text: For

text: ﬁxed

text: t

text: we

text: set

text: A

text: (i)

text: A

text: (i,

text: t),

text: h

text: t

text: and

text: [N]

text: N

text: h

text: t

text: h

text: Then

text: A

text: (i)

text: i

text: [N]

text: can

text: be

text: described

text: as

text: a

text: family

text: of

text: processes

text: in

text: [N]N

text: that

text: h

text: starts

text: in

text: A

text: (i)

text: i

text: and

text: has

text: the

text: following

text: dynamic:

text: Whenever

text: ηγ(

text: t

text: h

text: (see

text: Remark

text: we

text: pick

text: independent

text: and

text: uniformly

text: without

text: replacement

text: two

text: individuals

text: i

text: j

text: and

text: have

text: the

text: following

text: transition:

text: A

text: −(k)

text: A

text: (k)

text: i,

text: k

text: l

text: [n]

text: A

text: −(l)

text: j

text: h

text: h

text: h

text: It

text: is

text: now

text: straightforward

text: to

text: see

text: that

text: the

text: time

text: it

text: takes

text: to

text: decrease

text: the

text: num-

text: ber

text: of

text: diﬀerent

text: labels

text: by

text: given

text: there

text: are

text: k

text: diﬀerent

text: labels,

text: is

text: exponential

text: distributed

text: with

text: parameter

text: γ

text: k

text: and

text: that

text: the

text: two

text: labels

text: (the

text: one

text: that

text: replaces

text: and

text: the

text: one

text: that

text: is

text: replaced)

text: are

text: sampled

text: uniformly

text: without

text: replacement

text: under

text: all

text: existing

text: labels.

text: If

text: we

text: deﬁne

text: κ

text: (h)

text: j

text: [N]

text: A

text: (j)

text: A

text: (i)

text: i

text: h

text: h

text: this

text: implies

text: κ

text: κ

text: (h),

text: κ

text: (h)

text: is

text: a

text: Kingman

text: N-coalescent

text: (up

text: N

text: h

text: t

text: to

text: time

text: t).

text: If

text: we

text: know

text: deﬁne

text: V

text: N

text: N

text: N

text: rκ,

text: δ

text: t

text: t

text: N

text: k

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: CRITICAL BASES FOR TERNARY ALPHABETS 13 Furthermore, ≤ P r(m) < R , m m and the equality holds only if . r(m) = P m = M m d ∞ Proof. The ﬁrst assertion follows by observing that is a con- π (m1 ) ∈ ∞ q tinuous decreasing function of , and q (0, ) ∞ ∞ ∞ lim π (m1 ) = , lim π (m1 ) = 0. → q →∞ q q 1 q The second assertion follows from (9.4) and the formulas (9.5), (9.6) (cid:3) of the Appendix. Proof of Proposition 1.4. ≤ First step. If , then 1 < q r(m) ∞ ≥ − π (m1 ) m 1. q ≤ Since by (5.1), by Proposition 1.1 (iii) it is 2 < P r(m) < R m m ≤ suﬃcient to consider the case . 2 < q r(m) Then we may apply Lemma 4.3 to infer that is a forbidden block. 1m (cid:48) ⊂ { ∞ ∗ ∞} (cid:48) Hence , and thus is countable. V m , m 1 V m,q m,q (cid:48) Second step. If , then has the power of continuum. q > r(m) V m,q ∞ − Indeed, our assumption on implies that . There q π (m1 ) < m 1 q exists therefore a positive integer satisfying k ∞ − (5.2) π ((m1k) ) < m 1. q (cid:8) (cid:9) We complete the proof by showing that each sequence ∈ ∞ (c ) m1(cid:96) : (cid:96) = k, k + 1, . . . i (cid:48) belongs to . V m,q ≥ Since , it is suﬃcient to check the conditions of Lemma q > P 2 m 4.2. In fact, the conditions (4.1) are satisﬁed for all : we have n ≤ ∞ − π (c ) π ((m1k) ) < m 1 q n+i q ≤ ∞ by the lexicographic inequality (c ) (m1k) , Lemma 4.1 and (5.2), n+i and − − ≤ − ∞ m 1 π (m c ) π ((m 1) ) = − < 1 q n+i q q 1 ≥ because for all , and . c 1 n q > m n+i (cid:3) It follows from the preceding steps that . r = r(m) m ##LTLine##

text: CRITICAL

text: BASES

text: FOR

text: TERNARY

text: ALPHABETS

text: Furthermore,

text: P

text: r(m)

text: R

text: m

text: m

text: and

text: the

text: equality

text: holds

text: only

text: if

text: r(m)

text: P

text: m

text: M

text: m

text: d

text: Proof.

text: The

text: ﬁrst

text: assertion

text: follows

text: by

text: observing

text: that

text: is

text: a

text: con-

text: π

text: q

text: tinuous

text: decreasing

text: function

text: of

text: and

text: q

text: lim

text: π

text: lim

text: π

text: q

text: q

text: q

text: q

text: The

text: second

text: assertion

text: follows

text: from

text: and

text: the

text: formulas

text: of

text: the

text: Appendix.

text: Proof

text: of

text: Proposition

text: First

text: step.

text: If

text: then

text: q

text: r(m)

text: π

text: m

text: q

text: Since

text: by

text: by

text: Proposition

text: (iii)

text: it

text: is

text: P

text: r(m)

text: R

text: m

text: m

text: suﬃcient

text: to

text: consider

text: the

text: case

text: q

text: r(m)

text: Then

text: we

text: may

text: apply

text: Lemma

text: to

text: infer

text: that

text: is

text: a

text: forbidden

text: block.

text: Hence

text: and

text: thus

text: is

text: countable.

text: V

text: m

text: m

text: V

text: m,q

text: m,q

text: Second

text: step.

text: If

text: then

text: has

text: the

text: power

text: of

text: continuum.

text: q

text: r(m)

text: V

text: m,q

text: Indeed,

text: our

text: assumption

text: on

text: implies

text: that

text: There

text: q

text: π

text: m

text: q

text: exists

text: therefore

text: a

text: positive

text: integer

text: satisfying

text: k

text: π

text: m

text: q

text: We

text: complete

text: the

text: proof

text: by

text: showing

text: that

text: each

text: sequence

text: (c

text: k,

text: k

text: i

text: belongs

text: to

text: V

text: m,q

text: Since

text: it

text: is

text: suﬃcient

text: to

text: check

text: the

text: conditions

text: of

text: Lemma

text: q

text: P

text: m

text: In

text: fact,

text: the

text: conditions

text: are

text: satisﬁed

text: for

text: all

text: we

text: have

text: n

text: π

text: (c

text: π

text: m

text: q

text: n+i

text: q

text: by

text: the

text: lexicographic

text: inequality

text: (c

text: Lemma

text: and

text: n+i

text: and

text: m

text: π

text: (m

text: c

text: π

text: ((m

text: q

text: n+i

text: q

text: q

text: because

text: for

text: all

text: and

text: c

text: n

text: q

text: m

text: n+i

text: It

text: follows

text: from

text: the

text: preceding

text: steps

text: that

text: r

text: r(m)

text: m

text: ##LTLine##


text: 16 VILMOS KOMORNIK AND MARCO PEDICINI ∈ { }∞ Next assume that does not contain any block , (c ) 1, m 1mm i but it contains a block . Then using also the preceding c c = 11 n n+1 observation, − ≥ ∞ − ∞ ≥ π (m c ) π (m (1m) ) 1 q n+i q ∈ (cid:48) by hypothesis, and therefore again. (c ) / V (cid:48) ⊂ { ∞ i ∗ m,∞q } It follows that , and hence it is countable. V m , m (1m) m,q (cid:48) Second step. If , then has the power of continuum. q > r(m) V m,q ∞ − ∞ Indeed, it follows from(cid:0) our as(cid:0)sumptio(cid:1)n t(cid:1)hat π (m (1m) ) < 1. q There exists therefore a (suﬃciently large) positive integer satisfying k ∞ − ∞ π m (1m)k1 < 1. (cid:8) q (cid:9) We complete the proof by showing the inclusion ≥ ∞ ⊂ (cid:48) (1m)(cid:96)1 : (cid:96) k V . m,q We have to check that each sequence in the left hand side set (c ) i satisﬁes the conditions of Lemma 4.2. For this we use the sequence (cid:48) ∞ , introduced at the beginning of Section 4 in [17]; see also δ = (m1) [17, Lemma 3.9]. If , then [17, Lemma 5.11] and the relation imply c = 1 q > p (cid:48) ∈ n(cid:48) m and hence δ V m,q ∞ (cid:48) − π (c ) < π ((m1(cid:0)) ) =(cid:0)π (δ ) <(cid:1) m(cid:1) 1, q n+i q q while − ≤ − ∞ π (m c ) π m (1m)k1 < 1 q n+i q by the choice of . k (cid:3) It follows from the preceding steps that . r = r(m) m 7. Proof of Proposition 1.5 (ii) ∞ ≈ ≈ In this section we still have , and d = (10) m 2.80194 M d d . We consider the subinterval of 4.54646] [m , m ] := [2.992, 3.10214] 2 3 . (m , M ) d d ∈ Lemma 7.1. For each m [m , m ] there exists a number r(m) > 1 2 3 such that ≤ ⇒ ∞ ≥ − 1 < q r(m) = π (mm1(m11m) ) m 1, q ⇒ ∞ − and q > r(m) = π (mm1(m11m) ) < m 1 q ∞ − ∞ π (m (1mm1) ) < 1. q Furthermore, . P < r(m) < R m m See Figure 1.4.

text: VILMOS

text: KOMORNIK

text: AND

text: MARCO

text: PEDICINI

text: Next

text: assume

text: that

text: does

text: not

text: contain

text: any

text: block

text: (c

text: m

text: i

text: but

text: it

text: contains

text: a

text: block

text: Then

text: using

text: also

text: the

text: preceding

text: c

text: c

text: n

text: observation,

text: π

text: (m

text: c

text: π

text: (m

text: q

text: n+i

text: q

text: by

text: hypothesis,

text: and

text: therefore

text: again.

text: (c

text: V

text: i

text: m,∞q

text: It

text: follows

text: that

text: and

text: hence

text: it

text: is

text: countable.

text: V

text: m

text: m

text: m,q

text: Second

text: step.

text: If

text: then

text: has

text: the

text: power

text: of

text: continuum.

text: q

text: r(m)

text: V

text: m,q

text: Indeed,

text: it

text: follows

text: our

text: π

text: (m

text: q

text: There

text: exists

text: therefore

text: a

text: (suﬃciently

text: large)

text: positive

text: integer

text: satisfying

text: k

text: π

text: m

text: q

text: We

text: complete

text: the

text: proof

text: by

text: showing

text: the

text: inclusion

text: k

text: V

text: m,q

text: We

text: have

text: to

text: check

text: that

text: each

text: sequence

text: in

text: the

text: left

text: hand

text: side

text: set

text: (c

text: i

text: satisﬁes

text: the

text: conditions

text: of

text: Lemma

text: For

text: this

text: we

text: use

text: the

text: sequence

text: introduced

text: at

text: the

text: beginning

text: of

text: Section

text: in

text: see

text: also

text: δ

text: Lemma

text: If

text: then

text: Lemma

text: and

text: the

text: relation

text: imply

text: c

text: q

text: p

text: m

text: and

text: hence

text: δ

text: V

text: m,q

text: π

text: (c

text: π

text: (δ

text: q

text: n+i

text: q

text: q

text: while

text: π

text: (m

text: c

text: π

text: m

text: q

text: n+i

text: q

text: by

text: the

text: choice

text: of

text: k

text: It

text: follows

text: from

text: the

text: preceding

text: steps

text: that

text: r

text: r(m)

text: m

text: Proof

text: of

text: Proposition

text: (ii)

text: In

text: this

text: section

text: we

text: still

text: have

text: and

text: d

text: m

text: M

text: d

text: d

text: We

text: consider

text: the

text: subinterval

text: of

text: [m

text: m

text: (m

text: M

text: d

text: d

text: Lemma

text: For

text: each

text: m

text: [m

text: m

text: there

text: exists

text: a

text: number

text: r(m)

text: such

text: that

text: q

text: r(m)

text: π

text: m

text: q

text: and

text: q

text: r(m)

text: π

text: m

text: q

text: π

text: (m

text: q

text: Furthermore,

text: P

text: r(m)

text: R

text: m

text: m

text: See

text: Figure


text: CRITICAL BASES FOR TERNARY ALPHABETS 23 We recall from [17] that the connected component (m , M ) = (2.80194 . . . , 4.54646 . . .) ∞ \ d d{ ∞} of , associated with the admissible sequence , is [2, ) C d = (10) deﬁned by the equations ∞ − ∞ − ∞ and π ((m 1) ) = m 1 π (M (M 1) ) = 1, Pmd d PMd d d { (cid:48) (cid:48)(cid:48) } ∈ (cid:48) (cid:48)(cid:48) and that for all , where and p = max p , p m [m , M ] p p m m m d d m m are uniquely deﬁned by the equations ∞ − ∞ − ∞ and π (cid:48) ((m1) ) = m 1 π (cid:48)(cid:48) (m (m1) ) = 1. p p m m We have ∞ − − 1 − ∞ − − π ((m1) ) (m 1) = − + (m 1)π ((10) ) (m 1) q q q 1 − 1 (m 1)q − − = − + − (m 1) q 1 q2 1 − − − − (q + 1) (m 1)(q2 q 1) = − . q2 1 Hence (cid:112) ∞ − ⇐⇒ (9.7) π ((m1) ) = (m 1) q − − m 1 + (m 1)2 + 4 q = r(m) := . 2 Furthermore, using (9.1) we obtain ∞ − − ∼ − − − − π ((m1) ) (m 1) (P + 1) (m 1)(P 2 P 1) Pm ∼ m − −m m− − (P + 1)P (P 2) (P 2 P 1). m m m m m Hence ∞ − − ∼ − − (9.8) π ((m1) ) (m 1) P 3 2P 2 P + 1 Pm m m m (cid:55)→ after simpliﬁcation, and, using the decreasingness of , m P m − − ∼ − (9.9) P 3 2P 2 P + 1 m m. m m m d Finally, it follows from the identity ∞ − ∞ − − ∞ − π (m (m1) ) 1 = (m 1)π ((01) ) 1 q q − m 1 − = − 1 q2 1 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: CRITICAL

text: BASES

text: FOR

text: TERNARY

text: ALPHABETS

text: We

text: recall

text: from

text: that

text: the

text: connected

text: component

text: (m

text: M

text: d

text: d{

text: of

text: associated

text: with

text: the

text: admissible

text: sequence

text: is

text: C

text: d

text: deﬁned

text: by

text: the

text: equations

text: and

text: π

text: ((m

text: m

text: π

text: (M

text: (M

text: Pmd

text: d

text: PMd

text: d

text: d

text: and

text: that

text: for

text: all

text: where

text: and

text: p

text: max

text: p

text: p

text: m

text: [m

text: M

text: p

text: p

text: m

text: m

text: m

text: d

text: d

text: m

text: m

text: are

text: uniquely

text: deﬁned

text: by

text: the

text: equations

text: and

text: π

text: m

text: π

text: (m

text: p

text: p

text: m

text: m

text: We

text: have

text: π

text: (m

text: (m

text: (m

text: q

text: q

text: q

text: (m

text: (m

text: q

text: (q

text: (m

text: q

text: Hence

text: π

text: (m

text: q

text: m

text: (m

text: q

text: r(m)

text: Furthermore,

text: using

text: we

text: obtain

text: π

text: (m

text: (P

text: (m

text: P

text: Pm

text: m

text: −m

text: m−

text: (P

text: (P

text: (P

text: P

text: m

text: m

text: m

text: m

text: m

text: Hence

text: π

text: (m

text: P

text: P

text: Pm

text: m

text: m

text: m

text: after

text: simpliﬁcation,

text: and,

text: using

text: the

text: decreasingness

text: of

text: m

text: P

text: m

text: P

text: P

text: m

text: m.

text: m

text: m

text: m

text: d

text: Finally,

text: it

text: follows

text: from

text: the

text: identity

text: π

text: (m

text: (m

text: q

text: q

text: m

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 15 σ represents the beneﬁt that a caching user gains when storing data. Now similarly to (7), (8) and (9), we ﬁnd the upkeep costs to be       · − − Θ χ(Simple Caching) σ(Θ 1) for simple caching,  · − λ1 +−m1ω χ(Upkeep) = Θ χ(Replication) nσ(Θ 1) for replication, · − − Θ χ(Regenerating) nασ(Θ 1) for regenerating codes. In other words, when data are distributed and cached redundantly, the operator avoids the cost of data transmission from the base station altogether, but has to pay a cost of Θ for each transmitted unit of data over unit distance and σ for each unit of data cached on a user equipment. We now deﬁne the caching gain of an operator as G = χ(Downlink), (10) χ(Upkeep) which we call operator gain. In the next section, we present numerical results of both operator gains and overall energy consumption cost savings. V. NUMERICAL RESULTS In this section, we illustrate the performance of the four considered caching methods with respect to the derived performance metric with the help of numerical results. We investigate three cases: low, moderate and high storage cost, while the parameters of replication (n) and regenerating codes (n, k, d) are chosen from a small interval so that the cost function is mini- mized. Further, we study the operator gains for short and long distances from the cluster to the base station. For all cases in this section, we ﬁx m = 100, λ = 1, r = 1, Γ = 2 and Γ = 4, while σ BS D2D is varied. For the overall energy consumption results we ﬁx v = 20, while two values, v = 10 ∈ and v = 20, are considered for the operator gain. We choose n [2, 6] for replication, and ∈ n [3, 6] for regenerating codes, so that the cost is minimized for a given ω. The theoretical curves (solid lines) in the ﬁgures are numerical values using the derived cost functions (7), (8) and (9), while the simulated values (dots) are obtained by computing steady state averages of ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: σ

text: represents

text: the

text: beneﬁt

text: that

text: a

text: caching

text: user

text: gains

text: when

text: storing

text: data.

text: Now

text: similarly

text: to

text: and

text: we

text: ﬁnd

text: the

text: upkeep

text: costs

text: to

text: be

text: Θ

text: χ(Simple

text: Caching)

text: σ(Θ

text: for

text: simple

text: caching,

text: λ1

text: χ(Upkeep)

text: Θ

text: χ(Replication)

text: nσ(Θ

text: for

text: replication,

text: Θ

text: χ(Regenerating)

text: nασ(Θ

text: for

text: regenerating

text: codes.

text: In

text: other

text: words,

text: when

text: data

text: are

text: distributed

text: and

text: cached

text: redundantly,

text: the

text: operator

text: avoids

text: the

text: cost

text: of

text: data

text: transmission

text: from

text: the

text: base

text: station

text: altogether,

text: but

text: has

text: to

text: pay

text: a

text: cost

text: of

text: Θ

text: for

text: each

text: transmitted

text: unit

text: of

text: data

text: over

text: unit

text: distance

text: and

text: σ

text: for

text: each

text: unit

text: of

text: data

text: cached

text: on

text: a

text: user

text: equipment.

text: We

text: now

text: deﬁne

text: the

text: caching

text: gain

text: of

text: an

text: operator

text: as

text: G

text: χ(Downlink),

text: χ(Upkeep)

text: which

text: we

text: call

text: operator

text: gain.

text: In

text: the

text: next

text: section,

text: we

text: present

text: numerical

text: results

text: of

text: both

text: operator

text: gains

text: and

text: overall

text: energy

text: consumption

text: cost

text: savings.

text: V.

text: NUMERICAL

text: RESULTS

text: In

text: this

text: section,

text: we

text: illustrate

text: the

text: performance

text: of

text: the

text: four

text: considered

text: caching

text: methods

text: with

text: respect

text: to

text: the

text: derived

text: performance

text: metric

text: with

text: the

text: help

text: of

text: numerical

text: results.

text: We

text: investigate

text: three

text: cases:

text: low,

text: moderate

text: and

text: high

text: storage

text: cost,

text: while

text: the

text: parameters

text: of

text: replication

text: (n)

text: and

text: regenerating

text: codes

text: (n,

text: k,

text: d)

text: are

text: chosen

text: from

text: a

text: small

text: interval

text: so

text: that

text: the

text: cost

text: function

text: is

text: mini-

text: mized.

text: Further,

text: we

text: study

text: the

text: operator

text: gains

text: for

text: short

text: and

text: long

text: distances

text: from

text: the

text: cluster

text: to

text: the

text: base

text: station.

text: For

text: all

text: cases

text: in

text: this

text: section,

text: we

text: ﬁx

text: m

text: λ

text: r

text: Γ

text: and

text: Γ

text: while

text: σ

text: BS

text: is

text: varied.

text: For

text: the

text: overall

text: energy

text: consumption

text: results

text: we

text: ﬁx

text: v

text: while

text: two

text: values,

text: v

text: and

text: v

text: are

text: considered

text: for

text: the

text: operator

text: gain.

text: We

text: choose

text: n

text: for

text: replication,

text: and

text: n

text: for

text: regenerating

text: codes,

text: so

text: that

text: the

text: cost

text: is

text: minimized

text: for

text: a

text: given

text: ω.

text: The

text: theoretical

text: curves

text: (solid

text: lines)

text: in

text: the

text: ﬁgures

text: are

text: numerical

text: values

text: using

text: the

text: derived

text: cost

text: functions

text: and

text: while

text: the

text: simulated

text: values

text: (dots)

text: are

text: obtained

text: by

text: computing

text: steady

text: state

text: averages

text: of

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3 bility – when a caching node moves away from the caching cluster, its content is lost. To avoid this, we introduce erasure coding to ensure data availability. The focus of this article is studying the performance of such coded caching clusters. The main contributions of this article can be summarized as follows: • We construct a system model for a clustered wireless D2D caching community based on stochastic geometry. • Closed-form expressions for the expected energy cost based on signal attenuation of both uncoded and coded D2D caching methods are derived, and we further examine under which conditions coded caching outperforms uncoded caching without redundancy. • It is shown that coded caching can yield signiﬁcant cost savings in terms of both the overall energy consumption and economical cost savings from a operator’s point of view. The rest of this paper is organized as follows. In Section , we present the system model used throughout this work. In Section , we introduce the proposed caching methods. Analytical cost estimates are derived in section Section III-0c, while simulation results are presented, and compared with the analytical results, in Section III-0c. Finally, conclusions are drawn in Section III-0c. II. SYSTEM MODEL We begin by introducing the system model assumed throughout the paper. We model a cluster of mobile terminals with data storage capabilities – or nodes – by a disk of radius r. The expected number of nodes present in the cluster is denoted by m, and the nodes are assumed to be uniformly distributed inside the disk. A single base station is located at a distance v > r from the center of the cluster. A graphical representation of the model is displayed in Figure 1. The nodes inside the cluster form a D2D caching community. We assume that each node knows about the content stored in every other node, and any two nodes can communicate data. We further assume that all data transmission links are error-free. The time dynamics of the system are modeled as follows. The time that an arbitrary node remains active in the cluster follows an exponential distribution with expected value T . We deﬁne a failure as the event when a node becomes inactive by leaving the system and denote the node failure rate by λ = 1/T . With these parameters, we can model the instantaneous state of ∞ the system via an M/M/ Markov model (cf. Figure 2), which has been widely used to model

text: bility

text: when

text: a

text: caching

text: node

text: moves

text: away

text: from

text: the

text: caching

text: cluster,

text: its

text: content

text: is

text: lost.

text: To

text: avoid

text: this,

text: we

text: introduce

text: erasure

text: coding

text: to

text: ensure

text: data

text: availability.

text: The

text: focus

text: of

text: this

text: article

text: is

text: studying

text: the

text: performance

text: of

text: such

text: coded

text: caching

text: clusters.

text: The

text: main

text: contributions

text: of

text: this

text: article

text: can

text: be

text: summarized

text: as

text: follows:

text: We

text: construct

text: a

text: system

text: model

text: for

text: a

text: clustered

text: wireless

text: caching

text: community

text: based

text: on

text: stochastic

text: geometry.

text: Closed-form

text: expressions

text: for

text: the

text: expected

text: energy

text: cost

text: based

text: on

text: signal

text: attenuation

text: of

text: both

text: uncoded

text: and

text: coded

text: caching

text: methods

text: are

text: derived,

text: and

text: we

text: further

text: examine

text: under

text: which

text: conditions

text: coded

text: caching

text: outperforms

text: uncoded

text: caching

text: without

text: redundancy.

text: It

text: is

text: shown

text: that

text: coded

text: caching

text: can

text: yield

text: signiﬁcant

text: cost

text: savings

text: in

text: terms

text: of

text: both

text: the

text: overall

text: energy

text: consumption

text: and

text: economical

text: cost

text: savings

text: from

text: a

text: operator’s

text: point

text: of

text: view.

text: The

text: rest

text: of

text: this

text: paper

text: is

text: organized

text: as

text: follows.

text: In

text: Section

text: we

text: present

text: the

text: system

text: model

text: used

text: throughout

text: this

text: work.

text: In

text: Section

text: we

text: introduce

text: the

text: proposed

text: caching

text: methods.

text: Analytical

text: cost

text: estimates

text: are

text: derived

text: in

text: section

text: Section

text: while

text: simulation

text: results

text: are

text: presented,

text: and

text: compared

text: with

text: the

text: analytical

text: results,

text: in

text: Section

text: Finally,

text: conclusions

text: are

text: drawn

text: in

text: Section

text: II.

text: SYSTEM

text: MODEL

text: We

text: begin

text: by

text: introducing

text: the

text: system

text: model

text: assumed

text: throughout

text: the

text: paper.

text: We

text: model

text: a

text: cluster

text: of

text: mobile

text: terminals

text: with

text: data

text: storage

text: capabilities

text: or

text: nodes

text: by

text: a

text: disk

text: of

text: radius

text: r.

text: The

text: expected

text: number

text: of

text: nodes

text: present

text: in

text: the

text: cluster

text: is

text: denoted

text: by

text: m,

text: and

text: the

text: nodes

text: are

text: assumed

text: to

text: be

text: uniformly

text: distributed

text: inside

text: the

text: disk.

text: A

text: single

text: base

text: station

text: is

text: located

text: at

text: a

text: distance

text: v

text: r

text: from

text: the

text: center

text: of

text: the

text: cluster.

text: A

text: graphical

text: representation

text: of

text: the

text: model

text: is

text: displayed

text: in

text: Figure

text: The

text: nodes

text: inside

text: the

text: cluster

text: form

text: a

text: caching

text: community.

text: We

text: assume

text: that

text: each

text: node

text: knows

text: about

text: the

text: content

text: stored

text: in

text: every

text: other

text: node,

text: and

text: any

text: two

text: nodes

text: can

text: communicate

text: data.

text: We

text: further

text: assume

text: that

text: all

text: data

text: transmission

text: links

text: are

text: error-free.

text: The

text: time

text: dynamics

text: of

text: the

text: system

text: are

text: modeled

text: as

text: follows.

text: The

text: time

text: that

text: an

text: arbitrary

text: node

text: remains

text: active

text: in

text: the

text: cluster

text: follows

text: an

text: exponential

text: distribution

text: with

text: expected

text: value

text: T

text: We

text: deﬁne

text: a

text: failure

text: as

text: the

text: event

text: when

text: a

text: node

text: becomes

text: inactive

text: by

text: leaving

text: the

text: system

text: and

text: denote

text: the

text: node

text: failure

text: rate

text: by

text: λ

text: With

text: these

text: parameters,

text: we

text: can

text: model

text: the

text: instantaneous

text: state

text: of

text: the

text: system

text: via

text: an

text: M/M/

text: Markov

text: model

text: (cf.

text: Figure

text: which

text: has

text: been

text: widely

text: used

text: to

text: model


text: 23 2.5 σ = 100, Θ = 1 MBR 2 MSR Replication 1.5 Simple caching 1 v = 20 0.5 v = 10 0 -0.5 -1 -2.5 -2 -1.5 -1 -0.5 0 log10 ω Fig. 10: Theoretical operator gains G (10) versus ﬁle popularity ω when v = 20 (solid line) and v = 10 (solid line with marker), with σ = 100 and Θ = 1. VI. CONCLUSIONS We have studied the prospective beneﬁts of distributed storage coding in a D2D caching cluster, where communication cost grows with distance due to increasing pathloss. Our main objective has been optimizing the overall energy-efﬁciency of the network in terms of energy costs of communication and storage. We have found that distributed storage coding can save more than 90% in energy consumption compared to caching without redundancy in a realistic scenario. Especially an error correcting code with minimum storage overhead, here a parity check code or an MDS code, offers plenty of ofﬂoad potential when storage space is moderately to highly expensive. However, when storage costs are low as compared to communication costs, simple repetition coding is preferred. When communication costs dominate over storage costs in the D2D community, physical proximity is of utmost importance due to pathloss. Further, we have shown that storage coding offers plenty of cost saving potential also from an operator’s point of view, part of which can be used to incentivize users to participate in a D2D caching community. ACKNOWLEDGEMENTS The authors would like to thank Majid Gerami, Ejder Bas¸tug˘, Toni Ernvall, Pasi Lassila, and Lasse Leskela¨ for fruitful discussions. G gol 01 ##LTFigure## ##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## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: default

text: σ

text: Θ

text: MBR

text: MSR

text: Replication

text: Simple

text: caching

text: v

text: v

text: ω

text: Fig.

text: Theoretical

text: operator

text: gains

text: G

text: versus

text: ﬁle

text: popularity

text: ω

text: when

text: v

text: (solid

text: line)

text: and

text: v

text: (solid

text: line

text: with

text: marker),

text: with

text: σ

text: and

text: Θ

text: VI.

text: CONCLUSIONS

text: We

text: have

text: studied

text: the

text: prospective

text: beneﬁts

text: of

text: distributed

text: storage

text: coding

text: in

text: a

text: caching

text: cluster,

text: where

text: communication

text: cost

text: grows

text: with

text: distance

text: due

text: to

text: increasing

text: pathloss.

text: Our

text: main

text: objective

text: has

text: been

text: optimizing

text: the

text: overall

text: energy-efﬁciency

text: of

text: the

text: network

text: in

text: terms

text: of

text: energy

text: costs

text: of

text: communication

text: and

text: storage.

text: We

text: have

text: found

text: that

text: distributed

text: storage

text: coding

text: can

text: save

text: more

text: than

text: in

text: energy

text: consumption

text: compared

text: to

text: caching

text: without

text: redundancy

text: in

text: a

text: realistic

text: scenario.

text: Especially

text: an

text: error

text: correcting

text: code

text: with

text: minimum

text: storage

text: overhead,

text: here

text: a

text: parity

text: check

text: code

text: or

text: an

text: MDS

text: code,

text: offers

text: plenty

text: of

text: ofﬂoad

text: potential

text: when

text: storage

text: space

text: is

text: moderately

text: to

text: highly

text: expensive.

text: However,

text: when

text: storage

text: costs

text: are

text: low

text: as

text: compared

text: to

text: communication

text: costs,

text: simple

text: repetition

text: coding

text: is

text: preferred.

text: When

text: communication

text: costs

text: dominate

text: over

text: storage

text: costs

text: in

text: the

text: community,

text: physical

text: proximity

text: is

text: of

text: utmost

text: importance

text: due

text: to

text: pathloss.

text: Further,

text: we

text: have

text: shown

text: that

text: storage

text: coding

text: offers

text: plenty

text: of

text: cost

text: saving

text: potential

text: also

text: from

text: an

text: operator’s

text: point

text: of

text: view,

text: part

text: of

text: which

text: can

text: be

text: used

text: to

text: incentivize

text: users

text: to

text: participate

text: in

text: a

text: caching

text: community.

text: ACKNOWLEDGEMENTS

text: The

text: authors

text: would

text: like

text: to

text: thank

text: Majid

text: Gerami,

text: Ejder

text: Bas¸tug˘,

text: Toni

text: Ernvall,

text: Pasi

text: Lassila,

text: and

text: Lasse

text: Leskela¨

text: for

text: fruitful

text: discussions.

text: G

text: gol

text: ##LTFigure##

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: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##