text: 4 assumption makes no restriction and all our results can be extended to the case where cost functions have some discontinuities. 2 Preliminaries In this section, we give a formal description of MCFP and present some existing results, required throughout the paper. We are given a directed graph G = (V, E) with node set V and arc set E and a time horizon T > 0. We denote an arc e from node v to node w by e = (v, w) and assume, without loss of generality, that there is at most one arc between any pair of → R nodes in G. Each arc e is associated w→ithRtwo functions; the transit cost ce : [0, T] and the transit capacity ue : [0, T] ≥0. Here, ce(θ) gives the cost per ﬂow unit for sending ﬂow in arc e at time θ and ue(θ) gives an upper bound on the rate (i.e., amount of ﬂow per time unit) at which ﬂow can enter arc e at time θ. In addition, ∈ R for each arc e, a transit time τe is given. The transit time is the amount of time required to send ﬂow from the tail to the head of e. Thus ﬂow entering arc e = (v, w) at time θ arrives at node w at time θ + τe. → R Each node v is associated w→ithRthree functions; the storage cost cv : [0, T] → R, the storage capacity Uv : [0, T] ≥0, and the supply/demand rate bv : [0, T] . Here cv(θ) is the cost per time unit for storing one unit of ﬂow at node v at time θ and Uv(θ) is an upper bound on the amount of ﬂow that can be stored(cid:82)at|node |v at time θ. Moreover, depending on whether bv(θ) > 0 or bv(θ) < 0, the value bv(θ) de- notes the supply or demand rate of ﬂow at node v at time θ. Thus, the amount of avail- able supply or required demand up to time θ at∈nRode v equals Bv(θ) :(cid:82)= 0θ bv(ϑ) d(ϑ). In addition, there may be an initial storage sv ≥0 at node v. In this case, the total supply or demand at node v up to time θ is given by Bv(θ) := sv + 0θ bv(ϑ) d(ϑ). A ﬂow over time (or simply ﬂow) x is described by Lebesgue-measurable functions −→ R ∀ ∈ xe : [0, T) ≥0 e E . (cid:82) The value xe(θ) denotes the rate of ﬂow entering arc e at the point in time θ. There- fore, the am−ount of ﬂow entering arc e up to time θ equ−als Xe(θ) := 0θ x−e(ϑ) dϑ. We let∈Xe τ to be a shifted function deﬁned by (Xe τ)(θ)−→:=RXe(θ τ) for each θ [0, T). The ﬂow x induces a storage function Yv : [0, T) at node v by the ﬂow conservation constraint (cid:88) (cid:88) − − − Yv := Bv Xe (Xe τe) , (1) ∈ ∈ − e δ+(v) e δ (v) where the value Yv(θ) measures the amount of ﬂow s−tored at node v at time θ. Here and throughout the paper, the notation δ+(v) and δ (v) are used to denote the set of all arcs leaving and entering node v, respectively. Obviously, the functions X, B, Y are absolutely continuous. Moreover, we can assume without loss of generality that U is absolutely continuous as well. That is why we have used a capital letter to denote these functions in order to distinguish them from bounded measurable functions. ##LTLine##

text: assumption

text: makes

text: no

text: restriction

text: and

text: all

text: our

text: results

text: can

text: be

text: extended

text: to

text: the

text: case

text: where

text: cost

text: functions

text: have

text: some

text: discontinuities.

text: Preliminaries

text: In

text: this

text: section,

text: we

text: give

text: a

text: formal

text: description

text: of

text: MCFP

text: and

text: present

text: some

text: existing

text: results,

text: required

text: throughout

text: the

text: paper.

text: We

text: are

text: given

text: a

text: directed

text: graph

text: G

text: (V,

text: E)

text: with

text: node

text: set

text: V

text: and

text: arc

text: set

text: E

text: and

text: a

text: time

text: horizon

text: T

text: We

text: denote

text: an

text: arc

text: e

text: from

text: node

text: v

text: to

text: node

text: w

text: by

text: e

text: (v,

text: w)

text: and

text: assume,

text: without

text: loss

text: of

text: generality,

text: that

text: there

text: is

text: at

text: most

text: one

text: arc

text: between

text: any

text: pair

text: of

text: R

text: nodes

text: in

text: G.

text: Each

text: arc

text: e

text: is

text: associated

text: w→ithRtwo

text: functions;

text: the

text: transit

text: cost

text: ce

text: T]

text: and

text: the

text: transit

text: capacity

text: ue

text: T]

text: Here,

text: ce(θ)

text: gives

text: the

text: cost

text: per

text: ﬂow

text: unit

text: for

text: sending

text: ﬂow

text: in

text: arc

text: e

text: at

text: time

text: θ

text: and

text: ue(θ)

text: gives

text: an

text: upper

text: bound

text: on

text: the

text: rate

text: (i.e.,

text: amount

text: of

text: ﬂow

text: per

text: time

text: unit)

text: at

text: which

text: ﬂow

text: can

text: enter

text: arc

text: e

text: at

text: time

text: θ.

text: In

text: addition,

text: R

text: for

text: each

text: arc

text: e,

text: a

text: transit

text: time

text: τe

text: is

text: given.

text: The

text: transit

text: time

text: is

text: the

text: amount

text: of

text: time

text: required

text: to

text: send

text: ﬂow

text: from

text: the

text: tail

text: to

text: the

text: head

text: of

text: e.

text: Thus

text: ﬂow

text: entering

text: arc

text: e

text: (v,

text: w)

text: at

text: time

text: θ

text: arrives

text: at

text: node

text: w

text: at

text: time

text: θ

text: τe.

text: R

text: Each

text: node

text: v

text: is

text: associated

text: w→ithRthree

text: functions;

text: the

text: storage

text: cost

text: cv

text: T]

text: R,

text: the

text: storage

text: capacity

text: Uv

text: T]

text: and

text: the

text: supply/demand

text: rate

text: bv

text: T]

text: Here

text: cv(θ)

text: is

text: the

text: cost

text: per

text: time

text: unit

text: for

text: storing

text: one

text: unit

text: of

text: ﬂow

text: at

text: node

text: v

text: at

text: time

text: θ

text: and

text: Uv(θ)

text: is

text: an

text: upper

text: bound

text: on

text: the

text: amount

text: of

text: ﬂow

text: that

text: can

text: be

text: |v

text: at

text: time

text: θ.

text: Moreover,

text: depending

text: on

text: whether

text: bv(θ)

text: or

text: bv(θ)

text: the

text: value

text: bv(θ)

text: de-

text: notes

text: the

text: supply

text: or

text: demand

text: rate

text: of

text: ﬂow

text: at

text: node

text: v

text: at

text: time

text: θ.

text: Thus,

text: the

text: amount

text: of

text: avail-

text: able

text: supply

text: or

text: required

text: demand

text: up

text: to

text: time

text: θ

text: at∈nRode

text: v

text: equals

text: Bv(θ)

text: 0θ

text: bv(ϑ)

text: d(ϑ).

text: In

text: addition,

text: there

text: may

text: be

text: an

text: initial

text: storage

text: sv

text: ≥0

text: at

text: node

text: v.

text: In

text: this

text: case,

text: the

text: total

text: supply

text: or

text: demand

text: at

text: node

text: v

text: up

text: to

text: time

text: θ

text: is

text: given

text: by

text: Bv(θ)

text: sv

text: 0θ

text: bv(ϑ)

text: d(ϑ).

text: A

text: ﬂow

text: over

text: time

text: (or

text: simply

text: ﬂow)

text: x

text: is

text: described

text: by

text: Lebesgue-measurable

text: functions

text: R

text: xe

text: T)

text: ≥0

text: e

text: E

text: The

text: value

text: xe(θ)

text: denotes

text: the

text: rate

text: of

text: ﬂow

text: entering

text: arc

text: e

text: at

text: the

text: point

text: in

text: time

text: θ.

text: There-

text: fore,

text: the

text: am−ount

text: of

text: ﬂow

text: entering

text: arc

text: e

text: up

text: to

text: time

text: θ

text: equ−als

text: Xe(θ)

text: 0θ

text: x−e(ϑ)

text: dϑ.

text: We

text: let∈Xe

text: τ

text: to

text: be

text: a

text: shifted

text: function

text: deﬁned

text: by

text: (Xe

text: τ)(θ)−→:=RXe(θ

text: τ)

text: for

text: each

text: θ

text: T).

text: The

text: ﬂow

text: x

text: induces

text: a

text: storage

text: function

text: Yv

text: T)

text: at

text: node

text: v

text: by

text: the

text: ﬂow

text: conservation

text: constraint

text: Yv

text: Bv

text: Xe

text: (Xe

text: τe)

text: e

text: δ+(v)

text: e

text: δ

text: (v)

text: where

text: the

text: value

text: Yv(θ)

text: measures

text: the

text: amount

text: of

text: ﬂow

text: s−tored

text: at

text: node

text: v

text: at

text: time

text: θ.

text: Here

text: and

text: throughout

text: the

text: paper,

text: the

text: notation

text: δ+(v)

text: and

text: δ

text: (v)

text: are

text: used

text: to

text: denote

text: the

text: set

text: of

text: all

text: arcs

text: leaving

text: and

text: entering

text: node

text: v,

text: respectively.

text: Obviously,

text: the

text: functions

text: X,

text: B,

text: Y

text: are

text: absolutely

text: continuous.

text: Moreover,

text: we

text: can

text: assume

text: without

text: loss

text: of

text: generality

text: that

text: U

text: is

text: absolutely

text: continuous

text: as

text: well.

text: That

text: is

text: why

text: we

text: have

text: used

text: a

text: capital

text: letter

text: to

text: denote

text: these

text: functions

text: in

text: order

text: to

text: distinguish

text: them

text: from

text: bounded

text: measurable

text: functions.

text: ##LTLine##


text: Prepared for submission to JHEP Simpliﬁed diﬀerential equations approach for Master Integrals Costas G. Papadopoulos Institute of Nuclear and Particle Physics, NCSR ‘Demokritos’, Agia Paraskevi, 15310, Greece E-mail: costas.papadopoulos@cern.ch Abstract: A simpliﬁed diﬀerential equations approach for Master Integrals is presented. It allows to express them, straightforwardly, in terms of Goncharov Polylogarithms. As a proof-of-concept of the proposed method, results at one and two loops are presented, including the massless one-loop pentagon with up to one oﬀ-shell leg at order epsilon. Keywords: Feynman integrals, QCD, NLO and NNLO Calculations

text: Prepared

label: paragraph

text: for

text: submission

text: to

text: JHEP

text: Simpliﬁed

label: title

text: diﬀerential

text: equations

text: approach

text: for

text: Master

text: Integrals

text: Costas

label: author

text: G.

text: Papadopoulos

text: Institute

text: of

text: Nuclear

text: and

text: Particle

text: Physics,

text: NCSR

text: ‘Demokritos’,

text: Agia

text: Paraskevi,

text: Greece

text: E-mail:

text: costas.papadopoulos@cern.ch

text: Abstract:

text: A

label: abstract

text: simpliﬁed

text: diﬀerential

text: equations

text: approach

text: for

text: Master

text: Integrals

text: is

text: presented.

text: It

text: allows

text: to

text: express

text: them,

text: straightforwardly,

text: in

text: terms

text: of

text: Goncharov

text: Polylogarithms.

text: As

text: a

text: proof-of-concept

text: of

text: the

text: proposed

text: method,

text: results

text: at

text: one

text: and

text: two

text: loops

text: are

text: presented,

text: including

text: the

text: massless

text: one-loop

text: pentagon

text: with

text: up

text: to

text: one

text: oﬀ-shell

text: leg

text: at

text: order

text: epsilon.

text: Keywords:

text: Feynman

text: integrals,

text: QCD,

text: NLO

text: and

text: NNLO

text: Calculations


text: xp1 −p12 p12 − xp1 Figure 1. The one-loop graph with three oﬀ-shell legs. The integrating factor M is given by 4−d 4−d M = x (1 − x) 2 (−m3 + m1x) 2 (cid:16) (cid:17) (cid:0) (cid:1) and the DE takes the form, d = 4 − 2ε, ∂ 1 − − − − MG = c (1 − x) 1+ε (−m + m x) 1+ε −m x2 ε − (−m ) ε (2.7) 111 Γ 3 1 1 3 ∂x (cid:90) ε (cid:0) (cid:1) where we have used the known(cid:16)expression(cid:17)for the two-point function, ddk 1 = c −2 −p2 d/2−2 (2.8) Γ iπd/2 (−k2) − (k + p)2 (d − 3) (d − 4) with Γ (3 − d/2) Γ (d/2 − 1)2 c = (2.9) Γ Γ (d − 3) (cid:90) The left-hand side results to x ∂ dt (MG ) = (MG ) − (MG ) (2.10) ∂t 111 111 x 111 x=0 0 We need therefore, in general, to ﬁx the boundary condition. In the case under consideration we ﬁnd a posteriori that (MG ) = 0. We will see later on how this is justiﬁed and 111 x=0 how we can address this issue in most general cases when the x = 0 term is not vanishing. The right hand side of the equation can now be expanded around ε = 0 and integrated over x. All terms can be brought in(cid:90)the form x 1 dt G (a − , . . . , a , x) n 1 1 t − a n 0 by using partial fractioning and the shuﬄe algebra properties of GPs, resulting to an ex- (cid:90) pression of the MI in terms of GPs. The GPs [30, 31] are deﬁned as follows x 1 G (a , . . . , a , x) = dt G (a − , . . . , a , t) (2.11) n 1 n 1 1 t − a n 0 – 4 – ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

font: default

text: Figure

text: The

label: caption

text: one-loop

text: graph

text: with

text: three

text: oﬀ-shell

text: legs.

text: The

text: integrating

text: factor

text: M

text: is

text: given

text: by

text: M

text: x

text: x)

text: and

text: the

text: DE

text: takes

text: the

text: form,

text: d

text: MG

text: c

text: x)

text: (−m

text: m

text: x)

text: −m

text: ε

text: (−m

text: ε

text: Γ

text: ∂x

text: ε

text: where

text: we

text: have

text: used

text: the

text: the

text: two-point

text: function,

text: ddk

text: c

text: −2

text: Γ

text: (k

text: (d

text: (d

text: with

text: Γ

text: Γ

text: c

text: Γ

text: Γ

text: (d

text: The

text: left-hand

text: side

text: results

text: to

text: x

text: dt

text: (MG

text: (MG

text: (MG

text: ∂t

text: x

text: We

text: need

text: therefore,

text: in

text: general,

text: to

text: ﬁx

text: the

text: boundary

text: condition.

text: In

text: the

text: case

text: under

text: consideration

text: we

text: ﬁnd

text: a

text: posteriori

text: that

text: (MG

text: We

text: will

text: see

text: later

text: on

text: how

text: this

text: is

text: justiﬁed

text: and

text: how

text: we

text: can

text: address

text: this

text: issue

text: in

text: most

text: general

text: cases

text: when

text: the

text: x

text: term

text: is

text: not

text: vanishing.

text: The

text: right

text: hand

text: side

text: of

text: the

text: equation

text: can

text: now

text: be

text: expanded

text: around

text: ε

text: and

text: integrated

text: over

text: x.

text: All

text: terms

text: can

text: be

text: brought

text: form

text: x

text: dt

text: G

text: (a

text: a

text: x)

text: n

text: t

text: a

text: n

text: by

text: using

text: partial

text: fractioning

text: and

text: the

text: shuﬄe

text: algebra

text: properties

text: of

text: GPs,

text: resulting

text: to

text: an

text: ex-

text: pression

text: of

text: the

text: MI

text: in

text: terms

text: of

text: GPs.

text: The

text: GPs

text: are

text: deﬁned

text: as

text: follows

text: x

text: G

text: (a

text: a

text: x)

text: dt

text: G

text: (a

text: a

text: t)

text: n

text: n

text: t

text: a

text: n

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

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: The power spectral density (PSD) S (f) of the received y signal Y (t) is given by The basis functions in (7) are double indexed: the index − nm denotes the n th basis function φ (t) translated by mT − n F{ } in time, i.e., φ (t mT). The choice of using a double index n Sy(f) = Ry(τ) = Sx(f) (cid:63) SejΘ(f) + Sw(f) for basis functions is because orthogonality is also obtained by = e−σ2S (f) + lim S (f) (cid:63) (1 − e−σ2)rect(f/B) translation, as shown in (8). Property (9) states that the pulse x B→∞ x B shaping function g(t) has a non-zero projection only in the ﬁrst + Sw(f), (4) dimension, i.e., for n = 0. This means that φ0m(t) = gm(t). Note that assuming property (9) comes without loss of general- F{·} ity, because we can always obtain all the other basis functions where denotes the Fourier transform and (cid:63) the convo- φ (t) for n > 0 with an orthonormalization procedure. lution operator. Equation (4) shows that the PSD of the input Enxample. A complete orthonormal basis of L2(R) is the signal S (f) experiences a spectral loss [16], that is a gain x − ≤ trigonometric system equal to e σ2 1, and the remaining power proportional to − − (1 e σ2) is spread onto an inﬁnite bandwidth. Later in this { − · · · ∈ Z} paper we will see that when using projection receivers the φ (t) = φ (t mT), n = 0, 1, ; m , (10) nm n spectral loss is unavoidable. III. SYSTEM MODEL (cid:18) (cid:19) where Consider linear modulation for which we express the output of the continuous-time white phase noise channel as √1 2π φ (t) = exp j nt (11) (cid:88) n T T Y (t) = X(t)ejΘ(t) + W(t) ≤ (cid:88) − for 0 t < T andφn(t) is zero elsewhere. The square = A g(t kT)ejΘ(t) + W(t) pulse shaping ﬁlter  k √ k  ≤ = A g (t)ejΘ(t) + W(t), (5) 1/ T 0 t < T k k g (t) = (12) k 0 0 otherwise { } where A is a sequence of independent and identically k distributed (iid) random variables, T is the symbol period, j is such that (6) and (9) are satisﬁed. i{s the i}maginary unit, g(t) is the pulse shaping ﬁltRer such that The phase noise process Θ is deﬁned as a stationary random gk(t) is a set of orthonormal functions of L2( ) with the process such that  property (cid:90)  (cid:104)(cid:68) (cid:69)(cid:105)  ∞   1 k = l (cid:44) · 1 n = 0, m = k −∞ gk(t)gl(cid:63)(t) dt = 0 k (cid:54)= l (6) E gk(t)ejΘ(t), φnm(t) µΘ 0 otherwise, (13) (cid:104)(cid:68) (cid:69) (cid:68) (cid:69)(cid:105) where the superscript (cid:63) denotes complex conjugate, and W is a complex-valued circularly symmetric white Gaussian  noise. Let  · − E g (t)ejΘ(t), φ (t) g (cid:48)(s)e jΘ(s), φ (cid:48) (cid:48)(s) k nm k n m {φnm(t), n = 0, 1, . . . ; m ∈ Z} (7) (cid:44) | | ·  1 n = n(cid:48) = 0, m = k, m(cid:48) = k(cid:48), µ 2 (14) Θ (cid:2) (cid:3) 0 otherwise, R be a complete orthonormal basis of L2( ) with − (cid:104)(cid:68) (cid:69)(cid:105) φnm(cid:90)(t) = φn(t mT) and such that where µΘ = E ejΘ(t) . Note that (13) and (14) give ∞  (cid:48) (cid:48) Var g (t)ejΘ(t), φ (t) = 0 (15) 1 n = n , m = m k nm φ (t)φ(cid:63)(cid:48) (cid:48)(t) dt = (8) (cid:10) (cid:11) −∞ nm n m 0 otherwise, for any choice of k, n, and m. In other words, we can view  and (cid:90)  the projections gk(t)ejΘ(t), φnm(t) as constants. Deﬁning the phase noise process through (13)-(15) is rea- ∞  sonable if we interpret the model (5) as the limit of successive 1 n = 0, m = k −∞ gk(t)φ(cid:63)nm(t) dt = 0 otherwise. (9) rtiemﬁneemmeondtesl,ofcaonrseildaeterdtdhiescﬁrentiet-etiminetemrvoadlel[.−FSo,rSth] eadnidscrtiemtee- ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: The

text: power

text: spectral

text: density

text: (PSD)

text: S

text: (f)

text: of

text: the

text: received

text: y

text: signal

text: Y

text: (t)

text: is

text: given

text: by

text: The

text: basis

text: functions

text: in

text: are

text: double

text: indexed:

text: the

text: index

text: nm

text: denotes

text: the

text: n

text: th

text: basis

text: function

text: φ

text: (t)

text: translated

text: by

text: mT

text: n

text: F{

label: equation

text: in

text: time,

text: i.e.,

text: φ

text: (t

text: mT).

text: The

text: choice

text: of

text: using

text: a

text: double

text: index

text: n

text: Sy(f)

text: Ry(τ)

text: Sx(f)

text: SejΘ(f)

text: Sw(f)

text: for

text: basis

text: functions

text: is

text: because

text: orthogonality

text: is

text: also

text: obtained

text: by

text: (f)

text: lim

text: S

text: (f)

text: translation,

text: as

text: shown

text: in

text: Property

text: states

text: that

text: the

text: pulse

text: x

text: B→∞

text: x

text: B

text: shaping

text: function

text: g(t)

text: has

text: a

text: non-zero

text: projection

text: only

text: in

text: the

text: ﬁrst

text: Sw(f),

text: dimension,

text: i.e.,

text: for

text: n

text: This

text: means

text: that

text: gm(t).

text: Note

text: that

text: assuming

text: property

text: comes

text: without

text: loss

text: of

text: general-

text: F{·}

text: ity,

text: because

text: we

text: can

text: always

text: obtain

text: all

text: the

text: other

text: basis

text: functions

text: where

text: denotes

text: the

text: Fourier

text: transform

text: and

text: the

text: convo-

text: φ

text: (t)

text: for

text: n

text: with

text: an

text: orthonormalization

text: procedure.

text: lution

text: operator.

text: Equation

text: shows

text: that

text: the

text: PSD

text: of

text: the

text: input

text: Enxample.

text: A

text: complete

text: orthonormal

text: basis

text: of

text: is

text: the

text: signal

text: S

text: (f)

text: experiences

text: a

text: spectral

text: loss

text: that

text: is

text: a

text: gain

text: x

text: trigonometric

text: system

text: equal

text: to

text: e

text: σ2

text: and

text: the

text: remaining

text: power

text: proportional

text: to

text: e

text: is

text: spread

text: onto

text: an

text: inﬁnite

text: bandwidth.

text: Later

text: in

text: this

text: Z}

text: paper

text: we

text: will

text: see

text: that

text: when

text: using

text: projection

text: receivers

text: the

text: φ

text: (t)

text: φ

text: (t

text: mT),

text: n

text: m

text: nm

text: n

text: spectral

text: loss

text: is

text: unavoidable.

text: III.

text: SYSTEM

text: MODEL

text: where

text: Consider

text: linear

text: modulation

text: for

text: which

text: we

text: express

text: the

text: output

text: of

text: the

text: continuous-time

text: white

text: phase

text: noise

text: channel

text: as

text: √1

text: 2π

text: φ

text: (t)

text: exp

text: j

text: nt

text: n

text: T

text: T

text: Y

text: (t)

text: X(t)ejΘ(t)

text: W(t)

text: for

text: t

text: T

text: andφn(t)

text: is

text: zero

text: elsewhere.

text: The

text: square

text: A

text: g(t

text: kT)ejΘ(t)

text: W(t)

text: pulse

text: shaping

text: ﬁlter

text: k

text: k

text: A

text: g

text: (t)ejΘ(t)

text: W(t),

text: T

text: t

text: T

text: k

text: k

text: g

text: (t)

text: k

text: otherwise

text: where

text: A

text: is

text: a

text: sequence

text: of

text: independent

text: and

text: identically

text: k

text: distributed

text: (iid)

text: random

text: variables,

text: T

text: is

text: the

text: symbol

text: period,

text: j

text: is

text: such

text: that

text: and

text: are

text: satisﬁed.

text: i{s

text: the

text: i}maginary

text: unit,

text: g(t)

text: is

text: the

text: pulse

text: shaping

text: ﬁltRer

text: such

text: that

text: The

text: phase

text: noise

text: process

text: Θ

text: is

text: deﬁned

text: as

text: a

text: stationary

text: random

text: gk(t)

text: is

text: a

text: set

text: of

text: orthonormal

text: functions

text: of

text: with

text: the

text: process

text: such

text: that

text: property

text: k

text: l

text: n

text: m

text: k

text: dt

text: k

text: l

text: E

text: gk(t)ejΘ(t),

text: φnm(t)

text: µΘ

text: otherwise,

text: where

text: the

text: superscript

text: denotes

text: complex

text: conjugate,

text: and

text: W

text: is

text: a

text: complex-valued

text: circularly

text: symmetric

text: white

text: Gaussian

text: noise.

text: Let

text: E

text: g

text: (t)ejΘ(t),

text: φ

text: (t)

text: g

text: jΘ(s),

text: φ

text: k

text: nm

text: k

text: n

text: m

text: {φnm(t),

text: n

text: m

text: Z}

text: n

text: m

text: k,

text: µ

text: Θ

text: otherwise,

text: R

text: be

text: a

text: complete

text: orthonormal

text: basis

text: of

text: with

text: φn(t

text: mT)

text: and

text: such

text: that

text: where

text: µΘ

text: E

text: ejΘ(t)

text: Note

text: that

text: and

text: give

text: Var

text: g

text: (t)ejΘ(t),

text: φ

text: (t)

text: n

text: n

text: m

text: m

text: k

text: nm

text: φ

text: dt

text: nm

text: n

text: m

text: otherwise,

text: for

text: any

text: choice

text: of

text: k,

text: n,

text: and

text: m.

text: In

text: other

text: words,

text: we

text: can

text: view

text: and

text: the

text: projections

text: gk(t)ejΘ(t),

text: φnm(t)

text: as

text: constants.

text: Deﬁning

text: the

text: phase

text: noise

text: process

text: through

text: is

text: rea-

text: sonable

text: if

text: we

text: interpret

text: the

text: model

text: as

text: the

text: limit

text: of

text: successive

text: n

text: m

text: k

text: dt

text: otherwise.

text: eadnidscrtiemtee-

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: communication systems based on direct detection, e.g., when (cid:68) (cid:69) (cid:104) (cid:105) the front-end is a photodiode that performs photon counting, Y = Y (t), φ (t) (26) nm (cid:88) (cid:68)nm (cid:69) the numbers of photons being proportional to the energy the = X(t)ejΘ(t) + W(t), φ (t) (27) photodiode harvests. The output of the photodiode is usually nm modeled as the modulus-square of the ﬁeld at the input, so (cid:90) = A(cid:88) g (t)ejΘ(t), φ (t) + W (28) in principle the phase noise would not be an issue. But real k k nm nm k ∞ photodiodes are bandlimited and should be modeled as being a=.s. µ A g (t)φ(cid:63) (t) dt + W (29) preceded by a bandpass ﬁlter that reduces the energy collected Θ k −∞ k nm nm by the receiver, and the presence of these ﬁlters will cause k SNR loss. where the W ’s are iid circularly-symmetric Gaussian VI. CONCLUSION nm variates, and the last step follows by the Lemma in the We have discussed the modeling of the continuous-time previous section. Byusing (9) in (29) we have AWGN channel in the presence of white (memoryless) phase  noise. We have found that, under mild conditions, the sufﬁcient µ A + W n = 0, statistic for this channel is the output of a baud-sampled Y a=.s. Θ m nm (30) nm matched ﬁlter, and that the channel is equivalent to a discrete- W n > 0. nm time AWGN channel with an SNR penalty. Since Y does not carry information about the input A ACKNOWLEDGMENT nm m for n > 0, and the sequences of random variables converge L. Barletta was supported by Technische Universita¨t almost surely to their limits, we have Mu¨nchen — Institute for Advanced Study, funded by the German Excellence Initiative. G. Kramer was supported by an Alexander von Humboldt Professorship endowed by the I(X; Y ) = Mli→m∞ 2M1+ 1I((cid:88)X0M; Y0M) (31) German Federal Ministry of Education and Research. REFERENCES M 1 = Mli→m∞ 2M + 1 − I(X0m; Y0m) (32) [1] Gof. cFoohsecrheinnti,liLg.htGwraeveensstieginna,lsancdorGru.pVteadnnbuyccpih, a“sNeonnocioshe,e”reInEtEdEetTercatinosn. m= M Commun., vol. 36, no. 3, pp. 306–314, 1988. = I(X ; Y ) = I(A ; Y ) (33) 00 00 0 00 [2] R. Essiambre, G. Kramer, P. Winzer, G. Foschini, and B. Goebel, “Capacity limits of optical ﬁber networks,” J. Lightwave Technol., vol. 28, no. 4, pp. 662–701, 2010. where (32) follows because the channel is memoryless [3] A. Spalvieri and L. Barletta, “Pilot-aided carrier recovery in the presence by (30), and (33) follows by stationarity and by (25). The of phase noise,” IEEE Trans. Commun., vol. 59, no. 7, pp. 1966–1974, 2011. result (33) shows that a sufﬁcient statistic for inferring A k [4] L. Barletta, M. Magarini, and A. Spalvieri, “The information rate given Y is transferred through the discrete-time Wiener’s phase noise channel,” J. Lightwave Technol., vol. 30, no. 10, pp. 1480–1486, 2012. (cid:104) (cid:105) (cid:104) (cid:105) [5] H. Ghozlan and G. Kramer, “Multi-sample receivers increase informa- Y0k = Y (t), φ0k(t) = Y (t), gk(t) (34) tion rates for Wiener phase noise channels,” in Global Telecom. Conf. (GLOBECOM), Dec. 2013, pp. 1919–1924. [6] ——, “On Wiener phase noise channels at high signal-to-noise ratio,” that is the output of the sampled ﬁlter that is matched to in IEEE Int. Symp. Inf. Theory (ISIT), 2013, pp. 2279–2283. g(t). [7] ——, “Phase modulation for discrete-time Wiener phase noise channels with oversampling at high SNR,” in IEEE Int. Symp. Inf. Theory (ISIT), V. DISCUSSION 2014. By virtue of (30), at the output of the sampled matched ﬁlter [8] M. Katz and S. Shamai, “On the capacity-achieving distribution of the discrete-time noncoherent and partially coherent AWGN channels,” the continuous-time white phase noise channel is equivalent IEEE Trans. Inf. Theory, vol. 50, no. 10, pp. 2257–2270, 2004. to a discrete-time AWGN channel [9] A. Lapidoth, “On phase noise channels at high SNR,” in IEEE Inf. Theory Workshop, 2002, pp. 1–4. [10] L. Barletta, M. Magarini, and A. Spalvieri, “Estimate of information Y0k = µΘAk + W0k (35) rates of discrete-time ﬁrst-order Markov phase noise channels,” IEEE Photon. Technol. Lett., vol. 23, no. 21, pp. 1582–1584, 2011. [11] A. Barbieri and G. Colavolpe, “On the information rate and repeat- so the effect of the spectral loss µ is to reduce the SNR. In accumulate code design for phase noise channels,” IEEE Trans. Com- → Θ mun., vol. 59, no. 12, pp. 3223–3228, 2011. the limit of µ 0, reliable communication over this channel Θ [12] L. Barletta and G. Kramer, “Signal-to-noise ratio penalties for phase is not possible. noise channels,” in Intern. Conf. on Cognitive Radio Oriented Wirel. We conclude that the presence of rapidly varying Networks (CROWNCOM 2014), Jun. 2014. [13] L. Barletta, M. Magarini, and A. Spalvieri, “Tight upper and lower continuous-time phase noise affects not only the information bounds to the information rate of the phase noise channel,” in IEEE encoded in the phase of X(t), but also the information Int. Symp. Inf. Theory (ISIT), 2013, pp. 2284–2288. encoded in its amplitude. We further conclude that even a [14] L. Barletta, M. Magarini, S. Pecorino, and A. Spalvieri, “Upper and lower bounds to the information rate transferred through ﬁrst-order noncoherent receiver is affected by white phase noise and Markov channels with free-running continuous state,” IEEE Trans. Inf. suffers from an SNR loss. This is true also for ﬁber-optic Theory, 2014, forthcoming. ##LTLine## ##LTLine##

text: communication

text: systems

text: based

text: on

text: direct

text: detection,

text: e.g.,

text: when

text: the

text: front-end

text: is

text: a

text: photodiode

text: that

text: performs

text: photon

text: counting,

text: Y

text: Y

text: (t),

text: φ

text: (t)

text: nm

text: the

text: numbers

text: of

text: photons

text: being

text: proportional

text: to

text: the

text: energy

text: the

text: X(t)ejΘ(t)

text: W(t),

text: φ

text: (t)

text: photodiode

text: harvests.

text: The

text: output

text: of

text: the

text: photodiode

text: is

text: usually

text: nm

text: modeled

text: as

text: the

text: modulus-square

text: of

text: the

text: ﬁeld

text: at

text: the

text: input,

text: so

text: g

text: (t)ejΘ(t),

text: φ

text: (t)

text: W

text: in

text: principle

text: the

text: phase

text: noise

text: would

text: not

text: be

text: an

text: issue.

text: But

text: real

text: k

text: k

text: nm

text: nm

text: k

text: photodiodes

text: are

text: bandlimited

text: and

text: should

text: be

text: modeled

text: as

text: being

text: a=.s.

text: µ

text: A

text: g

text: (t)

text: dt

text: W

text: preceded

text: by

text: a

text: bandpass

text: ﬁlter

text: that

text: reduces

text: the

text: energy

text: collected

text: Θ

text: k

text: k

text: nm

text: nm

text: by

text: the

text: receiver,

text: and

text: the

text: presence

text: of

text: these

text: ﬁlters

text: will

text: cause

text: k

text: SNR

text: loss.

text: where

text: the

text: W

text: ’s

text: are

text: iid

text: circularly-symmetric

text: Gaussian

text: VI.

text: CONCLUSION

text: nm

text: variates,

text: and

text: the

text: last

text: step

text: follows

text: by

text: the

text: Lemma

text: in

text: the

text: We

text: have

text: discussed

text: the

text: modeling

text: of

text: the

text: continuous-time

text: previous

text: section.

text: Byusing

text: in

text: we

text: have

text: AWGN

text: channel

text: in

text: the

text: presence

text: of

text: white

text: (memoryless)

text: phase

text: noise.

text: We

text: have

text: found

text: that,

text: under

text: mild

text: conditions,

text: the

text: sufﬁcient

text: µ

text: A

text: W

text: n

text: statistic

text: for

text: this

text: channel

text: is

text: the

text: output

text: of

text: a

text: baud-sampled

text: Y

text: a=.s.

text: Θ

text: m

text: nm

text: nm

text: matched

text: ﬁlter,

text: and

text: that

text: the

text: channel

text: is

text: equivalent

text: to

text: a

text: discrete-

text: W

text: n

text: nm

text: time

text: AWGN

text: channel

text: with

text: an

text: SNR

text: penalty.

text: Since

text: Y

text: does

text: not

text: carry

text: information

text: about

text: the

text: input

text: A

text: ACKNOWLEDGMENT

text: nm

text: m

text: for

text: n

text: and

text: the

text: sequences

text: of

text: random

text: variables

text: converge

text: L.

text: Barletta

text: was

text: supported

text: by

text: Technische

text: Universita¨t

text: almost

text: surely

text: to

text: their

text: limits,

text: we

text: have

text: Mu¨nchen

text: Institute

text: for

text: Advanced

text: Study,

text: funded

text: by

text: the

text: German

text: Excellence

text: Initiative.

text: G.

text: Kramer

text: was

text: supported

text: by

text: an

text: Alexander

text: von

text: Humboldt

text: Professorship

text: endowed

text: by

text: the

text: I(X;

text: Y

text: Mli→m∞

text: German

text: Federal

text: Ministry

text: of

text: Education

text: and

text: Research.

text: REFERENCES

text: M

text: Mli→m∞

text: Gof.

text: m=

text: M

text: Commun.,

text: vol.

text: no.

text: pp.

text: I(X

text: Y

text: I(A

text: Y

text: R.

text: Essiambre,

text: G.

text: Kramer,

text: P.

text: Winzer,

text: G.

text: Foschini,

text: and

text: B.

text: Goebel,

text: “Capacity

text: limits

text: of

text: optical

text: ﬁber

text: networks,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: pp.

text: where

text: follows

text: because

text: the

text: channel

text: is

text: memoryless

text: A.

text: Spalvieri

text: and

text: L.

text: Barletta,

text: “Pilot-aided

text: carrier

text: recovery

text: in

text: the

text: presence

text: by

text: and

text: follows

text: by

text: stationarity

text: and

text: by

text: The

text: of

text: phase

text: noise,”

text: IEEE

text: Trans.

text: Commun.,

text: vol.

text: no.

text: pp.

text: result

text: shows

text: that

text: a

text: sufﬁcient

text: statistic

text: for

text: inferring

text: A

text: k

text: L.

text: Barletta,

text: M.

text: Magarini,

text: and

text: A.

text: Spalvieri,

text: “The

text: information

text: rate

text: given

text: Y

text: is

text: transferred

text: through

text: the

text: discrete-time

text: Wiener’s

text: phase

text: noise

text: channel,”

text: J.

text: Lightwave

text: Technol.,

text: vol.

text: no.

text: pp.

text: H.

text: Ghozlan

text: and

text: G.

text: Kramer,

text: “Multi-sample

text: receivers

text: increase

text: informa-

text: Y

text: (t),

text: Y

text: (t),

text: gk(t)

text: tion

text: rates

text: for

text: Wiener

text: phase

text: noise

text: channels,”

text: in

text: Global

text: Telecom.

text: Conf.

text: (GLOBECOM),

text: Dec.

text: pp.

text: “On

text: Wiener

text: phase

text: noise

text: channels

text: at

text: high

text: signal-to-noise

text: ratio,”

text: that

text: is

text: the

text: output

text: of

text: the

text: sampled

text: ﬁlter

text: that

text: is

text: matched

text: to

text: in

text: IEEE

text: Int.

text: Symp.

text: Inf.

text: Theory

text: (ISIT),

text: pp.

text: g(t).

text: “Phase

text: modulation

text: for

text: discrete-time

text: Wiener

text: phase

text: noise

text: channels

text: with

text: oversampling

text: at

text: high

text: SNR,”

text: in

text: IEEE

text: Int.

text: Symp.

text: Inf.

text: Theory

text: (ISIT),

text: V.

text: DISCUSSION

text: By

text: virtue

text: of

text: at

text: the

text: output

text: of

text: the

text: sampled

text: matched

text: ﬁlter

text: M.

text: Katz

text: and

text: S.

text: Shamai,

text: “On

text: the

text: capacity-achieving

text: distribution

text: of

text: the

text: discrete-time

text: noncoherent

text: and

text: partially

text: coherent

text: AWGN

text: channels,”

text: the

text: continuous-time

text: white

text: phase

text: noise

text: channel

text: is

text: equivalent

text: IEEE

text: Trans.

text: Inf.

text: Theory,

text: vol.

text: no.

text: pp.

text: to

text: a

text: discrete-time

text: AWGN

text: channel

text: A.

text: Lapidoth,

text: “On

text: phase

text: noise

text: channels

text: at

text: high

text: SNR,”

text: in

text: IEEE

text: Inf.

text: Theory

text: Workshop,

text: pp.

text: L.

text: Barletta,

text: M.

text: Magarini,

text: and

text: A.

text: Spalvieri,

text: “Estimate

text: of

text: information

text: µΘAk

text: rates

text: of

text: discrete-time

text: ﬁrst-order

text: Markov

text: phase

text: noise

text: channels,”

text: IEEE

text: Photon.

text: Technol.

text: Lett.,

text: vol.

text: no.

text: pp.

text: A.

text: Barbieri

text: and

text: G.

text: Colavolpe,

text: “On

text: the

text: information

text: rate

text: and

text: repeat-

text: so

text: the

text: effect

text: of

text: the

text: spectral

text: loss

text: µ

text: is

text: to

text: reduce

text: the

text: SNR.

text: In

text: accumulate

text: code

text: design

text: for

text: phase

text: noise

text: channels,”

text: IEEE

text: Trans.

text: Com-

text: Θ

text: mun.,

text: vol.

text: no.

text: pp.

text: the

text: limit

text: of

text: µ

text: reliable

text: communication

text: over

text: this

text: channel

text: Θ

text: L.

text: Barletta

text: and

text: G.

text: Kramer,

text: “Signal-to-noise

text: ratio

text: penalties

text: for

text: phase

text: is

text: not

text: possible.

text: noise

text: channels,”

text: in

text: Intern.

text: Conf.

text: on

text: Cognitive

text: Radio

text: Oriented

text: Wirel.

text: We

text: conclude

text: that

text: the

text: presence

text: of

text: rapidly

text: varying

text: Networks

text: (CROWNCOM

text: Jun.

text: L.

text: Barletta,

text: M.

text: Magarini,

text: and

text: A.

text: Spalvieri,

text: “Tight

text: upper

text: and

text: lower

text: continuous-time

text: phase

text: noise

text: affects

text: not

text: only

text: the

text: information

text: bounds

text: to

text: the

text: information

text: rate

text: of

text: the

text: phase

text: noise

text: channel,”

text: in

text: IEEE

text: encoded

text: in

text: the

text: phase

text: of

text: X(t),

text: but

text: also

text: the

text: information

text: Int.

text: Symp.

text: Inf.

text: Theory

text: (ISIT),

text: pp.

text: encoded

text: in

text: its

text: amplitude.

text: We

text: further

text: conclude

text: that

text: even

text: a

text: L.

text: Barletta,

text: M.

text: Magarini,

text: S.

text: Pecorino,

text: and

text: A.

text: Spalvieri,

text: “Upper

text: and

text: lower

text: bounds

text: to

text: the

text: information

text: rate

text: transferred

text: through

text: ﬁrst-order

text: noncoherent

text: receiver

text: is

text: affected

text: by

text: white

text: phase

text: noise

text: and

text: Markov

text: channels

text: with

text: free-running

text: continuous

text: state,”

text: IEEE

text: Trans.

text: Inf.

text: suffers

text: from

text: an

text: SNR

text: loss.

text: This

text: is

text: true

text: also

text: for

text: ﬁber-optic

text: Theory,

text: forthcoming.

text: ##LTLine##

text: ##LTLine##


text: ak ak−1 v1 a1 v k a 2 a 3 Figure 3: Train algorithm: the train a , . . . , a moving unidirectionally with speed v and the bidirectional 2 k k agent a with speed v . 1 1 For our speed setting, we also have 2 1 idle(A ) = , and idle(A ) = . 1 2 a + (k − 1)b kb Write t = a/b. It can be checked that for k ≥ 4, idle(A ) ≤ idle(A ) and idle(A ) ≤ idle(A ) √ 3 1 3 2 when a2 − b2 − 4ab ≥ 0, i.e., t ≥ 2 + 5. In particular, for a = 1, and b = 1/k (note that a ≤ kb), we have 2 2 idle(A3) = 1 − 1/k2 + 2(k − 2)/k k−→→∞ 3, while 2 1 idle(A1) = −→→∞ 1, and idle(A2) = = 1. 1 + (k − 1)/k k k(1/k) Useless agents for circle patrolling. Czyzowicz et al. [7] showed that for k = 2 there are maximum speeds for which an optimal schedule does not use one of the agents. Here we extend this result for all k ≥ 2: Proposition 2. (i) For every k ≥ 2, there exist maximum speeds v ≥ v ≥ . . . ≥ v > 0 and 1 2 k an optimal schedule for the circle with these speeds that does not use up to k − 1 of the agents a , . . . , a . 2 k (ii) In contrast, for a segment, any optimal schedule must use all agents. Proof. (i) Let v = 1 and v = . . . = v = ε/k, for a small positive ε ≤ 1/300, and C be a unit 1 2 k circle. Obviously by using agent a alone (moving perpetually clockwise) we can achieve unit idle 1 time. Assume for contradiction that there exists a schedule achieving an idle time less than 1. Let a (t) = t mod 1 denote the position of agent a at time t. Assume without loss of generality that 1 1 a (0) = 0 and consider the time interval [0, 2]. For 2 ≤ i ≤ k, let J be the interval of points visited 1 i by agent a during the time interval [0, 2], and put J = ∪k J . We have |J | ≤ 2ε/k, thus |J| ≤ 2ε. i i=2 i i We make the following observations: 1. a (1) ∈ [−2ε, 2ε]. Indeed, if a (1) ∈/ [−2ε, 2ε], then either some point in [−2ε, 2ε] is not visited 1 1 by any agent during the time interval [0, 1], or some point in C \ [−2ε, 2ε] is not visited by any agent during the time interval [0, 1]. 8 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: ak

text: v

text: k

text: a

text: a

text: Figure

text: Train

text: algorithm:

text: the

text: train

text: a

text: a

text: moving

text: unidirectionally

text: with

text: speed

text: v

text: and

text: the

text: bidirectional

text: k

text: k

text: agent

text: a

text: with

text: speed

text: v

text: For

text: our

text: speed

text: setting,

text: we

text: also

text: have

text: idle(A

text: and

text: idle(A

text: a

text: (k

text: kb

text: Write

text: t

text: a/b.

text: It

text: can

text: be

text: checked

text: that

text: for

text: k

text: idle(A

text: idle(A

text: and

text: idle(A

text: idle(A

text: when

text: i.e.,

text: t

text: In

text: particular,

text: for

text: a

text: and

text: b

text: (note

text: that

text: a

text: kb),

text: we

text: have

text: k−→→∞

text: while

text: and

text: (k

text: k

text: Useless

text: agents

text: for

text: circle

text: patrolling.

text: Czyzowicz

text: et

text: al.

text: showed

text: that

text: for

text: k

text: there

text: are

text: maximum

text: speeds

text: for

text: which

text: an

text: optimal

text: schedule

text: does

text: not

text: use

text: one

text: of

text: the

text: agents.

text: Here

text: we

text: extend

text: this

text: result

text: for

text: all

text: k

text: Proposition

text: (i)

text: For

text: every

text: k

text: there

text: exist

text: maximum

text: speeds

text: v

text: v

text: v

text: and

text: k

text: an

text: optimal

text: schedule

text: for

text: the

text: circle

text: with

text: these

text: speeds

text: that

text: does

text: not

text: use

text: up

text: to

text: k

text: of

text: the

text: agents

text: a

text: a

text: k

text: (ii)

text: In

text: contrast,

text: for

text: a

text: segment,

text: any

text: optimal

text: schedule

text: must

text: use

text: all

text: agents.

text: Proof.

text: (i)

text: Let

text: v

text: and

text: v

text: v

text: ε/k,

text: for

text: a

text: small

text: positive

text: ε

text: and

text: C

text: be

text: a

text: unit

text: k

text: circle.

text: Obviously

text: by

text: using

text: agent

text: a

text: alone

text: (moving

text: perpetually

text: clockwise)

text: we

text: can

text: achieve

text: unit

text: idle

text: time.

text: Assume

text: for

text: contradiction

text: that

text: there

text: exists

text: a

text: schedule

text: achieving

text: an

text: idle

text: time

text: less

text: than

text: Let

text: a

text: (t)

text: t

text: mod

text: denote

text: the

text: position

text: of

text: agent

text: a

text: at

text: time

text: t.

text: Assume

text: without

text: loss

text: of

text: generality

text: that

text: a

text: and

text: consider

text: the

text: time

text: interval

text: For

text: i

text: k,

text: let

text: J

text: be

text: the

text: interval

text: of

text: points

text: visited

text: i

text: by

text: agent

text: a

text: during

text: the

text: time

text: interval

text: and

text: put

text: J

text: ∪k

text: J

text: We

text: have

text: |J

text: thus

text: |J|

text: i

text: i

text: i

text: We

text: make

text: the

text: following

text: observations:

text: a

text: Indeed,

text: if

text: a

text: then

text: either

text: some

text: point

text: in

text: is

text: not

text: visited

text: by

text: any

text: agent

text: during

text: the

text: time

text: interval

text: or

text: some

text: point

text: in

text: C

text: is

text: not

text: visited

text: by

text: any

text: agent

text: during

text: the

text: time

text: interval

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: 2. a has done almost a complete (say, clockwise) rotation along C during the time interval 1 [0, 1], i.e., it starts at 0 ∈ [−2ε, 2ε] and ends in [−2ε, 2ε], otherwise some point in C \[−2ε, 2ε] is not visited during the time interval [0, 1]. 3. a (2) ∈ [−4ε, 4ε], by a similar argument. 1 4. a has done almost a complete rotation along C during the time interval [1, 2], i.e., it starts 1 in [−2ε, 2ε] and ends in [−4ε, 4ε]. Moreover this rotation must be in the same clockwise sense as the previous one, since otherwise there would exist points not visited for at least one unit of time. Pick three points x , x , x ∈ C\J close to 1/4, 2/4, and 3/4, respectively, i.e., |x −i/4| ≤ 1/100, 1 2 3 i for i = 1, 2, 3. By Observations 2 and 4, these three points must be visited by a in the ﬁrst two 1 rotations during the time interval [0, 2] in the order x , x , x , x , x , x . Since a has unit speed, 1 2 3 1 2 3 1 successive visits to x are separated in time by at least one time unit, contradicting the assumption 1 that the idle time of the schedule is less than 1. (ii) Given v ≥ v ≥ . . . ≥ v > 0, assume for contradiction that there is an optimal guarding 1 2 k schedule with unit idle time for a segment s of maximum length that does not use agent a (with j maximum speed v ), for some 1 ≤ j ≤ k. Extend s at one end by a subsegment of length v /2 j j and assign a to this subsegment to move back and forth from one end to the other, perpetually. j We now have a guarding schedule with unit idle time for a segment longer than s, which is a contradiction. Overtaking other agents. Consider an optimal schedule for circle patrolling (with unit idle time) for the agents in the proof of Proposition 2, with v = 1 and v = . . . = v = ε/k, in 1 2 k which all agents move clockwise at their maximum speeds. Obviously a will overtake all other 1 agents during the time interval [0, 2]. Thus there exist settings in which if all k agents are used by a patrolling algorithm, then some agent(s) need to overtake (pass) other agent(s). Observe however that overtaking can be easily avoided in this setting by not making use of any of the agents a , . . . , a . 2 k 4 An Improved Idle Time for Open Fence Patrolling Kawamura and Kobayashi [9] showed that algorithm A by Czyzowicz et al. [7] does not always 1 produce an optimal schedule for open fence patrolling. They presented two counterexamples: their ﬁrst example uses 6 agents and achieves an idle time of 41 idle(A ); their second example uses 42 1 9 agents and achieves an idle time of 99 idle(A ). By replicating the strategy from the second 100 1 example with a number of agents larger than 9, i.e., iteratively using blocks of agents, we improve the ratio to 24/25 + ε for any ε > 0. We need two technical lemmas to verify this claim. Lemma 2. Consider a segment of length L = 25 such that three agents a , a , a are patrolling 3 1 2 3 perpetually each with speed of 5 and generating an alternating sequence of uncovered triangles T , T , T , T , . . ., as shown in the position-time diagram in Fig. 4. Denote the vertical distances 2 1 2 1 between consecutive occurrences of T and T by δ and between consecutive occurrences of T and 1 2 12 2 T by δ . Denote the bases of T and T by b and b respectively, and the heights of T and T by 1 21 1 2 1 2 1 2 h and h respectively. Then 1 2 (i) 10 is a period of the schedule. 3 (ii) T and T are congruent; further, b = b = 1, δ = δ = 4, and h = h = 5. 1 2 1 2 3 12 21 3 1 2 6 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: list

text: a

text: has

text: done

text: almost

text: a

text: complete

text: (say,

text: clockwise)

text: rotation

text: along

text: C

text: during

text: the

text: time

text: interval

text: i.e.,

text: it

text: starts

text: at

text: and

text: ends

text: in

text: otherwise

text: some

text: point

text: in

text: C

text: is

text: not

text: visited

text: during

text: the

text: time

text: interval

text: a

text: by

text: a

text: similar

text: argument.

text: a

text: has

text: done

text: almost

text: a

text: complete

text: rotation

text: along

text: C

text: during

text: the

text: time

text: interval

text: i.e.,

text: it

text: starts

text: in

text: and

text: ends

text: in

text: Moreover

text: this

text: rotation

text: must

text: be

text: in

text: the

text: same

text: clockwise

text: sense

text: as

text: the

text: previous

text: one,

text: since

text: otherwise

text: there

text: would

text: exist

text: points

text: not

text: visited

text: for

text: at

text: least

text: one

text: unit

text: of

text: time.

text: Pick

text: three

text: points

text: x

text: x

text: x

text: C\J

text: close

text: to

text: and

text: respectively,

text: i.e.,

text: |x

text: i

text: for

text: i

text: By

text: Observations

text: and

text: these

text: three

text: points

text: must

text: be

text: visited

text: by

text: a

text: in

text: the

text: ﬁrst

text: two

text: rotations

text: during

text: the

text: time

text: interval

text: in

text: the

text: order

text: x

text: x

text: x

text: x

text: x

text: x

text: Since

text: a

text: has

text: unit

text: speed,

text: successive

text: visits

text: to

text: x

text: are

text: separated

text: in

text: time

text: by

text: at

text: least

text: one

text: time

text: unit,

text: contradicting

text: the

text: assumption

text: that

text: the

text: idle

text: time

text: of

text: the

text: schedule

text: is

text: less

text: than

text: (ii)

text: Given

text: v

text: v

text: v

text: assume

text: for

text: contradiction

text: that

text: there

text: is

text: an

text: optimal

text: guarding

text: k

text: schedule

text: with

text: unit

text: idle

text: time

text: for

text: a

text: segment

text: s

text: of

text: maximum

text: length

text: that

text: does

text: not

text: use

text: agent

text: a

text: (with

text: j

text: maximum

text: speed

text: v

text: for

text: some

text: j

text: k.

text: Extend

text: s

text: at

text: one

text: end

text: by

text: a

text: subsegment

text: of

text: length

text: v

text: j

text: j

text: and

text: assign

text: a

text: to

text: this

text: subsegment

text: to

text: move

text: back

text: and

text: forth

text: from

text: one

text: end

text: to

text: the

text: other,

text: perpetually.

text: j

text: We

text: now

text: have

text: a

text: guarding

text: schedule

text: with

text: unit

text: idle

text: time

text: for

text: a

text: segment

text: longer

text: than

text: s,

text: which

text: is

text: a

text: contradiction.

text: Overtaking

text: other

text: agents.

text: Consider

text: an

text: optimal

text: schedule

text: for

text: circle

text: patrolling

text: (with

text: unit

text: idle

text: time)

text: for

text: the

text: agents

text: in

text: the

text: proof

text: of

text: Proposition

text: with

text: v

text: and

text: v

text: v

text: ε/k,

text: in

text: k

text: which

text: all

text: agents

text: move

text: clockwise

text: at

text: their

text: maximum

text: speeds.

text: Obviously

text: a

text: will

text: overtake

text: all

text: other

text: agents

text: during

text: the

text: time

text: interval

text: Thus

text: there

text: exist

text: settings

text: in

text: which

text: if

text: all

text: k

text: agents

text: are

text: used

text: by

text: a

text: patrolling

text: algorithm,

text: then

text: some

text: agent(s)

text: need

text: to

text: overtake

text: (pass)

text: other

text: agent(s).

text: Observe

text: however

text: that

text: overtaking

text: can

text: be

text: easily

text: avoided

text: in

text: this

text: setting

text: by

text: not

text: making

text: use

text: of

text: any

text: of

text: the

text: agents

text: a

text: a

text: k

text: An

text: Improved

text: Idle

text: Time

text: for

text: Open

text: Fence

text: Patrolling

text: Kawamura

text: and

text: Kobayashi

text: showed

text: that

text: algorithm

text: A

text: by

text: Czyzowicz

text: et

text: al.

text: does

text: not

text: always

text: produce

text: an

text: optimal

text: schedule

text: for

text: open

text: fence

text: patrolling.

text: They

text: presented

text: two

text: counterexamples:

text: their

text: ﬁrst

text: example

text: uses

text: agents

text: and

text: achieves

text: an

text: idle

text: time

text: of

text: idle(A

text: their

text: second

text: example

text: uses

text: agents

text: and

text: achieves

text: an

text: idle

text: time

text: of

text: idle(A

text: By

text: replicating

text: the

text: strategy

text: from

text: the

text: second

text: example

text: with

text: a

text: number

text: of

text: agents

text: larger

text: than

text: i.e.,

text: iteratively

text: using

text: blocks

text: of

text: agents,

text: we

text: improve

text: the

text: ratio

text: to

text: ε

text: for

text: any

text: ε

text: We

text: need

text: two

text: technical

text: lemmas

text: to

text: verify

text: this

text: claim.

text: Lemma

text: Consider

text: a

text: segment

text: of

text: length

text: L

text: such

text: that

text: three

text: agents

text: a

text: a

text: a

text: are

text: patrolling

text: perpetually

text: each

text: with

text: speed

text: of

text: and

text: generating

text: an

text: alternating

text: sequence

text: of

text: uncovered

text: triangles

text: T

text: T

text: T

text: T

text: as

text: shown

text: in

text: the

text: position-time

text: diagram

text: in

text: Fig.

text: Denote

text: the

text: vertical

text: distances

text: between

text: consecutive

text: occurrences

text: of

text: T

text: and

text: T

text: by

text: δ

text: and

text: between

text: consecutive

text: occurrences

text: of

text: T

text: and

text: T

text: by

text: δ

text: Denote

text: the

text: bases

text: of

text: T

text: and

text: T

text: by

text: b

text: and

text: b

text: respectively,

text: and

text: the

text: heights

text: of

text: T

text: and

text: T

text: by

text: h

text: and

text: h

text: respectively.

text: Then

text: (i)

text: is

text: a

text: period

text: of

text: the

text: schedule.

text: (ii)

text: T

text: and

text: T

text: are

text: congruent;

text: further,

text: b

text: b

text: δ

text: δ

text: and

text: h

text: h

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Figure 5. Representative trajectories from a particular surface of constant energy density ﬁxed outside of the the visible area. The blue solid lines are trajectories for the v = 40M case and the red pl dotted lines are for the v = 10M case. We see that while slow-roll is a good approximation these pl lines are almost identical when plotted on the rescaled (ψ/v, σ/v) axis, but diverge as slow-roll ends. Inﬂation also ends in diﬀerent positions for the two cases. The resultant distributions for n and r for the v = 40M and v = 10M cases are s pl pl plotted in Fig. 6, respectively, where roughly 1000 initial conditions are drawn from each of the prior distributions (the results are presented in histogram form, and so the vertical axis represents the number of points in each bin, rather than the normalised probability distribu- tion). One can see in both cases that the bulk of the probability distribution corresponds to values of r disfavoured by Planck. However, in the v = 40M case there is signiﬁcant weight pl close to the preferred region. It is an interesting question how to interpret these results. First we should note that we have eﬀectively marginalised over the amplitude of the scalar power spectrum, since we have ﬁxed this by implicitly normalising A. This is true also of previous statistical studies [32, 39], and in reality there is a distribution of amplitudes as well as of n and r given ﬁxed model s parameters. This makes it diﬃcult to directly interpret the plotted distributions. Moreover, even if we were to take the distributions at face value, it is still an open question when to prefer one case over another. For example, comparing the v = 10M and v = 40M cases it pl pl is clear more of the probability in the v = 40M case is close to the observationally preferred pl values of n and r. However, the v = 10M case has a small probability to get right in the s pl middle of the preferred (n , r) region. We might consider therefore not weighting all initial s conditions equally, but preferring those that get closer to the the preferred observational values of n and r, and thus deriving some ultimate measure of the goodness of the model. s Though that is beyond the scope of the present work. On the other hand, if we simply required the majority of the probability as plotted to be within the preferred (n , r) region, s it is clear that neither value of v could be considered consistent with observations. Before concluding this Section, we re-emphasize the point that, in this model, trajec- tories that begin their evolution in the quartic regime of the potential may plausibly ﬁnd – 13 – ##LTFigure##

text: Figure

text: Representative

text: trajectories

text: from

text: a

text: particular

text: surface

text: of

text: constant

text: energy

text: density

text: ﬁxed

text: outside

text: of

text: the

text: the

text: visible

text: area.

text: The

text: blue

text: solid

text: lines

text: are

text: trajectories

text: for

text: the

text: v

text: case

text: and

text: the

text: red

text: pl

text: dotted

text: lines

text: are

text: for

text: the

text: v

text: case.

text: We

text: see

text: that

text: while

text: slow-roll

text: is

text: a

text: good

text: approximation

text: these

text: pl

text: lines

text: are

text: almost

text: identical

text: when

text: plotted

text: on

text: the

text: rescaled

text: (ψ/v,

text: σ/v)

text: axis,

text: but

text: diverge

text: as

text: slow-roll

text: ends.

text: Inﬂation

text: also

text: ends

text: in

text: diﬀerent

text: positions

text: for

text: the

text: two

text: cases.

text: The

text: resultant

text: distributions

text: for

text: n

text: and

text: r

text: for

text: the

text: v

text: and

text: v

text: cases

text: are

text: s

text: pl

text: pl

text: plotted

text: in

text: Fig.

text: respectively,

text: where

text: roughly

text: initial

text: conditions

text: are

text: drawn

text: from

text: each

text: of

text: the

text: prior

text: distributions

text: (the

text: results

text: are

text: presented

text: in

text: histogram

text: form,

text: and

text: so

text: the

text: vertical

text: axis

text: represents

text: the

text: number

text: of

text: points

text: in

text: each

text: bin,

text: rather

text: than

text: the

text: normalised

text: probability

text: distribu-

text: tion).

text: One

text: can

text: see

text: in

text: both

text: cases

text: that

text: the

text: bulk

text: of

text: the

text: probability

text: distribution

text: corresponds

text: to

text: values

text: of

text: r

text: disfavoured

text: by

text: Planck.

text: However,

text: in

text: the

text: v

text: case

text: there

text: is

text: signiﬁcant

text: weight

text: pl

text: close

text: to

text: the

text: preferred

text: region.

text: It

text: is

text: an

text: interesting

text: question

text: how

text: to

text: interpret

text: these

text: results.

text: First

text: we

text: should

text: note

text: that

text: we

text: have

text: eﬀectively

text: marginalised

text: over

text: the

text: amplitude

text: of

text: the

text: scalar

text: power

text: spectrum,

text: since

text: we

text: have

text: ﬁxed

text: this

text: by

text: implicitly

text: normalising

text: A.

text: This

text: is

text: true

text: also

text: of

text: previous

text: statistical

text: studies

text: and

text: in

text: reality

text: there

text: is

text: a

text: distribution

text: of

text: amplitudes

text: as

text: well

text: as

text: of

text: n

text: and

text: r

text: given

text: ﬁxed

text: model

text: s

text: parameters.

text: This

text: makes

text: it

text: diﬃcult

text: to

text: directly

text: interpret

text: the

text: plotted

text: distributions.

text: Moreover,

text: even

text: if

text: we

text: were

text: to

text: take

text: the

text: distributions

text: at

text: face

text: value,

text: it

text: is

text: still

text: an

text: open

text: question

text: when

text: to

text: prefer

text: one

text: case

text: over

text: another.

text: For

text: example,

text: comparing

text: the

text: v

text: and

text: v

text: cases

text: it

text: pl

text: pl

text: is

text: clear

text: more

text: of

text: the

text: probability

text: in

text: the

text: v

text: case

text: is

text: close

text: to

text: the

text: observationally

text: preferred

text: pl

text: values

text: of

text: n

text: and

text: r.

text: However,

text: the

text: v

text: case

text: has

text: a

text: small

text: probability

text: to

text: get

text: right

text: in

text: the

text: s

text: pl

text: middle

text: of

text: the

text: preferred

text: (n

text: r)

text: region.

text: We

text: might

text: consider

text: therefore

text: not

text: weighting

text: all

text: initial

text: s

text: conditions

text: equally,

text: but

text: preferring

text: those

text: that

text: get

text: closer

text: to

text: the

text: the

text: preferred

text: observational

text: values

text: of

text: n

text: and

text: r,

text: and

text: thus

text: deriving

text: some

text: ultimate

text: measure

text: of

text: the

text: goodness

text: of

text: the

text: model.

text: s

text: Though

text: that

text: is

text: beyond

text: the

text: scope

text: of

text: the

text: present

text: work.

text: On

text: the

text: other

text: hand,

text: if

text: we

text: simply

text: required

text: the

text: majority

text: of

text: the

text: probability

text: as

text: plotted

text: to

text: be

text: within

text: the

text: preferred

text: (n

text: r)

text: region,

text: s

text: it

text: is

text: clear

text: that

text: neither

text: value

text: of

text: v

text: could

text: be

text: considered

text: consistent

text: with

text: observations.

text: Before

text: concluding

text: this

text: Section,

text: we

text: re-emphasize

text: the

text: point

text: that,

text: in

text: this

text: model,

text: trajec-

text: tories

text: that

text: begin

text: their

text: evolution

text: in

text: the

text: quartic

text: regime

text: of

text: the

text: potential

text: may

text: plausibly

text: ﬁnd

text: ##LTFigure##


text: Figure 6. The statistical distributions of n and r for the v = 40M (upper panel) and v = 10M s pl pl (lower panel) cases. The results presented are not normalised, and so are histograms with the vertical axis referring to the number of points in each bin. their way into the concave region for the requisite number of e-folds, as exempliﬁed by the v = 40 case discussed above – where a minority but signiﬁcant amount of the probability distribution corresponds to evolutions on the concave region. This observation is interesting – 14 – ##LTFigure## ##LTFigure##

text: Figure

text: The

text: statistical

text: distributions

text: of

text: n

text: and

text: r

text: for

text: the

text: v

text: (upper

text: panel)

text: and

text: v

text: s

text: pl

text: pl

text: (lower

text: panel)

text: cases.

text: The

text: results

text: presented

text: are

text: not

text: normalised,

text: and

text: so

text: are

text: histograms

text: with

text: the

text: vertical

text: axis

text: referring

text: to

text: the

text: number

text: of

text: points

text: in

text: each

text: bin.

text: their

text: way

text: into

text: the

text: concave

text: region

text: for

text: the

text: requisite

text: number

text: of

text: e-folds,

text: as

text: exempliﬁed

text: by

text: the

text: v

text: case

text: discussed

text: above

text: where

text: a

text: minority

text: but

text: signiﬁcant

text: amount

text: of

text: the

text: probability

text: distribution

text: corresponds

text: to

text: evolutions

text: on

text: the

text: concave

text: region.

text: This

text: observation

text: is

text: interesting

text: ##LTFigure##

label: figure

text: ##LTFigure##


text: calculate f , and we also provide the relations we use to connect the ﬁeld ﬂuctuations to ζ. The methods NL by which these are calculated are discussed extensively elsewhere [43]3 We can write the second order equations of motion for the scalar ﬁeld ﬂuctuations, at second order in perturbation theory, as a set of ﬁrst order equations of the compact form dx 1 α = u x + u x x (5.1) dN αβ β 2 αβγ β γ where for convenience we use N as the time variable, the Greek indices run over all ﬁelds and ﬁeld momenta (cid:48) perturbations, and where x represents (δφ , δφ ). The u matrices are α a b u = 0 , ab ua¯b = δ−ab , u = M2 /H2 , a¯b ab − ua¯¯b = ((cid:15) 3)δab , u = 0 , abc ua¯bc = 0 , (cid:34) (cid:35) ua¯bc¯ = 0 , −V V V → V V − 2V V V u = ,abc + ,ab ,c− + (b c) + ,bc ,a− ,a ,b−,c , a¯bc H2 H4M2 (3 (cid:15)) H4M2 (3 (cid:15)) H6M4 (3 (cid:15))2 pl pl pl (cid:48) (cid:48) − V V (cid:34)ϕ V ϕ(cid:35) ua¯¯bc = H4M,a4 (,3c −b (cid:15))2 + H2M,2ac(3b− (cid:15)) , pl pl (cid:48) (cid:48) (cid:48) (cid:48) ϕ ϕ → − V ϕ ϕ V δ ua¯¯bc¯ = Ma2 δbc + Mc2 δab + (b c) H2M,a4 (3b −c (cid:15))2 + H2M,2a(3bc− (cid:15)) , (5.2) pl pl pl pl (cid:48) where the bar indicates ﬁeld momentum indices (indices to be contracted with δϕ ) and no bar represents a ﬁeld indices, a dash indicates diﬀerentiation with respect to N, and M2 is deﬁned below Eq. (2.1) (note that ab after the change in time variable is taken into account, comparing the ﬁrst order u matrices with Eq. (2.1), the only diﬀerence is the missing k2 term which we neglect on super-horizon scales). These u matrices are used in Eq. (2.8). To convert to ζ, Eqs. (2.9)-(2.10), we use the follow N coeﬁcients − 1 ∂H2 (cid:18) (cid:19) (cid:18) (cid:19) N = , α 2H˙ ∂Xα − 1 ∂2H2 − ∂ 1 ∂H2 1 ∂ 1 dX ∂H2 ∂H2 N = + γ , (5.3) αβ 2H˙ ∂XαXβ ∂X(α H˙ ∂Xβ) 2H˙ ∂Xγ 2H˙ dN ∂Xα Xβ (cid:48) where X represents (ϕ , ϕ ) and where α a a 3We recall that the linear cosmological parameters, (n , r, α) are calculated using the full ﬁrst order k s dependent equations of motion for the two-point function from vacuum initial conditions, given in the main body of the text. But that the three point function is calculated assuming it is zero at horizon crossing, and using only the super-horizon equations of motion. – 16 – ##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: calculate

text: f

text: and

text: we

text: also

text: provide

text: the

text: relations

text: we

text: use

text: to

text: connect

text: the

text: ﬁeld

text: ﬂuctuations

text: to

text: ζ.

text: The

text: methods

text: NL

text: by

text: which

text: these

text: are

text: calculated

text: are

text: discussed

text: extensively

text: elsewhere

text: We

text: can

text: write

text: the

text: second

text: order

text: equations

text: of

text: motion

text: for

text: the

text: scalar

text: ﬁeld

text: ﬂuctuations,

text: at

text: second

text: order

text: in

text: perturbation

text: theory,

text: as

text: a

text: set

text: of

text: ﬁrst

text: order

text: equations

text: of

text: the

text: compact

text: form

text: dx

text: α

text: u

text: x

text: u

text: x

text: x

text: dN

text: αβ

text: β

text: αβγ

text: β

text: γ

text: where

text: for

text: convenience

text: we

text: use

text: N

text: as

text: the

text: time

text: variable,

text: the

text: Greek

text: indices

text: run

text: over

text: all

text: ﬁelds

text: and

text: ﬁeld

text: momenta

text: perturbations,

text: and

text: where

text: x

text: represents

text: (δφ

text: δφ

text: The

text: u

text: matrices

text: are

text: α

text: a

text: b

text: u

text: ab

text: ua¯b

text: δ−ab

text: u

text: a¯b

text: ab

text: ua¯¯b

text: u

text: abc

text: ua¯bc

text: ua¯bc¯

text: −V

text: V

text: V

text: V

text: V

text: V

text: V

text: u

text: ,abc

text: ,ab

text: ,c−

text: (b

text: c)

text: ,bc

text: ,a−

text: ,a

text: ,b−,c

text: a¯bc

text: pl

text: pl

text: pl

text: V

text: V

text: V

text: ua¯¯bc

text: −b

text: pl

text: pl

text: ϕ

text: ϕ

text: V

text: ϕ

text: ϕ

text: V

text: δ

text: ua¯¯bc¯

text: δbc

text: δab

text: (b

text: c)

text: −c

text: pl

text: pl

text: pl

text: pl

text: where

text: the

text: bar

text: indicates

text: ﬁeld

text: momentum

text: indices

text: (indices

text: to

text: be

text: contracted

text: with

text: δϕ

text: and

text: no

text: bar

text: represents

text: a

text: ﬁeld

text: indices,

text: a

text: dash

text: indicates

text: diﬀerentiation

text: with

text: respect

text: to

text: N,

text: and

text: is

text: deﬁned

text: below

text: Eq.

text: (note

text: that

text: ab

text: after

text: the

text: change

text: in

text: time

text: variable

text: is

text: taken

text: into

text: account,

text: comparing

text: the

text: ﬁrst

text: order

text: u

text: matrices

text: with

text: Eq.

text: the

text: only

text: diﬀerence

text: is

text: the

text: missing

text: term

text: which

text: we

text: neglect

text: on

text: super-horizon

text: scales).

text: These

text: u

text: matrices

text: are

text: used

text: in

text: Eq.

text: To

text: convert

text: to

text: ζ,

text: Eqs.

text: we

text: use

text: the

text: follow

text: N

text: coeﬁcients

text: N

text: α

text: ∂Xα

text: dX

text: N

text: γ

text: αβ

text: ∂XαXβ

text: ∂X(α

text: H˙

text: ∂Xβ)

text: ∂Xγ

text: dN

text: ∂Xα

text: Xβ

text: where

text: X

text: represents

text: (ϕ

text: ϕ

text: and

text: where

text: α

text: a

text: a

text: recall

text: that

text: the

text: linear

text: cosmological

text: parameters,

text: (n

text: r,

text: α)

text: are

text: calculated

text: using

text: the

text: full

text: ﬁrst

text: order

text: k

text: s

text: dependent

text: equations

text: of

text: motion

text: for

text: the

text: two-point

text: function

text: from

text: vacuum

text: initial

text: conditions,

text: given

text: in

text: the

text: main

text: body

text: of

text: the

text: text.

text: But

text: that

text: the

text: three

text: point

text: function

text: is

text: calculated

text: assuming

text: it

text: is

text: zero

text: at

text: horizon

text: crossing,

text: and

text: using

text: only

text: the

text: super-horizon

text: equations

text: of

text: motion.

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: SHELL et al.: BARE DEMO OF IEEETRAN.CLS FOR JOURNALS 3 are required for obtaining close-to-optimal results [14]. It in a parallel fashion using a decomposition technique. Let (cid:48) shall be demonstrated in Section V that even for as few as us commence by stating that the Lagrangian of (P ) is given two subcarriers, the solution algorithm employed in this work by (??), where λ ≥ 0 is the Lagrangian multiplier associated approaches the optimal EE achieved by an exhaustive search. with the constraint (7). The feasible region constraints (10) The optimization problem is formulated as shown as fol- and (11), as well as constraints (8) and (9) will be considered, lows. when deriving the optimal solution, which is detailed later. (cid:48) Relaxed Problem (P): The dual problem of (P ) may be written as [16] (cid:101) min. g(λ) = min. max. L (P, S, λ), which is solved by solv- ≥ ≥ P S (cid:101) λ 0 λ 0 , R ing NK similar subproblems for obtaining both the power maximize T (6) P S (cid:88) (cid:88) as well as the subcarrier allocations, and by solving a master , PT (cid:101) (cid:101) (cid:101) problem to update λ, until convergence is obtained. K N A. Solving the NK subproblems subject to PD,n + PAM,n + PMA,n ≤ P , 0,k 0, (k) (k),k max These subproblems are solved by employing the k=1 n=1 (7) Karush–Kuhn–Tucker (KKT) conditions [17], which are (cid:88) ﬁrst-order necessary and sufﬁcient conditions for optimality. sD,n + sA,n ≤ 1, ∀k, n, (8) k k We denote all optimal var(cid:101)iables by(cid:101)a superscri(cid:101)pt asterisk, and (cid:101)K sD,n(cid:101) + sA,n ≤(cid:101) 1, ∀n, (9) the total transmit(cid:101)power assign(cid:101)ed for A(cid:101)F transmission to user k k k over subcarrier n by PA,n = PAM,n + PMA,n . Then, k=1 k 0, (k) (k),k P0D,k,n, P0A,M,n(k), PMA,(nk),k ∈ R+, ∀k, n, (10) bfoylloswubinstgituﬁtrisntg-orPdMeAr,(ndk)e,rkiva=tiv(cid:12)(cid:12)PeskAm,nay−bPe0Ao,M,bnt(akin) eidnto (??), the (cid:12) 0 ≤ sD,n, sA,n ≤ 1, ∀k, n, (11) (cid:12) k k (cid:101) (cid:12) ∂L (P, S, λ) (cid:101) (cid:101) = 0, (16) where the objective function is the ratio between (??) ∂PD,n ∗ 0,k (cid:12)PD,n=PD,n and (??(cid:101)). (cid:101) (cid:101) (cid:12) 0,k 0,k (cid:12) In this formulation, the variables to be optimized are sD,n, (cid:12) k (cid:101) (cid:12) sA,n, PD,(cid:101)n, PAM,(cid:101)n and PMA(cid:101),n , ∀k, n. Physically, the ∂L (P, S, λ) coknstrain0t,k(7) en0s,ur(eks) that the su(mk),kof the power allocated to (cid:101) (cid:101) = 0 (17) variables PD,n, PAM,n and PMA,n does not exceed the ∂PkA,n PA,n=PA,n∗ 0,k 0, (k) (k),k k k maximum power budget of the system. Constraint (8) ensures (cid:12) and (cid:12) that a single transmission protocol, either direct or AF, is cho- (cid:12) (cid:12) sen for each user-subcarrier pair. The constraint (9) guarantees (cid:101) (cid:12) that each subcarrier is only allocated to at most one user, thus ∂L (P, S, λ) (cid:101) (cid:101) = 0. (18) idnetsrcar-icbeelltihnetefrefaesriebnlceeriesgaiovnoiodfedth. eThoeptcimonizstartaioinntsv(a1r0ia)balensd. (T1h1e) ∂P0A,M,n(k) P(cid:101)AM,n =PAM,n∗ 0, (k) 0, (k) OF of problem (P) is quasi-concave [10], please see [15] for the proof. The optimal val(cid:34)ues of P0D,k,n may be rea(cid:35)dily obtained from (16) as IV. DINKELBACH’S METHOD FOR SOLVING THE PROBLEM (cid:0) (cid:1) (P) + ∗ 1 1 Dinkelbach’s method [10] is an iterative algorithm that can PD,n = − , (19) be used for solving a quasi-concave problem in a parameter- 0,k ln 2 qiξ(B) + λ αkD,n ized concave form. The value of the parameter at iteration i is denoted by q , and the parameterized form is given by where the effective channel gain of the direct transmission Subtractive piroblem (P(cid:48)): is given by αD,n = Gn0,k and [·]+ denotes(cid:101) max(0, ·), (cid:101) (cid:101) s(cid:101)ince the powekrs allocat∆edγNh0aWve to be nonnegative due to the constraint (10). Similarly the optimal values of PAM,n and maximize R (P, S) − q P (P, S) (14) 0, (k) P,S T i T PMA,(nk),k may be obtained by equating (17) and (18) to give subject to (7), (8), (9), (10), (11), ∗ ∗ PAM,n = βA,nPA,n (20) 0, (k) k k which i(cid:101)s solved at each(cid:101)iteration for obtaining an updated (cid:16) (cid:17) parameter value. For futher details, please refer to [10]. and Since R (P, S) and P (P, S) are concave and afﬁne, respective(cid:48)lyT[15], it is plausTible that the OF in (P(cid:48)) is concave. PMA,n∗ = 1 − βA,n PA,n∗, (21) Thus, (P ) is a typical concave maximization problem and (k),k k k may be solved using convex optimization techniques. In this work, we opt for the method of dual decomposition [16], where the total transmit power assigned for the AF trans- (cid:48) which solves (P ) by solving a series of subproblems. This mission to user k over subcarrier n is given by (??), (??) (cid:48) approach is favorable in this context as the OF in (P ) is and (??). Observe that (??) is the fraction of the total AF formed by the summation of multiple similar terms of separate transmit power that is allocated for the BS-to-RN link while variables, where the maximization of each term can be solved obeying 0 ≤ βA,n ≤ 1. k ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: SHELL

text: et

text: al.:

text: BARE

text: DEMO

text: OF

text: IEEETRAN.CLS

text: FOR

text: JOURNALS

text: are

text: required

text: for

text: obtaining

text: close-to-optimal

text: results

text: It

text: in

text: a

text: parallel

text: fashion

text: using

text: a

text: decomposition

text: technique.

text: Let

text: shall

text: be

text: demonstrated

text: in

text: Section

text: V

text: that

text: even

text: for

text: as

text: few

text: as

text: us

text: commence

text: by

text: stating

text: that

text: the

text: Lagrangian

text: of

text: (P

text: is

text: given

text: two

text: subcarriers,

text: the

text: solution

text: algorithm

text: employed

text: in

text: this

text: work

text: by

text: where

text: λ

text: is

text: the

text: Lagrangian

text: multiplier

text: associated

text: approaches

text: the

text: optimal

text: EE

text: achieved

text: by

text: an

text: exhaustive

text: search.

text: with

text: the

text: constraint

text: The

text: feasible

text: region

text: constraints

text: The

text: optimization

text: problem

text: is

text: formulated

text: as

text: shown

text: as

text: fol-

text: and

text: as

text: well

text: as

text: constraints

text: and

text: will

text: be

text: considered,

text: lows.

text: when

text: deriving

text: the

text: optimal

text: solution,

text: which

text: is

text: detailed

text: later.

text: Relaxed

text: Problem

text: (P):

text: The

text: dual

text: problem

text: of

text: (P

text: may

text: be

text: written

text: as

text: min.

text: g(λ)

text: min.

text: max.

text: L

text: (P,

text: S,

text: λ),

text: which

text: is

text: solved

text: by

text: solv-

text: P

text: S

text: λ

text: λ

text: R

text: ing

text: NK

text: similar

text: subproblems

text: for

text: obtaining

text: both

text: the

text: power

text: maximize

text: T

text: P

text: S

text: as

text: well

text: as

text: the

text: subcarrier

text: allocations,

text: and

text: by

text: solving

text: a

text: master

text: PT

text: problem

text: to

text: update

text: λ,

text: until

text: convergence

text: is

text: obtained.

text: K

text: N

text: A.

text: Solving

text: the

text: NK

text: subproblems

text: subject

text: to

text: PD,n

text: PAM,n

text: PMA,n

text: P

text: (k)

text: (k),k

text: max

text: These

text: subproblems

text: are

text: solved

text: by

text: employing

text: the

text: Karush–Kuhn–Tucker

text: (KKT)

text: conditions

text: which

text: are

text: ﬁrst-order

text: necessary

text: and

text: sufﬁcient

text: conditions

text: for

text: optimality.

text: sD,n

text: sA,n

text: ∀k,

text: n,

text: k

text: k

text: We

text: denote

text: all

text: optimal

text: asterisk,

text: and

text: sA,n

text: ∀n,

text: the

text: total

text: for

text: transmission

text: to

text: user

text: k

text: k

text: k

text: over

text: subcarrier

text: n

text: by

text: PA,n

text: PAM,n

text: PMA,n

text: Then,

text: k

text: (k)

text: (k),k

text: PMA,(nk),k

text: R+,

text: ∀k,

text: n,

text: eidnto

text: the

text: sD,n,

text: sA,n

text: ∀k,

text: n,

text: k

text: k

text: ∂L

text: (P,

text: S,

text: λ)

text: where

text: the

text: objective

text: function

text: is

text: the

text: ratio

text: between

text: ∂PD,n

text: and

text: In

text: this

text: formulation,

text: the

text: variables

text: to

text: be

text: optimized

text: are

text: sD,n,

text: k

text: sA,n,

text: and

text: ∀k,

text: n.

text: Physically,

text: the

text: ∂L

text: (P,

text: S,

text: λ)

text: that

text: the

text: su(mk),kof

text: the

text: power

text: allocated

text: to

text: variables

text: PD,n,

text: PAM,n

text: and

text: PMA,n

text: does

text: not

text: exceed

text: the

text: ∂PkA,n

text: PA,n=PA,n∗

text: (k)

text: (k),k

text: k

text: k

text: maximum

text: power

text: budget

text: of

text: the

text: system.

text: Constraint

text: ensures

text: and

text: that

text: a

text: single

text: transmission

text: protocol,

text: either

text: direct

text: or

text: AF,

text: is

text: cho-

text: sen

text: for

text: each

text: user-subcarrier

text: pair.

text: The

text: constraint

text: guarantees

text: that

text: each

text: subcarrier

text: is

text: only

text: allocated

text: to

text: at

text: most

text: one

text: user,

text: thus

text: ∂L

text: (P,

text: S,

text: λ)

text: =PAM,n∗

text: (k)

text: (k)

text: OF

text: of

text: problem

text: (P)

text: is

text: quasi-concave

text: please

text: see

text: for

text: the

text: proof.

text: The

text: optimal

text: of

text: may

text: be

text: obtained

text: from

text: as

text: IV.

text: DINKELBACH’S

text: METHOD

text: FOR

text: SOLVING

text: THE

text: PROBLEM

text: (P)

text: Dinkelbach’s

text: method

text: is

text: an

text: iterative

text: algorithm

text: that

text: can

text: PD,n

text: be

text: used

text: for

text: solving

text: a

text: quasi-concave

text: problem

text: in

text: a

text: parameter-

text: ln

text: qiξ(B)

text: λ

text: αkD,n

text: ized

text: concave

text: form.

text: The

text: value

text: of

text: the

text: parameter

text: at

text: iteration

text: i

text: is

text: denoted

text: by

text: q

text: and

text: the

text: parameterized

text: form

text: is

text: given

text: by

text: where

text: the

text: effective

text: channel

text: gain

text: of

text: the

text: direct

text: transmission

text: Subtractive

text: piroblem

text: is

text: given

text: by

text: αD,n

text: and

text: the

text: powekrs

text: to

text: be

text: nonnegative

text: due

text: to

text: the

text: constraint

text: Similarly

text: the

text: optimal

text: values

text: of

text: PAM,n

text: and

text: maximize

text: R

text: (P,

text: S)

text: q

text: P

text: (P,

text: S)

text: (k)

text: P,S

text: T

text: i

text: T

text: PMA,(nk),k

text: may

text: be

text: obtained

text: by

text: equating

text: and

text: to

text: give

text: subject

text: to

text: PAM,n

text: βA,nPA,n

text: (k)

text: k

text: k

text: which

text: solved

text: at

text: for

text: obtaining

text: an

text: updated

text: parameter

text: value.

text: For

text: futher

text: details,

text: please

text: refer

text: to

text: and

text: Since

text: R

text: (P,

text: S)

text: and

text: P

text: (P,

text: S)

text: are

text: concave

text: and

text: afﬁne,

text: it

text: is

text: plausTible

text: that

text: the

text: OF

text: in

text: is

text: concave.

text: PMA,n∗

text: βA,n

text: PA,n∗,

text: Thus,

text: (P

text: is

text: a

text: typical

text: concave

text: maximization

text: problem

text: and

text: (k),k

text: k

text: k

text: may

text: be

text: solved

text: using

text: convex

text: optimization

text: techniques.

text: In

text: this

text: work,

text: we

text: opt

text: for

text: the

text: method

text: of

text: dual

text: decomposition

text: where

text: the

text: total

text: transmit

text: power

text: assigned

text: for

text: the

text: AF

text: trans-

text: which

text: solves

text: (P

text: by

text: solving

text: a

text: series

text: of

text: subproblems.

text: This

text: mission

text: to

text: user

text: k

text: over

text: subcarrier

text: n

text: is

text: given

text: by

text: approach

text: is

text: favorable

text: in

text: this

text: context

text: as

text: the

text: OF

text: in

text: (P

text: is

text: and

text: Observe

text: that

text: is

text: the

text: fraction

text: of

text: the

text: total

text: AF

text: formed

text: by

text: the

text: summation

text: of

text: multiple

text: similar

text: terms

text: of

text: separate

text: transmit

text: power

text: that

text: is

text: allocated

text: for

text: the

text: BS-to-RN

text: link

text: while

text: variables,

text: where

text: the

text: maximization

text: of

text: each

text: term

text: can

text: be

text: solved

text: obeying

text: βA,n

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##