text: 5 Analysis of the WB functional In this section we compute the mean and the variance of the WB functional. 5.1 Average of the functional Using our model (3.13) and the deﬁnition of the functional (3.1), we have E{ } (cid:39) − E{ } IW [p] (z) e Σ/2 IW [p ] (z). B The cross-range resolution of IW is the same as the classical Kirchhoﬀ functional and given by the Rayleigh formula λL/l. 5.2 Variance of the functional (cid:8) (cid:8) (cid:9) (cid:9) The variance is deﬁned by E | − E | V W (z) = IW [p](z) IW [p] (z) 2 . As before, we distinguish the contribution of the single scattering, denoted by V W , from the one of the noise, denoted by V W . We then have the following propositions, proved in sections n and : Proposition 5.1 The variance of the WB functional for the single scattering contribution satisﬁes: ∼ − | | ≤ V W (z) e Σσ2 for z εµ, 0 | | ≤ and V W is mostly supported on z µε. As for the CB functional, the results are optimal. Regarding the contribution of the noise, we have: Proposition 5.2 The variance of the WB functional for the noise contribution satisﬁes for all z: ∼ V W (z) σ2. n n In the latter case, the variance is uniform in z and not just supported on the support of the source. This is due to the fact that, contrary to the CB functional which considers the correlation of the noise with the coherent waveﬁeld (i.e. V C involves (pB)2(σ nε)2), the n n p variance of the noise for the WB functional does not involve the average waveﬁeld and the information about the source is lost (i.e. V W involves only (σ nε)2). Remark also that V W n n p n and V C are comparable when γ = 1, namely when both functionals have the same resolution. n V C decreases when the resolution worsens. n The proof of theorem 2.1 is then a straightforward consequence of (4.1), propositions 4.2, − 4.3, 5.1, and 5.2 after recasting ε, η and r ε γ in terms of λ, L, (cid:96) and N . 0 c C 6 Proofs 6.1 Proof of lemma 4.1 We start from (3.14) using the notations of section . We project the initial condition W ε onto the propagating modes and introduce the related amplitudes a± (recall there are no 0 (cid:88) vortical modes since the initial velocity is zero): ⊗ √1 ± W ε(t, x, k) = a±(t, x, k)B±(k), B± = b± b± b± = (kˆ, 1)T , 0 ± 2 19 ##LTLine## ##LTLine##

text: Analysis

text: of

text: the

text: WB

text: functional

text: In

text: this

text: section

text: we

text: compute

text: the

text: mean

text: and

text: the

text: variance

text: of

text: the

text: WB

text: functional.

text: Average

text: of

text: the

text: functional

text: Using

text: our

text: model

text: and

text: the

text: deﬁnition

text: of

text: the

text: functional

text: we

text: have

text: E{

text: E{

text: IW

text: [p]

text: (z)

text: e

text: IW

text: [p

text: (z).

text: B

text: The

text: cross-range

text: resolution

text: of

text: IW

text: is

text: the

text: same

text: as

text: the

text: classical

text: Kirchhoﬀ

text: functional

text: and

text: given

text: by

text: the

text: Rayleigh

text: formula

text: λL/l.

text: Variance

text: of

text: the

text: functional

text: The

text: variance

text: is

text: deﬁned

text: by

text: E

text: E

text: V

text: W

text: (z)

text: IW

text: [p](z)

text: IW

text: [p]

text: (z)

text: As

text: before,

text: we

text: distinguish

text: the

text: contribution

text: of

text: the

text: single

text: scattering,

text: denoted

text: by

text: V

text: W

text: from

text: the

text: one

text: of

text: the

text: noise,

text: denoted

text: by

text: V

text: W

text: We

text: then

text: have

text: the

text: following

text: propositions,

text: proved

text: in

text: sections

text: n

text: and

text: Proposition

text: The

text: variance

text: of

text: the

text: WB

text: functional

text: for

text: the

text: single

text: scattering

text: contribution

text: satisﬁes:

text: V

text: W

text: (z)

text: e

text: Σσ2

text: for

text: z

text: εµ,

text: and

text: V

text: W

text: is

text: mostly

text: supported

text: on

text: z

text: µε.

text: As

text: for

text: the

text: CB

text: functional,

text: the

text: results

text: are

text: optimal.

text: Regarding

text: the

text: contribution

text: of

text: the

text: noise,

text: we

text: have:

text: Proposition

text: The

text: variance

text: of

text: the

text: WB

text: functional

text: for

text: the

text: noise

text: contribution

text: satisﬁes

text: for

text: all

text: z:

text: V

text: W

text: (z)

text: n

text: n

text: In

text: the

text: latter

text: case,

text: the

text: variance

text: is

text: uniform

text: in

text: z

text: and

text: not

text: just

text: supported

text: on

text: the

text: support

text: of

text: the

text: source.

text: This

text: is

text: due

text: to

text: the

text: fact

text: that,

text: contrary

text: to

text: the

text: CB

text: functional

text: which

text: considers

text: the

text: correlation

text: of

text: the

text: noise

text: with

text: the

text: coherent

text: waveﬁeld

text: (i.e.

text: V

text: C

text: involves

text: the

text: n

text: n

text: p

text: variance

text: of

text: the

text: noise

text: for

text: the

text: WB

text: functional

text: does

text: not

text: involve

text: the

text: average

text: waveﬁeld

text: and

text: the

text: information

text: about

text: the

text: source

text: is

text: lost

text: (i.e.

text: V

text: W

text: involves

text: only

text: (σ

text: Remark

text: also

text: that

text: V

text: W

text: n

text: n

text: p

text: n

text: and

text: V

text: C

text: are

text: comparable

text: when

text: γ

text: namely

text: when

text: both

text: functionals

text: have

text: the

text: same

text: resolution.

text: n

text: V

text: C

text: decreases

text: when

text: the

text: resolution

text: worsens.

text: n

text: The

text: proof

text: of

text: theorem

text: is

text: then

text: a

text: straightforward

text: consequence

text: of

text: propositions

text: and

text: after

text: recasting

text: ε,

text: η

text: and

text: r

text: ε

text: γ

text: in

text: terms

text: of

text: λ,

text: L,

text: and

text: N

text: c

text: C

text: Proofs

text: Proof

text: of

text: lemma

text: We

text: start

text: from

text: using

text: the

text: notations

text: of

text: section

text: We

text: project

text: the

text: initial

text: condition

text: W

text: ε

text: onto

text: the

text: propagating

text: modes

text: and

text: introduce

text: the

text: related

text: amplitudes

text: a±

text: (recall

text: there

text: are

text: no

text: vortical

text: modes

text: since

text: the

text: initial

text: velocity

text: is

text: zero):

text: √1

text: W

text: ε(t,

text: x,

text: k)

text: a±(t,

text: x,

text: k)B±(k),

text: B±

text: b±

text: b±

text: b±

text: (kˆ,

text: ##LTLine##

text: ##LTLine##


text: (cid:90) (cid:88) where G(cid:90) (|ξ|, ξˆ)(cid:90)= S(cid:90)(0)(cid:90) (cid:90) dY |q|4F (|u|ξˆ)f0 (z + (1 − σ )ξ + e θ1 + e θ2, |q|, ξˆ) z ± σ2 εµ 1 1 u 2 u σ1,σ2= 1 (cid:18) | | (cid:19)| | · · · dY = d q dθ1dθ2d u ,(cid:0) e ξˆ = e (cid:1) ξˆ = e e = 0 R R R(cid:98) R u u 1 2 1 2 + + | | 1 · ∇ | | | | − | | f0 (x, q , ξˆ) = ξ + iµσ q w x, µ( q k ) , σ2 2 x 2 0 0  (cid:90)  and z = z/εµ. We will use the following relation: εµ  · eik x (2π)3δ0(x) if β = 0, dk | | = (6.3) R3 k β C |x|β−3 if 0 < β and β (cid:54)= 3, 5, · · · , β − − − where δ0 is the Dirac measure at zero and Cβ = 23 βπ 32 Γ(3 2·β·)·(Γ(β2 )) 1 (Γ being the gamma function). Note that (6.3) still holds for the case β = 3, 5, provided the constant C is β adjusted, see [22]. We(cid:90)will not explicit this constant since only the dependency in x matters to us. Hence, we deduce from (6.3) that · eik x (cid:48) | | − ∈ dk | | kˆ kˆ = C ∂2 x δ 1 for δ [0, 2], (6.4) R k δ j l δ xjxl 3 (cid:48) ∈ → → where C is a constant. When δ (0, 1), setting ξ εξ and ξ εξ in (6.2), it comes δ (cid:29) 1 1 2 2 using (6.4) and µ 1: (cid:90) (cid:90) ∼ − − − vε σ2η3 δε4(1 γ)µ4r4e 2Σ 2 0 0 · − · − × dξ dξ (ξˆ (ξ ξ ))(ξˆ (ξ ξ )) 1 2 | 1 − 1 | −2| | 2| | 1 2 G (0, ξˆ )G (0, ξˆ ) ≤| | ≤| | ξ ξ 5 δ ξ 2 ξ 2 z 1 z 2 1 ξ1 1 ξ2 1 2 1 2 plus a term of same order. The integral above is easily shown to be ﬁnite using the Hardy- Littlewood-Sobolev inequality [26]. A close look at G shows that only the term proportional · ∇ z | | → | | | | ∼ to ξˆ is left because of the sum over σ . Setting ﬁnally q k + q /µ yields vε − x − − | | ≤ 2 0 2 σ2η3 δε4(1 γ)µ2r4e 2Σ for z µε. Because of the term f0 , it is not diﬃcult to see that vε 0 0 | | ≤ ∈ σ2 2 is mostly supported on z µε. When(cid:90)δ [1(cid:90), 2) we use (6.4) and directly send ε to zero in (6.2). The leading term in G is obtained for σ = 1, and we ﬁnd z 1 ∼ − − − − dξ dξ v2ε σ02η3 δε4(1 γ)+1 δ(cid:88)µ4r04(cid:90)e 2Σ | |≤ | |≤ |ξ − ξ |31−δ|ξ2 |2|ξ |2 G0z(ξˆ1)G0z(ξˆ2), ξ1 1 ξ2 1 1 2 1 2 where | | | | | | G0(ξˆ) = S(0) dY q 4F ( u ξˆ)f0 (z + e θ1 + e θ2, q , ξˆ). z ± σ2 εµ 1 u 2 u σ2= 1 ∼ − − − − | | ≤ Again, summation over σ in G0 imply that vε σ2η3 δε4(1 γ)+1 δµ2r4e 2Σ for z µε. The ∼ 2 −z 2 0 0 | | ≤ case δ = 0 gives vε σ2η3ε4(1 γ)µ2r4, and vε(z) is mostly supported on z εµ. Gathering 2 0 0 2 − − all the previous results, we ﬁnd for the case µ = ε α with α < 1 γ: ∼ − − − ∧ − | | ≤ vε(z) σ2η3 δε4(1 γ)+(1 δ) 0µ2r4e 2Σ, z εµ, 2 0 0 | | ≤ ≥ − ≥ and vε(z) is essentially supported on z εµ. When α 1 γ (so that εµ εγ), very 2 | | ≤ ∼ − − ∧ − − similar calculations show that for z εµ, we have w (z) σ2η3 δε(1 δ) 0µ 2e 2Σ, and that (cid:28) | | (cid:29) ε 0 vε(z) vε(0) when z εµ. Combining the last two results, it ﬁnally follows that 2 2 ∼ − − − ∧ − ∧ − − | | ≤ vε(z) σ2η3 δε4(1 γ)+(1 δ) 0µ 2((r µ) εγ 1)4e 2Σ, z εµ, 2 0 0 23 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: where

text: (|ξ|,

text: dY

text: (z

text: σ

text: )ξ

text: e

text: θ1

text: e

text: |q|,

text: ξˆ)

text: z

text: σ2

text: εµ

text: u

text: u

text: dY

text: d

text: q

text: u

text: e

text: ξˆ

text: e

text: ξˆ

text: e

text: e

text: R

text: R

text: R

text: u

text: u

text: (x,

text: q

text: ξˆ)

text: ξ

text: iµσ

text: q

text: w

text: x,

text: µ(

text: q

text: k

text: σ2

text: x

text: and

text: z

text: z/εµ.

text: We

text: will

text: use

text: the

text: following

text: relation:

text: εµ

text: eik

text: x

text: if

text: β

text: dk

text: k

text: β

text: C

text: if

text: β

text: and

text: β

text: β

text: where

text: δ0

text: is

text: the

text: Dirac

text: measure

text: at

text: zero

text: and

text: Cβ

text: βπ

text: 2·β·)·(Γ(β2

text: (Γ

text: being

text: the

text: gamma

text: function).

text: Note

text: that

text: still

text: holds

text: for

text: the

text: case

text: β

text: provided

text: the

text: constant

text: C

text: is

text: β

text: adjusted,

text: see

text: not

text: explicit

text: this

text: constant

text: since

text: only

text: the

text: dependency

text: in

text: x

text: matters

text: to

text: us.

text: Hence,

text: we

text: deduce

text: from

text: that

text: eik

text: x

text: dk

text: kˆ

text: kˆ

text: C

text: ∂2

text: x

text: δ

text: for

text: δ

text: R

text: k

text: δ

text: j

text: l

text: δ

text: xjxl

text: where

text: C

text: is

text: a

text: constant.

text: When

text: δ

text: setting

text: ξ

text: εξ

text: and

text: ξ

text: εξ

text: in

text: it

text: comes

text: δ

text: using

text: and

text: µ

text: vε

text: σ2η3

text: 2Σ

text: dξ

text: dξ

text: (ξˆ

text: (ξ

text: ξ

text: ))(ξˆ

text: (ξ

text: ξ

text: G

text: ξˆ

text: )G

text: ξˆ

text: ξ

text: ξ

text: δ

text: ξ

text: ξ

text: z

text: z

text: ξ1

text: ξ2

text: plus

text: a

text: term

text: of

text: same

text: order.

text: The

text: integral

text: above

text: is

text: easily

text: shown

text: to

text: be

text: ﬁnite

text: using

text: the

text: Hardy-

text: Littlewood-Sobolev

text: inequality

text: A

text: close

text: look

text: at

text: G

text: shows

text: that

text: only

text: the

text: term

text: proportional

text: z

text: to

text: ξˆ

text: is

text: left

text: because

text: of

text: the

text: sum

text: over

text: σ

text: Setting

text: ﬁnally

text: q

text: k

text: q

text: /µ

text: yields

text: vε

text: x

text: σ2η3

text: 2Σ

text: for

text: z

text: µε.

text: Because

text: of

text: the

text: term

text: it

text: is

text: not

text: diﬃcult

text: to

text: see

text: that

text: vε

text: σ2

text: is

text: mostly

text: supported

text: on

text: z

text: µε.

text: we

text: use

text: and

text: directly

text: send

text: ε

text: to

text: zero

text: in

text: The

text: leading

text: term

text: in

text: G

text: is

text: obtained

text: for

text: σ

text: and

text: we

text: ﬁnd

text: z

text: dξ

text: dξ

text: 2Σ

text: |ξ

text: ξ

text: ξ1

text: ξ2

text: where

text: dY

text: q

text: u

text: (z

text: e

text: θ1

text: e

text: q

text: ξˆ).

text: z

text: σ2

text: εµ

text: u

text: u

text: Again,

text: summation

text: over

text: σ

text: in

text: imply

text: that

text: vε

text: σ2η3

text: 2Σ

text: for

text: z

text: µε.

text: The

text: −z

text: case

text: δ

text: gives

text: vε

text: and

text: vε(z)

text: is

text: mostly

text: supported

text: on

text: z

text: εµ.

text: Gathering

text: all

text: the

text: previous

text: results,

text: we

text: ﬁnd

text: for

text: the

text: case

text: µ

text: ε

text: α

text: with

text: α

text: γ:

text: vε(z)

text: σ2η3

text: δ)

text: z

text: εµ,

text: and

text: vε(z)

text: is

text: essentially

text: supported

text: on

text: z

text: εµ.

text: When

text: α

text: γ

text: (so

text: that

text: εµ

text: εγ),

text: very

text: similar

text: calculations

text: show

text: that

text: for

text: z

text: εµ,

text: we

text: have

text: w

text: (z)

text: σ2η3

text: δε(1

text: δ)

text: 0µ

text: and

text: that

text: ε

text: vε(z)

text: when

text: z

text: εµ.

text: Combining

text: the

text: last

text: two

text: results,

text: it

text: ﬁnally

text: follows

text: that

text: vε(z)

text: σ2η3

text: δ)

text: 0µ

text: µ)

text: εγ

text: z

text: εµ,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: with a similar observation for the ot(cid:90)her exponential, V W can be split into four terms. It can (cid:88) 1 be shown that the leading one is the one involving the product of the derivatives, so that ∼ (cid:48) (cid:0) (cid:48) (cid:8) (cid:9) (cid:1) V (z) σ2η3 dkdk dph (k , p, k) 1 0 ± R9 µ σ3,σ4,σ5,σ6= 1 × { | | − | | } − | (cid:48)| − | (cid:48) | − (exp i (σ k σ k + p ) 1) exp i (σ k σ k + p ) 1 . 5 3 6 4 With the changes of variab(cid:90)les(cid:90)|k| → |k | + |k|/µ, |(cid:12)(cid:12)k(cid:48)|(cid:32)→ |k | + |k(cid:48)(cid:33)|/µ(cid:12)(cid:12) and p → p/η, we ﬁnd 0 (cid:12) 0 (cid:12) (cid:12) (cid:12) (cid:12) − (cid:48) · (cid:12)2 V (z) ∼ σ2e−Σ (cid:88)dkˆdkˆ(cid:90)(cid:48)ei(kˆ−kˆ(cid:48))·z/ε(cid:16)gˆ (kˆ kˆ ) z(cid:17) (cid:16) (cid:17) 1 0 εµ S2 S2 − | | − − | | − dpRˆ(p) e iσ3 p /η) 1 e iσ4 p )/η 1 . ± R3 σ3,σ4= 1 Terms in the expression above involving an oscillating exponential are negligible, which shows ∼ − | | ≤ that V (0) σ2e Σ, and for the same reason as V , V is mostly supported on z εµ. The 1 0 2 1 leading term is therefore V , which ends the proof. 1 6.5 Proof of proposition 5.2 The proof is straightforward, the variance of the WB functional for the noise contribution (cid:90) admits the expression σ2 (cid:48) − (cid:48) · | | | (cid:48)|E{ F F (cid:48) } VnW (z) = (2πn)3 R dkdk ei(k k ) z cos k cos k ( 1Dnεp)(t = 1, k)( 1Dnεp)(t = 1, k ) . 3 (cid:90) Neglecting the ﬁnite size of the detector in ﬁrst approximation leads to ∼ | | ∼ V W (z) σ2ε3 dk(cos k )2Φˆ(εk) σ2. n n R n 3 7 Conclusion This work is concerned with the comparison in terms of resolution and stability of prototype wave-based and correlation-based imaging functionals. In the framework of 3D acoustic waves propagating in a random medium with possibly long-range correlations, we obtained optimal estimates of the variance and the SNR in terms of the main physical parameters of the problem. In the radiative transfer regime, we showed that for an identical cross-range resolution, the CB and WB functionals have a comparable SNR. The CB functional is shown to oﬀer a better SNR provided the resolution is lowered, which is achieved by calculating correlations over a small domain compared to the detector. This is the classical stability/resolution trade-oﬀ. We obtained morever that the minimal central wavelength λ that the functionals could accurately m reconstruct were identical in the regime of weak ﬂuctuations in the random medium, and that in the case of larger ﬂuctuations, the CB functional oﬀered a better (smaller) λ (resolution) m than the WB functional. We also investigated the eﬀects of long-range correlations in the complex medium. We showed that coherent imaging became diﬃcult to implement because the mean free path was very small and therefore the measured signal too weak compared to additive, external, noise. In such a case, transport-based imaging with lower resolution is a good alternative to wave-based (coherent) imaging. This will be investigated in more detail in future works. 29 ##LTLine## ##LTLine## ##LTLine##

text: with

text: a

text: similar

text: observation

text: for

text: the

text: exponential,

text: V

text: W

text: can

text: be

text: split

text: into

text: four

text: terms.

text: It

text: can

text: be

text: shown

text: that

text: the

text: leading

text: one

text: is

text: the

text: one

text: involving

text: the

text: product

text: of

text: the

text: derivatives,

text: so

text: that

text: V

text: (z)

text: σ2η3

text: dkdk

text: dph

text: (k

text: p,

text: k)

text: µ

text: (exp

text: i

text: (σ

text: k

text: σ

text: k

text: p

text: exp

text: i

text: (σ

text: k

text: σ

text: k

text: p

text: With

text: the

text: changes

text: of

text: |k

text: |k|/µ,

text: |k

text: and

text: p

text: p/η,

text: we

text: ﬁnd

text: V

text: (z)

text: σ2e−Σ

text: (kˆ

text: kˆ

text: εµ

text: dpRˆ(p)

text: e

text: p

text: /η)

text: e

text: p

text: )/η

text: Terms

text: in

text: the

text: expression

text: above

text: involving

text: an

text: oscillating

text: exponential

text: are

text: negligible,

text: which

text: shows

text: that

text: V

text: Σ,

text: and

text: for

text: the

text: same

text: reason

text: as

text: V

text: V

text: is

text: mostly

text: supported

text: on

text: z

text: εµ.

text: The

text: leading

text: term

text: is

text: therefore

text: V

text: which

text: ends

text: the

text: proof.

text: Proof

text: of

text: proposition

text: The

text: proof

text: is

text: straightforward,

text: the

text: variance

text: of

text: the

text: WB

text: functional

text: for

text: the

text: noise

text: contribution

text: admits

text: the

text: expression

text: σ2

text: F

text: F

text: VnW

text: (z)

text: R

text: dkdk

text: ei(k

text: k

text: z

text: cos

text: k

text: cos

text: k

text: k)(

text: k

text: Neglecting

text: the

text: ﬁnite

text: size

text: of

text: the

text: detector

text: in

text: ﬁrst

text: approximation

text: leads

text: to

text: V

text: W

text: (z)

text: σ2ε3

text: dk(cos

text: k

text: n

text: n

text: R

text: n

text: Conclusion

text: This

text: work

text: is

text: concerned

text: with

text: the

text: comparison

text: in

text: terms

text: of

text: resolution

text: and

text: stability

text: of

text: prototype

text: wave-based

text: and

text: correlation-based

text: imaging

text: functionals.

text: In

text: the

text: framework

text: of

text: acoustic

text: waves

text: propagating

text: in

text: a

text: random

text: medium

text: with

text: possibly

text: long-range

text: correlations,

text: we

text: obtained

text: optimal

text: estimates

text: of

text: the

text: variance

text: and

text: the

text: SNR

text: in

text: terms

text: of

text: the

text: main

text: physical

text: parameters

text: of

text: the

text: problem.

text: In

text: the

text: radiative

text: transfer

text: regime,

text: we

text: showed

text: that

text: for

text: an

text: identical

text: cross-range

text: resolution,

text: the

text: CB

text: and

text: WB

text: functionals

text: have

text: a

text: comparable

text: SNR.

text: The

text: CB

text: functional

text: is

text: shown

text: to

text: oﬀer

text: a

text: better

text: SNR

text: provided

text: the

text: resolution

text: is

text: lowered,

text: which

text: is

text: achieved

text: by

text: calculating

text: correlations

text: over

text: a

text: small

text: domain

text: compared

text: to

text: the

text: detector.

text: This

text: is

text: the

text: classical

text: stability/resolution

text: trade-oﬀ.

text: We

text: obtained

text: morever

text: that

text: the

text: minimal

text: central

text: wavelength

text: λ

text: that

text: the

text: functionals

text: could

text: accurately

text: m

text: reconstruct

text: were

text: identical

text: in

text: the

text: regime

text: of

text: weak

text: ﬂuctuations

text: in

text: the

text: random

text: medium,

text: and

text: that

text: in

text: the

text: case

text: of

text: larger

text: ﬂuctuations,

text: the

text: CB

text: functional

text: oﬀered

text: a

text: better

text: (smaller)

text: λ

text: (resolution)

text: m

text: than

text: the

text: WB

text: functional.

text: We

text: also

text: investigated

text: the

text: eﬀects

text: of

text: long-range

text: correlations

text: in

text: the

text: complex

text: medium.

text: We

text: showed

text: that

text: coherent

text: imaging

text: became

text: diﬃcult

text: to

text: implement

text: because

text: the

text: mean

text: free

text: path

text: was

text: very

text: small

text: and

text: therefore

text: the

text: measured

text: signal

text: too

text: weak

text: compared

text: to

text: additive,

text: external,

text: noise.

text: In

text: such

text: a

text: case,

text: transport-based

text: imaging

text: with

text: lower

text: resolution

text: is

text: a

text: good

text: alternative

text: to

text: wave-based

text: (coherent)

text: imaging.

text: This

text: will

text: be

text: investigated

text: in

text: more

text: detail

text: in

text: future

text: works.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [24] F. C. Karal, Jr. and J. B. Keller, Elastic, electromagnetic, and other waves in a random medium, J. Mathematical Phys., 5 (1964), pp. 537–547. [25] P.-L. Lions and T. Paul, Sur les mesures de Wigner, Rev. Mat. Iberoamericana, 9 (1993), pp. 553–618. [26] M. Reed and B. Simon, Methods of modern mathematical physics. II. Fourier Analysis, Self-Adjointness, Academic Press, Inc., New York, second ed., 1980. [27] L. Ryzhik, G. Papanicolaou, and J. B. Keller, Transport equations for elastic and other waves in random media, Wave Motion, 24 (1996), pp. 327–370. [28] P. J. Shull, Nondestructive evaluation. Theory, Techniques and Applications, Marcel Dekker, New York, 2002. [29] C. Sidi and F. Dalaudier, Turbulence in the stratiﬁed atmosphere: Recent theoretical devel- opments and experimental results, Adv. in Space Res., 10 (1990), pp. 25–36. 31

label: reference

text: F.

text: C.

text: Karal,

text: Jr.

text: and

text: J.

text: B.

text: Keller,

text: Elastic,

text: electromagnetic,

text: and

text: other

text: waves

text: in

text: a

text: random

text: medium,

text: J.

text: Mathematical

text: Phys.,

text: pp.

text: P.-L.

text: Lions

text: and

text: T.

text: Paul,

text: Sur

text: les

text: mesures

text: de

text: Wigner,

text: Rev.

text: Mat.

text: Iberoamericana,

text: pp.

text: M.

text: Reed

text: and

text: B.

text: Simon,

text: Methods

text: of

text: modern

text: mathematical

text: physics.

text: II.

text: Fourier

text: Analysis,

text: Self-Adjointness,

text: Academic

text: Press,

text: Inc.,

text: New

text: York,

text: second

text: ed.,

text: L.

text: Ryzhik,

text: G.

text: Papanicolaou,

text: and

text: J.

text: B.

text: Keller,

text: Transport

text: equations

text: for

text: elastic

text: and

text: other

text: waves

text: in

text: random

text: media,

text: Wave

text: Motion,

text: pp.

text: P.

text: J.

text: Shull,

text: Nondestructive

text: evaluation.

text: Theory,

text: Techniques

text: and

text: Applications,

text: Marcel

text: Dekker,

text: New

text: York,

text: C.

text: Sidi

text: and

text: F.

text: Dalaudier,

text: Turbulence

text: in

text: the

text: stratiﬁed

text: atmosphere:

text: Recent

text: theoretical

text: devel-

text: opments

text: and

text: experimental

text: results,

text: Adv.

text: in

text: Space

text: Res.,

text: pp.


text: We consider now the noise contributions V C and V W . A ﬁrst important observation is that n n V C(x) is mostly localized on the support of the source, while V W (x) is essentially a constant n n everywhere. This stems from the fact that in the CB functional, the noise is correlated with the average ﬁeld so that the functional keeps track of the source direction, while in the WB (cid:18)(cid:18) (cid:19) (cid:19) functional the noise is correlated with itself, see sections and . Moreover,the SNR are − SNRW (0) ∼ e 12ΣL , SNRC(0) ∼ SNRW (0) L ∧ µ 2 . n σ n n N λ n C As for the single scattering SNR, for identical resolutions (i.e. when N = l/λ), the SNR are c comparable. In order to obtain to better SNR for CB, one needs to lower the resolution (and ∧ (cid:29) therefore decrease N ) so that (L/(N λ)) µ = µ and SNRC(0) = SNRW (0)µ SNRW (0). C C n n n Minimal wavelength for a given SNR. We want to address here the question of the lowest central wavelength λ of the source (and therefore the best resolution) that can be achieved m for a given SNR. In order to do so, we need to take into account the frequency-dependent absorption factor. We ﬁrst consider the WB functional. We assume for concreteness that the noise contribution is larger than the single scattering one, but the same analysis holds for the − reversed situation. Let us ﬁx the SNR at one. Hence, λ has to be such that e ΣL/2 = σ . − m n Writing σn = e τn, this yields ΣL = 2τn. We will see in section that Σ admits the following expression − − − ∼ σ2η3 δ σ2(cid:96)3 δL − ∼ σ2(cid:96)3 δL Σ 0 − = −0 c − , which gives λ4 δ 0 c− . ε(1 δ ) λ4 δ(1 δ ) m τ (1 δ ) 2 m 2 m 2 Hence, as can be expected, λ decreases as the ﬂuctuations of the random medium and the m ↓ ↑ intensity of the noise decrease (i.e. σ and τ .) Remark as well that λ decreases as (cid:96) 0 n m → c does, and in a faster way compared to σ or τ . This is also expected since the limit (cid:96) 0 0 n c corresponds to the homogenization limit in which the wave propagates in a homogeneous medium provided σ is small. The measurements are therefore primarily coherent and both 0 the CB and WB functionals perform well. ∧ (cid:29) Let us consider now the CB functional and let δ = 0. Since for (L/(N λ)) µ 1, C SNRC is greater than SNRW , we may expect in principle to ﬁnd a lower minimal wavelength. A way to exploit this fact is to consider a central wavelength of the source λ /α, for the m λ above and some α > 1, and to compute correlations over a suﬃciently small domain m in order to gain stability, but a domain not too large so that the resolution is still better than λ . The resolution of the CB functional being L/N , we choose N = Lβ/λ , with m C C m β > 1 so that λ /β is smaller than λ . The prefactor in the SNR is then the square of ∧ m ∧ m (Lα/(N λ )) µ = (α/β) µ that we suppose is equal to (α/β)2. We ﬁnd C m ∼ − SNRC(0) σ4α 1(α/β)2, n − ≤ and we look for α > 1 and β > 1 such that σ4α 1α/β = 1. Since σ 1, this is possible only n n when α is not too large (so that the central wavelength of the source cannot be too small, otherwise absorption is too strong) and when σ is not too small either. When σ is below the n n threshold, then the minimal wavelength is the same for the CB and WB functionals. Hence, compared to the WB functional, the averaging eﬀects of the CB functional can be exploited in order to improve the optimal resolution only when the noise is signiﬁcant. Finding the optimal N is actually a diﬃcult problem, and is addressed numerically in [15]. C 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: We

text: consider

text: now

text: the

text: noise

text: contributions

text: V

text: C

text: and

text: V

text: W

text: A

text: ﬁrst

text: important

text: observation

text: is

text: that

text: n

text: n

text: V

text: C(x)

text: is

text: mostly

text: localized

text: on

text: the

text: support

text: of

text: the

text: source,

text: while

text: V

text: W

text: (x)

text: is

text: essentially

text: a

text: constant

text: n

text: n

text: everywhere.

text: This

text: stems

text: from

text: the

text: fact

text: that

text: in

text: the

text: CB

text: functional,

text: the

text: noise

text: is

text: correlated

text: with

text: the

text: average

text: ﬁeld

text: so

text: that

text: the

text: functional

text: keeps

text: track

text: of

text: the

text: source

text: direction,

text: while

text: in

text: the

text: WB

text: functional

text: the

text: noise

text: is

text: correlated

text: with

text: itself,

text: see

text: sections

text: and

text: Moreover,the

text: SNR

text: are

text: SNRW

text: e

text: SNRW

text: L

text: µ

text: n

text: σ

text: n

text: n

text: N

text: λ

text: n

text: C

text: As

text: for

text: the

text: single

text: scattering

text: SNR,

text: for

text: identical

text: resolutions

text: (i.e.

text: when

text: N

text: l/λ),

text: the

text: SNR

text: are

text: c

text: comparable.

text: In

text: order

text: to

text: obtain

text: to

text: better

text: SNR

text: for

text: CB,

text: one

text: needs

text: to

text: lower

text: the

text: resolution

text: (and

text: therefore

text: decrease

text: N

text: so

text: that

text: (L/(N

text: λ))

text: µ

text: µ

text: and

text: SNRW

text: SNRW

text: C

text: C

text: n

text: n

text: n

text: Minimal

text: wavelength

text: for

text: a

text: given

text: SNR.

text: We

text: want

text: to

text: address

text: here

text: the

text: question

text: of

text: the

text: lowest

text: central

text: wavelength

text: λ

text: of

text: the

text: source

text: (and

text: therefore

text: the

text: best

text: resolution)

text: that

text: can

text: be

text: achieved

text: m

text: for

text: a

text: given

text: SNR.

text: In

text: order

text: to

text: do

text: so,

text: we

text: need

text: to

text: take

text: into

text: account

text: the

text: frequency-dependent

text: absorption

text: factor.

text: We

text: ﬁrst

text: consider

text: the

text: WB

text: functional.

text: We

text: assume

text: for

text: concreteness

text: that

text: the

text: noise

text: contribution

text: is

text: larger

text: than

text: the

text: single

text: scattering

text: one,

text: but

text: the

text: same

text: analysis

text: holds

text: for

text: the

text: reversed

text: situation.

text: Let

text: us

text: ﬁx

text: the

text: SNR

text: at

text: one.

text: Hence,

text: λ

text: has

text: to

text: be

text: such

text: that

text: e

text: σ

text: m

text: n

text: Writing

text: σn

text: e

text: τn,

text: this

text: yields

text: ΣL

text: We

text: will

text: see

text: in

text: section

text: that

text: Σ

text: admits

text: the

text: following

text: expression

text: σ2η3

text: δ

text: δL

text: δL

text: Σ

text: −0

text: c

text: which

text: gives

text: λ4

text: δ

text: c−

text: δ

text: λ4

text: δ

text: m

text: τ

text: δ

text: m

text: m

text: Hence,

text: as

text: can

text: be

text: expected,

text: λ

text: decreases

text: as

text: the

text: ﬂuctuations

text: of

text: the

text: random

text: medium

text: and

text: the

text: m

text: intensity

text: of

text: the

text: noise

text: decrease

text: (i.e.

text: σ

text: and

text: τ

text: Remark

text: as

text: well

text: that

text: λ

text: decreases

text: as

text: n

text: m

text: c

text: does,

text: and

text: in

text: a

text: faster

text: way

text: compared

text: to

text: σ

text: or

text: τ

text: This

text: is

text: also

text: expected

text: since

text: the

text: limit

text: n

text: c

text: corresponds

text: to

text: the

text: homogenization

text: limit

text: in

text: which

text: the

text: wave

text: propagates

text: in

text: a

text: homogeneous

text: medium

text: provided

text: σ

text: is

text: small.

text: The

text: measurements

text: are

text: therefore

text: primarily

text: coherent

text: and

text: both

text: the

text: CB

text: and

text: WB

text: functionals

text: perform

text: well.

text: Let

text: us

text: consider

text: now

text: the

text: CB

text: functional

text: and

text: let

text: δ

text: Since

text: for

text: (L/(N

text: λ))

text: µ

text: C

text: SNRC

text: is

text: greater

text: than

text: SNRW

text: we

text: may

text: expect

text: in

text: principle

text: to

text: ﬁnd

text: a

text: lower

text: minimal

text: wavelength.

text: A

text: way

text: to

text: exploit

text: this

text: fact

text: is

text: to

text: consider

text: a

text: central

text: wavelength

text: of

text: the

text: source

text: λ

text: /α,

text: for

text: the

text: m

text: λ

text: above

text: and

text: some

text: α

text: and

text: to

text: compute

text: correlations

text: over

text: a

text: suﬃciently

text: small

text: domain

text: m

text: in

text: order

text: to

text: gain

text: stability,

text: but

text: a

text: domain

text: not

text: too

text: large

text: so

text: that

text: the

text: resolution

text: is

text: still

text: better

text: than

text: λ

text: The

text: resolution

text: of

text: the

text: CB

text: functional

text: being

text: L/N

text: we

text: choose

text: N

text: Lβ/λ

text: with

text: m

text: C

text: C

text: m

text: β

text: so

text: that

text: λ

text: /β

text: is

text: smaller

text: than

text: λ

text: The

text: prefactor

text: in

text: the

text: SNR

text: is

text: then

text: the

text: square

text: of

text: m

text: m

text: (Lα/(N

text: λ

text: µ

text: (α/β)

text: µ

text: that

text: we

text: suppose

text: is

text: equal

text: to

text: We

text: ﬁnd

text: C

text: m

text: σ4α

text: n

text: and

text: we

text: look

text: for

text: α

text: and

text: β

text: such

text: that

text: σ4α

text: 1α/β

text: Since

text: σ

text: this

text: is

text: possible

text: only

text: n

text: n

text: when

text: α

text: is

text: not

text: too

text: large

text: (so

text: that

text: the

text: central

text: wavelength

text: of

text: the

text: source

text: cannot

text: be

text: too

text: small,

text: otherwise

text: absorption

text: is

text: too

text: strong)

text: and

text: when

text: σ

text: is

text: not

text: too

text: small

text: either.

text: When

text: σ

text: is

text: below

text: the

text: n

text: n

text: threshold,

text: then

text: the

text: minimal

text: wavelength

text: is

text: the

text: same

text: for

text: the

text: CB

text: and

text: WB

text: functionals.

text: Hence,

text: compared

text: to

text: the

text: WB

text: functional,

text: the

text: averaging

text: eﬀects

text: of

text: the

text: CB

text: functional

text: can

text: be

text: exploited

text: in

text: order

text: to

text: improve

text: the

text: optimal

text: resolution

text: only

text: when

text: the

text: noise

text: is

text: signiﬁcant.

text: Finding

text: the

text: optimal

text: N

text: is

text: actually

text: a

text: diﬃcult

text: problem,

text: and

text: is

text: addressed

text: numerically

text: in

text: C

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∗ Vanishing beta function curves from the functional renormalisation group P. Mati † ‡ and 11 In this paper we will discuss the derivation of the so-called vanishing beta function curves which can be used to explore the ﬁxed point structure of the theory under consideration. This can be applied to the O(N) symmetric theories, essentially, for arbitrary dimensions (D) and ﬁeld com- ponent (N). We will show the restoration of the Mermin-Wagner theorem for theories deﬁned in ≤ D 2 and the presence of the Wilson-Fisher ﬁxed point in 2 < D < 4. Triviality is found in D > 4. Interestingly, one needs to make an excursion to the complex plane to see the triviality of the four-dimensional O(N) theories. The large -N analysis shows a new ﬁxed point candidate in 4 < D < 6 dimensions which turns out to deﬁne an unbounded ﬁxed point potential supporting the recent results by R. Percacci and G. P. Vacca in: ”Are there scaling solutions in the O(N)-models for large -N in D > 4?” [Phys. Rev. D 90, 107702 (2014)]. PACS numbers: 11.10.Gh, 11.10.Hi, 05.10.Cc, 11.10.Kk Keywords: I. INTRODUCTION There have been many investigations on the phase structure of the scalar O(N) models [1, 2, 8–10] using functional renormalisation group (FRG) techniques [11, 12, 15, 18] in various dimensions. Critical exponents were computed with high precision, ﬁxed points were found, and many physical aspects seem to be well understood. Hence, we can safely state: the FRG method is a reliable tool for non-perturbative calculations which can be used to consider the phase structure of a model and consequently to study e.g. the appearance of spontaneous symmetry breaking (SSB). For instance, according to the Mermin-Wagner (MW) theorem [23–25] a continuous symmetry cannot be broken ≥ spontaneously below a lower critical dimension, which is D = 2 for the O(N) symmetric theory for N 2. This has been recently shown in the framework of FRG [28]. Numerical evidence for the MW theorem is presented in [29]. The only exception is in D = 2 for N = 2 (the XY model), when an inﬁnite order phase transition is present [3, 4]. That is called the Berezinskii-Kosterlitz-Thouless (BTK) phase transition. To detect this kind of symmetry breaking the local potential approximation (LPA) is not sensitive enough [28]. Throughout this paper we will not consider the special case when N = 2 in D = 2 for these aforementioned reasons. Beyond LPA the BTK phase transition can be observed in the framework of FRG [5–7]. In summary, we can say that the O(N) scalar model represents an excellent playground for testing new techniques. The goal of this paper is to introduce the so-called vanishing beta function (VBF) method in the framework of the O(N) symmetric scalar ﬁeld theory, where the Wetterich FRG equation [11, 12] is used in the LPA assuming that the potential is analytic around the vanishing ﬁeld. There is an extensive study about the radius of convergence of the Taylor-expanded eﬀective potential in the large -N limit of the O(N) model in [22]. Expanding around vanishing ﬁeld enables us to provide a one-parameter representation of the ﬁxed point solution which actually deﬁnes the VBF curves through the couplings. This single parameter is the quadratic coupling of the theory (m2) and the roots of the VBF curve will deﬁne the position of the ﬁxed points at a given truncation level. In this approach we will lay down general requirements that a root must satisfy in order to deﬁne a stable ﬁxed point potential. Using this polynomial expression for the couplings will reveal an interesting root structure, which depends highly on dimensionality but there is a dependence on N, too, which is rather quantitative. As a consequence of the approximations used in the VBF technique could lead us to potentially artiﬁcial ﬁxed points even in the higher order of truncation. However, it can be shown that these ”spurious” ﬁxed point solutions are excluded by taking the inﬁnite limit in the order of the expansion, although strictly mathematically they must be considered as a valid ﬁxed point at ﬁnite truncation. We will show, from a diﬀerent aspect that has been used in [28] and [29], that the Mermin-Wagner theorem is not violated, although at ﬁnite truncation order one would draw the opposite conclusion. An equally interesting ﬁnding is the direct observation of triviality above four Euclidean ∗ † ‡ ##LTLine##

text: Vanishing

label: title

text: beta

text: function

text: curves

text: from

text: the

text: functional

text: renormalisation

text: group

text: P.

label: author

text: Mati

text: and

text: In

label: abstract

text: this

text: paper

text: we

text: will

text: discuss

text: the

text: derivation

text: of

text: the

text: so-called

text: vanishing

text: beta

text: function

text: curves

text: which

text: can

text: be

text: used

text: to

text: explore

text: the

text: ﬁxed

text: point

text: structure

text: of

text: the

text: theory

text: under

text: consideration.

text: This

text: can

text: be

text: applied

text: to

text: the

text: O(N)

text: symmetric

text: theories,

text: essentially,

text: for

text: arbitrary

text: dimensions

text: (D)

text: and

text: ﬁeld

text: com-

text: ponent

text: (N).

text: We

text: will

text: show

text: the

text: restoration

text: of

text: the

text: Mermin-Wagner

text: theorem

text: for

text: theories

text: deﬁned

text: in

text: D

text: and

text: the

text: presence

text: of

text: the

text: Wilson-Fisher

text: ﬁxed

text: point

text: in

text: D

text: Triviality

text: is

text: found

text: in

text: D

text: Interestingly,

text: one

text: needs

text: to

text: make

text: an

text: excursion

text: to

text: the

text: complex

text: plane

text: to

text: see

text: the

text: triviality

text: of

text: the

text: four-dimensional

text: O(N)

text: theories.

text: The

text: large

text: -N

text: analysis

text: shows

text: a

text: new

text: ﬁxed

text: point

text: candidate

text: in

text: D

text: dimensions

text: which

text: turns

text: out

text: to

text: deﬁne

text: an

text: unbounded

text: ﬁxed

text: point

text: potential

text: supporting

text: the

text: recent

text: results

text: by

text: R.

text: Percacci

text: and

text: G.

text: P.

text: Vacca

text: in:

text: ”Are

text: there

text: scaling

text: solutions

text: in

text: the

text: O(N)-models

text: for

text: large

text: -N

text: in

text: D

text: [Phys.

text: Rev.

text: D

text: PACS

text: numbers:

text: Keywords:

text: I.

text: INTRODUCTION

text: There

text: have

text: been

text: many

text: investigations

text: on

text: the

text: phase

text: structure

text: of

text: the

text: scalar

text: O(N)

text: models

text: using

text: functional

text: renormalisation

text: group

text: (FRG)

text: techniques

text: in

text: various

text: dimensions.

text: Critical

text: exponents

text: were

text: computed

text: with

text: high

text: precision,

text: ﬁxed

text: points

text: were

text: found,

text: and

text: many

text: physical

text: aspects

text: seem

text: to

text: be

text: well

text: understood.

text: Hence,

text: we

text: can

text: safely

text: state:

text: the

text: FRG

text: method

text: is

text: a

text: reliable

text: tool

text: for

text: non-perturbative

text: calculations

text: which

text: can

text: be

text: used

text: to

text: consider

text: the

text: phase

text: structure

text: of

text: a

text: model

text: and

text: consequently

text: to

text: study

text: e.g.

text: the

text: appearance

text: of

text: spontaneous

text: symmetry

text: breaking

text: (SSB).

text: For

text: instance,

text: according

text: to

text: the

text: Mermin-Wagner

text: (MW)

text: theorem

text: a

text: continuous

text: symmetry

text: cannot

text: be

text: broken

text: spontaneously

text: below

text: a

text: lower

text: critical

text: dimension,

text: which

text: is

text: D

text: for

text: the

text: O(N)

text: symmetric

text: theory

text: for

text: N

text: This

text: has

text: been

text: recently

text: shown

text: in

text: the

text: framework

text: of

text: FRG

text: Numerical

text: evidence

text: for

text: the

text: MW

text: theorem

text: is

text: presented

text: in

text: The

text: only

text: exception

text: is

text: in

text: D

text: for

text: N

text: (the

text: XY

text: model),

text: when

text: an

text: inﬁnite

text: order

text: phase

text: transition

text: is

text: present

text: That

text: is

text: called

text: the

text: Berezinskii-Kosterlitz-Thouless

text: (BTK)

text: phase

text: transition.

text: To

text: detect

text: this

text: kind

text: of

text: symmetry

text: breaking

text: the

text: local

text: potential

text: approximation

text: (LPA)

text: is

text: not

text: sensitive

text: enough

text: Throughout

text: this

text: paper

text: we

text: will

text: not

text: consider

text: the

text: special

text: case

text: when

text: N

text: in

text: D

text: for

text: these

text: aforementioned

text: reasons.

text: Beyond

text: LPA

text: the

text: BTK

text: phase

text: transition

text: can

text: be

text: observed

text: in

text: the

text: framework

text: of

text: FRG

text: In

text: summary,

text: we

text: can

text: say

text: that

text: the

text: O(N)

text: scalar

text: model

text: represents

text: an

text: excellent

text: playground

text: for

text: testing

text: new

text: techniques.

text: The

text: goal

text: of

text: this

text: paper

text: is

text: to

text: introduce

text: the

text: so-called

text: vanishing

text: beta

text: function

text: (VBF)

text: method

text: in

text: the

text: framework

text: of

text: the

text: O(N)

text: symmetric

text: scalar

text: ﬁeld

text: theory,

text: where

text: the

text: Wetterich

text: FRG

text: equation

text: is

text: used

text: in

text: the

text: LPA

text: assuming

text: that

text: the

text: potential

text: is

text: analytic

text: around

text: the

text: vanishing

text: ﬁeld.

text: There

text: is

text: an

text: extensive

text: study

text: about

text: the

text: radius

text: of

text: convergence

text: of

text: the

text: Taylor-expanded

text: eﬀective

text: potential

text: in

text: the

text: large

text: -N

text: limit

text: of

text: the

text: O(N)

text: model

text: in

text: Expanding

text: around

text: vanishing

text: ﬁeld

text: enables

text: us

text: to

text: provide

text: a

text: one-parameter

text: representation

text: of

text: the

text: ﬁxed

text: point

text: solution

text: which

text: actually

text: deﬁnes

text: the

text: VBF

text: curves

text: through

text: the

text: couplings.

text: This

text: single

text: parameter

text: is

text: the

text: quadratic

text: coupling

text: of

text: the

text: theory

text: and

text: the

text: roots

text: of

text: the

text: VBF

text: curve

text: will

text: deﬁne

text: the

text: position

text: of

text: the

text: ﬁxed

text: points

text: at

text: a

text: given

text: truncation

text: level.

text: In

text: this

text: approach

text: we

text: will

text: lay

text: down

text: general

text: requirements

text: that

text: a

text: root

text: must

text: satisfy

text: in

text: order

text: to

text: deﬁne

text: a

text: stable

text: ﬁxed

text: point

text: potential.

text: Using

text: this

text: polynomial

text: expression

text: for

text: the

text: couplings

text: will

text: reveal

text: an

text: interesting

text: root

text: structure,

text: which

text: depends

text: highly

text: on

text: dimensionality

text: but

text: there

text: is

text: a

text: dependence

text: on

text: N,

text: too,

text: which

text: is

text: rather

text: quantitative.

text: As

text: a

text: consequence

text: of

text: the

text: approximations

text: used

text: in

text: the

text: VBF

text: technique

text: could

text: lead

text: us

text: to

text: potentially

text: artiﬁcial

text: ﬁxed

text: points

text: even

text: in

text: the

text: higher

text: order

text: of

text: truncation.

text: However,

text: it

text: can

text: be

text: shown

text: that

text: these

text: ”spurious”

text: ﬁxed

text: point

text: solutions

text: are

text: excluded

text: by

text: taking

text: the

text: inﬁnite

text: limit

text: in

text: the

text: order

text: of

text: the

text: expansion,

text: although

text: strictly

text: mathematically

text: they

text: must

text: be

text: considered

text: as

text: a

text: valid

text: ﬁxed

text: point

text: at

text: ﬁnite

text: truncation.

text: We

text: will

text: show,

text: from

text: a

text: diﬀerent

text: aspect

text: that

text: has

text: been

text: used

text: in

text: and

text: that

text: the

text: Mermin-Wagner

text: theorem

text: is

text: not

text: violated,

text: although

text: at

text: ﬁnite

text: truncation

text: order

text: one

text: would

text: draw

text: the

text: opposite

text: conclusion.

text: An

text: equally

text: interesting

text: ﬁnding

text: is

text: the

text: direct

text: observation

text: of

text: triviality

text: above

text: four

text: Euclidean

text: ##LTLine##


text: 6 (cid:88) − n 2 g (N, D) = f (Nα)Dj. (18) i i,j j=0 ≤ Interestingly, when setting D 2 the ﬁnding is that all the g ’s are positive for every term, at least till the highest i order (n = 45) that has been considered in the expansion; this is the observation. This fact suggests that the roots (which are not complex) must be either negative or zero. Let us ﬁnd the ﬁxed points according to the rule that has been established in the previous section, using N = 3 and D = 2. The following VBF curves are found: −8π λ = m2(1 + m2)2, 2 5 64π2 (cid:0) (cid:1) λ = m2(1 + m2)3(5 + 27m2), 3 175 −512π3 (cid:0) (cid:1) λ = m2(1 + m2)4 25 + 670m2 + 1671(m2)2 , 4 7875 4096π4 λ = m2(1 + m2)5 175 + 18595m2 + 161115(m2)2 + 254799(m2)3 , 5 606375 ... (19) − Considering only the real roots, we can ﬁnd that they are all situated in the interval [ 1, 0]. In Fig. 1, one can see the plot of the VBF curves versus m2. The mere fact that we can ﬁnd roots is against the Mermin-Wagner theorem, − because for that to hold true, we should have no roots at all, except at the ending points of the interval [ 1, 0]. 5 0  (cid:1) i (cid:1) - (cid:1) / 2 5 (cid:1) / 3 2 4 - 4 - - 5 - - - - 10 1.2 1.0 0.8 0.6 0.4 0.2 0.0 0.2 m2 FIG. 1: The VBF curves for the couplings λ , λ , λ and λ in the O(3), D = 2 model . Each curve is deﬁned by the 2 3 4 5 vanishing beta functions: ∂ m2 = ∂ λ = ∂ λ = ∂ λ = 0 respectively. The roots for λ (m2) are indicated by black t t 2 t 3 t 4 5 dots. These roots are going to deﬁne the ﬁxed point potentials at the truncation level n = 4. Two of its roots are indicated by a green dot and a red triangle to demonstrate a valid and a false ﬁxed point, respectively. At the green ≈ − − dot (m2 0.484) we ﬁnd that λ > 0, and evaluating λ at the red triangle (m2 = 0.137) we get λ < 0, hence 4 4 4 deﬁning an unbounded potential (see Fig. 2). On λ and on λ a scaling is performed for the sake of the presentation. 4 5 We found true ﬁxed point potentials at a ﬁnite truncation level according to Fig. 1, which should not be there as a consequence of MW theorem. The situation is getting worse when we go to higher order in the truncation: indeed, in this case we are going to have more zeros; hence more and more ﬁxed point potentials emerge. How can we resolve − this contradiction? One way to overcome this situation would be that if all the roots between 1 and 0 turned into ##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## ##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##

label: equation

text: n

text: g

text: (N,

text: D)

text: f

text: (Nα)Dj.

text: i

text: i,j

text: Interestingly,

text: when

text: setting

text: D

text: the

text: ﬁnding

text: is

text: that

text: all

text: the

text: g

text: ’s

text: are

text: positive

text: for

text: every

text: term,

text: at

text: least

text: till

text: the

text: highest

text: i

text: order

text: (n

text: that

text: has

text: been

text: considered

text: in

text: the

text: expansion;

text: this

text: is

text: the

text: observation.

text: This

text: fact

text: suggests

text: that

text: the

text: roots

text: (which

text: are

text: not

text: complex)

text: must

text: be

text: either

text: negative

text: or

text: zero.

text: Let

text: us

text: ﬁnd

text: the

text: ﬁxed

text: points

text: according

text: to

text: the

text: rule

text: that

text: has

text: been

text: established

text: in

text: the

text: previous

text: section,

text: using

text: N

text: and

text: D

text: The

text: following

text: VBF

text: curves

text: are

text: found:

text: −8π

text: λ

text: λ

text: λ

text: λ

text: Considering

text: only

text: the

text: real

text: roots,

text: we

text: can

text: ﬁnd

text: that

text: they

text: are

text: all

text: situated

text: in

text: the

text: interval

text: In

text: Fig.

text: one

text: can

text: see

text: the

text: plot

text: of

text: the

text: VBF

text: curves

text: versus

text: The

text: mere

text: fact

text: that

text: we

text: can

text: ﬁnd

text: roots

text: is

text: against

text: the

text: Mermin-Wagner

text: theorem,

text: because

text: for

text: that

text: to

text: hold

text: true,

text: we

text: should

text: have

text: no

text: roots

text: at

text: all,

text: except

text: at

text: the

text: ending

text: points

text: of

text: the

text: interval

text: i

text: FIG.

text: The

text: VBF

text: curves

text: for

text: the

text: couplings

text: λ

text: λ

text: λ

text: and

text: λ

text: in

text: the

text: D

text: model

text: Each

text: curve

text: is

text: deﬁned

text: by

text: the

text: vanishing

text: beta

text: functions:

text: λ

text: λ

text: λ

text: respectively.

text: The

text: roots

text: for

text: λ

text: are

text: indicated

text: by

text: black

text: t

text: t

text: t

text: t

text: dots.

text: These

text: roots

text: are

text: going

text: to

text: deﬁne

text: the

text: ﬁxed

text: point

text: potentials

text: at

text: the

text: truncation

text: level

text: n

text: Two

text: of

text: its

text: roots

text: are

text: indicated

text: by

text: a

text: green

text: dot

text: and

text: a

text: red

text: triangle

text: to

text: demonstrate

text: a

text: valid

text: and

text: a

text: false

text: ﬁxed

text: point,

text: respectively.

text: At

text: the

text: green

text: dot

text: we

text: ﬁnd

text: that

text: λ

text: and

text: evaluating

text: λ

text: at

text: the

text: red

text: triangle

text: we

text: get

text: λ

text: hence

text: deﬁning

text: an

text: unbounded

text: potential

text: (see

text: Fig.

text: On

text: λ

text: and

text: on

text: λ

text: a

text: scaling

text: is

text: performed

text: for

text: the

text: sake

text: of

text: the

text: presentation.

text: We

text: found

text: true

text: ﬁxed

text: point

text: potentials

text: at

text: a

text: ﬁnite

text: truncation

text: level

text: according

text: to

text: Fig.

text: which

text: should

text: not

text: be

text: there

text: as

text: a

text: consequence

text: of

text: MW

text: theorem.

text: The

text: situation

text: is

text: getting

text: worse

text: when

text: we

text: go

text: to

text: higher

text: order

text: in

text: the

text: truncation:

text: indeed,

text: in

text: this

text: case

text: we

text: are

text: going

text: to

text: have

text: more

text: zeros;

text: hence

text: more

text: and

text: more

text: ﬁxed

text: point

text: potentials

text: emerge.

text: How

text: can

text: we

text: resolve

text: this

text: contradiction?

text: One

text: way

text: to

text: overcome

text: this

text: situation

text: would

text: be

text: that

text: if

text: all

text: the

text: roots

text: between

text: and

text: turned

text: into

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

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: THE PARALLEL REPLICA METHOD FOR COMPUTING EQUILIBRIUM AVERAGES OF MARKOV CHAINS DAVID ARISTOFF Abstract. An algorithm is proposed for computing equilibrium averages of Markov chains which suﬀer from metastability – the tendency to remain in one or more subsets of state space for long time intervals. The algorithm, called the parallel replica method (or ParRep), uses many parallel processors to explore these subsets more eﬃciently. Numerical simulations on a simple model demonstrate consistency of the method. A proof of consistency is given in an idealized setting. The parallel replica method can be considered a gen- eralization of A.F. Voter’s parallel replica dynamics, originally developed to eﬃciently simulate metastable Langevin stochastic dynamics. 1. Introduction This article concerns the problem of computing equilibrium averages of time ho- mogeneous, ergodic Markov chains in the presence of metastability. A Markov chain is said to be metastable if it has typically very long sojourn times in certain subsets of state space, called metastable sets. A new method, called the parallel replica method (or ParRep), is proposed for eﬃciently simulating equilibrium averages in this setting. Markov chains are widely used to model physical systems. In computational statistical physics – the main setting for this article – Markov chains are used to understand macroscopic properties of matter, starting from a mesoscopic or microscopic description. Equilibrium averages then correspond to bulk properties of the physical system under consideration, like average density or internal energy. A popular class of such models are the Markov State Models [4, 9, 11]. Markov chains also arise as time discretizations of continuous time models like the Langevin dynamics [8], a popular stochastic model for molecular dynamics. For examples of Markov chain models not obtained from an underlying continuous time dynamics, see for example [3, 12]. It should be emphasized that the discrete in time setting is generic – even if the underlying model is continuous in time, what must be simulated in practice is a time-discretized version. In computational statistical physics, metastability arises from entropic barriers, which are bottlenecks in state space, as well as energetic barriers, which are regions separating metastable states through which crossings are unlikely (due to, for ex- ample, high energy saddle points in a potential energy landscape separating the states). See Figures 1–2 for simple examples of entropic and energetic barriers. Date: 31 December 2014. 2000 Mathematics Subject Classiﬁcation. 65C05, 65C20, 65C40, 60J22, 65Y05. Key words and phrases. Monte Carlo methods, Markov chain Monte Carlo, metastability, parallel computing. 1 ##LTLine##

text: THE

text: PARALLEL

text: REPLICA

text: METHOD

text: FOR

text: COMPUTING

text: EQUILIBRIUM

text: AVERAGES

text: OF

text: MARKOV

text: CHAINS

text: DAVID

text: ARISTOFF

text: Abstract.

text: An

text: algorithm

text: is

text: proposed

text: for

text: computing

text: equilibrium

text: averages

text: of

text: Markov

text: chains

text: which

text: suﬀer

text: from

text: metastability

text: the

text: tendency

text: to

text: remain

text: in

text: one

text: or

text: more

text: subsets

text: of

text: state

text: space

text: for

text: long

text: time

text: intervals.

text: The

text: algorithm,

text: called

text: the

text: parallel

text: replica

text: method

text: (or

text: ParRep),

text: uses

text: many

text: parallel

text: processors

text: to

text: explore

text: these

text: subsets

text: more

text: eﬃciently.

text: Numerical

text: simulations

text: on

text: a

text: simple

text: model

text: demonstrate

text: consistency

text: of

text: the

text: method.

text: A

text: proof

text: of

text: consistency

text: is

text: given

text: in

text: an

text: idealized

text: setting.

text: The

text: parallel

text: replica

text: method

text: can

text: be

text: considered

text: a

text: gen-

text: eralization

text: of

text: A.F.

text: Voter’s

text: parallel

text: replica

text: dynamics,

text: originally

text: developed

text: to

text: eﬃciently

text: simulate

text: metastable

text: Langevin

text: stochastic

text: dynamics.

text: Introduction

text: This

text: article

text: concerns

text: the

text: problem

text: of

text: computing

text: equilibrium

text: averages

text: of

text: time

text: ho-

text: mogeneous,

text: ergodic

text: Markov

text: chains

text: in

text: the

text: presence

text: of

text: metastability.

text: A

text: Markov

text: chain

text: is

text: said

text: to

text: be

text: metastable

text: if

text: it

text: has

text: typically

text: very

text: long

text: sojourn

text: times

text: in

text: certain

text: subsets

text: of

text: state

text: space,

text: called

text: metastable

text: sets.

text: A

text: new

text: method,

text: called

text: the

text: parallel

text: replica

text: method

text: (or

text: ParRep),

text: is

text: proposed

text: for

text: eﬃciently

text: simulating

text: equilibrium

text: averages

text: in

text: this

text: setting.

text: Markov

text: chains

text: are

text: widely

text: used

text: to

text: model

text: physical

text: systems.

text: In

text: computational

text: statistical

text: physics

text: the

text: main

text: setting

text: for

text: this

text: article

text: Markov

text: chains

text: are

text: used

text: to

text: understand

text: macroscopic

text: properties

text: of

text: matter,

text: starting

text: from

text: a

text: mesoscopic

text: or

text: microscopic

text: description.

text: Equilibrium

text: averages

text: then

text: correspond

text: to

text: bulk

text: properties

text: of

text: the

text: physical

text: system

text: under

text: consideration,

text: like

text: average

text: density

text: or

text: internal

text: energy.

text: A

text: popular

text: class

text: of

text: such

text: models

text: are

text: the

text: Markov

text: State

text: Models

text: Markov

text: chains

text: also

text: arise

text: as

text: time

text: discretizations

text: of

text: continuous

text: time

text: models

text: like

text: the

text: Langevin

text: dynamics

text: a

text: popular

text: stochastic

text: model

text: for

text: molecular

text: dynamics.

text: For

text: examples

text: of

text: Markov

text: chain

text: models

text: not

text: obtained

text: from

text: an

text: underlying

text: continuous

text: time

text: dynamics,

text: see

text: for

text: example

text: It

text: should

text: be

text: emphasized

text: that

text: the

text: discrete

text: in

text: time

text: setting

text: is

text: generic

text: even

text: if

text: the

text: underlying

text: model

text: is

text: continuous

text: in

text: time,

text: what

text: must

text: be

text: simulated

text: in

text: practice

text: is

text: a

text: time-discretized

text: version.

text: In

text: computational

text: statistical

text: physics,

text: metastability

text: arises

text: from

text: entropic

text: barriers,

text: which

text: are

text: bottlenecks

text: in

text: state

text: space,

text: as

text: well

text: as

text: energetic

text: barriers,

text: which

text: are

text: regions

text: separating

text: metastable

text: states

text: through

text: which

text: crossings

text: are

text: unlikely

text: (due

text: to,

text: for

text: ex-

text: ample,

text: high

text: energy

text: saddle

text: points

text: in

text: a

text: potential

text: energy

text: landscape

text: separating

text: the

text: states).

text: See

text: Figures

text: for

text: simple

text: examples

text: of

text: entropic

text: and

text: energetic

text: barriers.

text: Date:

text: December

text: Mathematics

text: Subject

text: Classiﬁcation.

text: Key

text: words

text: and

text: phrases.

text: Monte

text: Carlo

text: methods,

text: Markov

text: chain

text: Monte

text: Carlo,

text: metastability,

text: parallel

text: computing.

text: ##LTLine##


text: ixh pudeeps emit ifh PARREP FOR MARKOV CHAINS 11 30 0.25 28 0.2 26 0.15 24 0.1 22 0.05 20 18 0 0 20 40 60 0 20 40 60 T (S ) T (S ) corr 3 corr 3 70 65 60 55 50 0 20 40 60 T (S ) corr 3 Figure 6. Equilibrium average values and (average) time speedup vs. T (S ) in ParRep simulations of the Markov chain from Ex- corr 3 ample 2, with N = 100. The straight lines correspond to exact values. ParRep simulations were stopped when T ﬁrst exceeded sim 109, and error bars are standard deviations obtained from 100 in- dependent trials. For the smallest value of T (S ), the Markov corr 3 chain is typically close to the edges of S , S or S , which results 1 2 3 in shorter parallel steps and thus a smaller time speedup.  Here,  ∈ { } 0.6, x 1, . . . , 15 0.4, x ∈ {16, . . . , 30} p := ∈ { } x 0.65, x 31, . . . , 45 ∈ { } 0.35, x 46, . . . , 60 . The equilibrium distribution µ of this Markov chain can be explicitly computed. bias ##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## ##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## ##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: ixh

font: default

text: pudeeps

text: emit

text: ifh

text: PARREP

text: FOR

text: MARKOV

text: CHAINS

text: T

text: (S

text: T

text: (S

text: corr

text: corr

text: T

text: (S

text: corr

text: Figure

text: Equilibrium

text: average

text: values

text: and

text: (average)

text: time

text: speedup

text: vs.

text: T

text: (S

text: in

text: ParRep

text: simulations

text: of

text: the

text: Markov

text: chain

text: from

text: Ex-

text: corr

text: ample

text: with

text: N

text: The

text: straight

text: lines

text: correspond

text: to

text: exact

text: values.

text: ParRep

text: simulations

text: were

text: stopped

text: when

text: T

text: ﬁrst

text: exceeded

text: sim

text: and

text: error

text: bars

text: are

text: standard

text: deviations

text: obtained

text: from

text: in-

text: dependent

text: trials.

text: For

text: the

text: smallest

text: value

text: of

text: T

text: (S

text: the

text: Markov

text: corr

text: chain

text: is

text: typically

text: close

text: to

text: the

text: edges

text: of

text: S

text: S

text: or

text: S

text: which

text: results

text: in

text: shorter

text: parallel

text: steps

text: and

text: thus

text: a

text: smaller

text: time

text: speedup.

text: Here,

text: x

text: 0.4,

text: x

text: p

text: x

text: x

text: x

text: The

text: equilibrium

text: distribution

text: µ

text: of

text: this

text: Markov

text: chain

text: can

text: be

text: explicitly

text: computed.

text: bias

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

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: ##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: PARREP FOR MARKOV CHAINS 23 (cid:18) (cid:90) (cid:19) So by Lemma 13 and (5.17), 1 = P (cid:32) lim fY (Y0) + . . . + fY (Yn−1) (cid:90)= f(cid:33) dµ ξY n→∞ n Y Y ΩY (5.19) = P lim f(X˜0) + . . . + f(X˜n−1) = f dµ(cid:48) . ξ n→∞ n Ω Also, by Lemma 14 and (5.18), |P ∈ × { } − × { } | 0 = lim sup (Y A 0, . . . , T ) µ (A 0, . . . , T ) n→∞ A∈F ξY n corr Y corr |P ∈ − (cid:48) | = lim sup (X A) µ (A) n→∞ A∈F ξ n ||P ∈ · − (cid:48)|| = lim (X ) µ . n→∞ ξ(cid:32) n (cid:90) (cid:33) (cid:48) Using Assumption 7 one can conclude µ = µ . So from (5.19), P lim f(X˜0) + . . . + f(X˜n−1) = f dµ = 1. ξ n→∞ n Ω (cid:3) Here the main result, Theorem 10, is ﬁnally proved. The idea is to use ergodicity of (X˜ ) ≥ along with the fact that the average value of the contribution to f n n 0 sim from a Parallel Step of Algorithm 2 does not depend on the number of replicas. A law of large numbers applied to the contributions to f from all the Parallel sim Steps will then be enough to conclude. Note that the law of (f ) ≥ depends sim Tsim 0 on the number N of replicas, but this is not indicated explicitly. F Proof of Theorem 10. Fix a pr(cid:40)obability measure ξ on (Ω, ) and a bounded mea- surable function f : Ω → R. Deﬁne fˆ : Ω → R by Y ∈ { − } f(x), t 0, . . . , T 1 fˆ(x, t) = corr 0, t = T corr Let Algorithm 2 start at ξ. The quantity f will be decomposed into contributions sim from the Decorrelation Step and the Parallel Step. Let fcorr denote the contribution sim to f from the Decorrelation Step up to time T , and let fpar denote the sim sim sim contribution to f from the Parallel Step up to time T . Thus, sim sim (f ) ≥ = (fcorr + fpar) ≥ . (5.20) sim Tsim 0 sim sim Tsim 0 ∼ Let (Y ) ≥ start at Y ξ , with ξ deﬁned as in (5.16). Because the starting n n 0 0 Y Y points x , . . . , x sampled in the Dephasing Step are independent of the history of 1 N algorithm, each Parallel Step – in particular the pair (τ , XK ) – is independent acc τK of the history of the algorithm. This and Theorem 6 imply that (fcorr) ≥ has sim Tcorr 0 the same law for every number of replicas N. In particular when N = 1, from Lemma 13, ##LTLine## ##LTLine## ##LTLine##

text: PARREP

text: FOR

text: MARKOV

text: CHAINS

text: So

text: by

text: Lemma

text: and

text: P

text: lim

text: fY

text: fY

text: dµ

text: ξY

text: n→∞

text: n

text: Y

text: Y

text: ΩY

text: P

text: lim

text: f

text: ξ

text: n→∞

text: n

text: Ω

text: Also,

text: by

text: Lemma

text: and

text: |P

text: lim

text: sup

text: (Y

text: A

text: T

text: µ

text: (A

text: T

text: n→∞

text: A∈F

text: ξY

text: n

text: corr

text: Y

text: corr

text: |P

text: lim

text: sup

text: (X

text: A)

text: µ

text: (A)

text: n→∞

text: A∈F

text: ξ

text: n

text: ||P

text: lim

text: (X

text: µ

text: n→∞

text: n

text: Using

text: Assumption

text: one

text: can

text: conclude

text: µ

text: µ

text: So

text: from

text: P

text: lim

text: f

text: dµ

text: ξ

text: n→∞

text: n

text: Ω

text: Here

text: the

text: main

text: result,

text: Theorem

text: is

text: ﬁnally

text: proved.

text: The

text: idea

text: is

text: to

text: use

text: ergodicity

text: of

text: (X˜

text: along

text: with

text: the

text: fact

text: that

text: the

text: average

text: value

text: of

text: the

text: contribution

text: to

text: f

text: n

text: n

text: sim

text: from

text: a

text: Parallel

text: Step

text: of

text: Algorithm

text: does

text: not

text: depend

text: on

text: the

text: number

text: of

text: replicas.

text: A

text: law

text: of

text: large

text: numbers

text: applied

text: to

text: the

text: contributions

text: to

text: f

text: from

text: all

text: the

text: Parallel

text: sim

text: Steps

text: will

text: then

text: be

text: enough

text: to

text: conclude.

text: Note

text: that

text: the

text: law

text: of

text: (f

text: depends

text: sim

text: Tsim

text: on

text: the

text: number

text: N

text: of

text: replicas,

text: but

text: this

text: is

text: not

text: indicated

text: explicitly.

text: F

text: Proof

text: of

text: Theorem

text: Fix

text: a

text: measure

text: ξ

text: on

text: (Ω,

text: and

text: a

text: bounded

text: mea-

text: surable

text: function

text: f

text: Ω

text: R.

text: Deﬁne

text: fˆ

text: Ω

text: R

text: by

text: Y

text: f(x),

text: t

text: T

text: fˆ(x,

text: t)

text: corr

text: t

text: T

text: corr

text: Let

text: Algorithm

text: start

text: at

text: ξ.

text: The

text: quantity

text: f

text: will

text: be

text: decomposed

text: into

text: contributions

text: sim

text: from

text: the

text: Decorrelation

text: Step

text: and

text: the

text: Parallel

text: Step.

text: Let

text: fcorr

text: denote

text: the

text: contribution

text: sim

text: to

text: f

text: from

text: the

text: Decorrelation

text: Step

text: up

text: to

text: time

text: T

text: and

text: let

text: fpar

text: denote

text: the

text: sim

text: sim

text: sim

text: contribution

text: to

text: f

text: from

text: the

text: Parallel

text: Step

text: up

text: to

text: time

text: T

text: Thus,

text: sim

text: sim

text: (f

text: (fcorr

text: fpar)

text: sim

text: Tsim

text: sim

text: sim

text: Tsim

text: Let

text: (Y

text: start

text: at

text: Y

text: ξ

text: with

text: ξ

text: deﬁned

text: as

text: in

text: Because

text: the

text: starting

text: n

text: n

text: Y

text: Y

text: points

text: x

text: x

text: sampled

text: in

text: the

text: Dephasing

text: Step

text: are

text: independent

text: of

text: the

text: history

text: of

text: N

text: algorithm,

text: each

text: Parallel

text: Step

text: in

text: particular

text: the

text: pair

text: (τ

text: XK

text: is

text: independent

text: acc

text: τK

text: of

text: the

text: history

text: of

text: the

text: algorithm.

text: This

text: and

text: Theorem

text: imply

text: that

text: (fcorr)

text: has

text: sim

text: Tcorr

text: the

text: same

text: law

text: for

text: every

text: number

text: of

text: replicas

text: N.

text: In

text: particular

text: when

text: N

text: from

text: Lemma

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 26 DAVID ARISTOFF [1] D. Aristoff, T. Lelie`vre and G. Simpson, The parallel replica method for simulating long trajectories of Markov chains, Applied Mathematics Research eXpress 2014(2): 332–352 (2014) [2] A. Binder, T. Lelie`vre and G. Simpson, A generalized parallel replica dynamics, J. Com- put. Phys. 284: 595–616 (2015) [3] A. Bovier, M. Eckhoff, V. Gayrard, and M. Klein, Metastability and low lying spectra in reversible Markov chains, Commun. Math. Phys. 228(2): 219–255 (2002) [4] J.D. Chodera, N. Singhal, V.S. Pande, K.A. Dill, and W.C. Swope, Automatic discovery of metastable states for the construction of Markov models of macromolecular conformational dynamics, J. Chem. Phys. 126(15): 155101 (2007) [5] R. Douc, E. Moulines, and D. Stoffer. Nonlinear time series: theory, methods and applications with examples. CRC Press (2014) [6] R. Durrett. Probability: Theory and examples. Cambridge U. Press, 4th edn (2010) [7] C. Le Bris, T. Lelie`vre, M. Luskin, and D. Perez, A mathematical formulation of the parallel replica dynamics, Monte Carlo Methods Appl. 18:119–146 (2012) [8] T. Lelie`vre, G. Stoltz, and M. Rousset. Free Energy Computations: A Mathematical Perspective. Imperial College Press (2010) [9] J.H. Prinz, H. Wu, M. Sarich, B. Keller, M. Senne, M. Held, J.D. Chodera, C. Schu¨tte, and F. Noe´, Markov models of molecular kinetics: Generation and valida- tion. J. Chem. Phys. 134 (17): 174105 (2011) [10] R.Y. Rubinstein and D.P Kroese. Simulation and the Monte Carlo Method, Wiley, 2nd edn (2007) [11] C. Schu¨tte and M. Sarich. Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches. Courant Lecture Notes (2010) [12] E. Scoppola. Metastability for Markov chains: A general procedure based on renormalization group ideas. In G. Grimmett, editor, Probability and Phase Transition, volume 420 of NATO ASI Series, pp. 303–322, Springer Verlag (1994) [13] G. Simpson and M. Luskin, Numerical analysis of parallel replica dynamics, ESAIM: M2AN 47(5): 1287–1314 (2013) [14] A.F. Voter, Parallel replica method for dynamics of infrequent events, Phys. Rev. B 57(22): 13985–13988 (1998) Department of Mathematics Colorado State University Email address: aristoff@math.colostate.edu

text: DAVID

text: ARISTOFF

text: D.

text: Aristoff,

text: T.

text: Lelie`vre

text: and

text: G.

text: Simpson,

text: The

text: parallel

text: replica

text: method

text: for

text: simulating

text: long

text: trajectories

text: of

text: Markov

text: chains,

text: Applied

text: Mathematics

text: Research

text: eXpress

text: A.

text: Binder,

text: T.

text: Lelie`vre

text: and

text: G.

text: Simpson,

text: A

text: generalized

text: parallel

text: replica

text: dynamics,

text: J.

text: Com-

text: put.

text: Phys.

text: A.

text: Bovier,

text: M.

text: Eckhoff,

text: V.

text: Gayrard,

text: and

text: M.

text: Klein,

text: Metastability

text: and

text: low

text: lying

text: spectra

text: in

text: reversible

text: Markov

text: chains,

text: Commun.

text: Math.

text: Phys.

text: J.D.

text: Chodera,

text: N.

text: Singhal,

text: V.S.

text: Pande,

text: K.A.

text: Dill,

text: and

text: W.C.

text: Swope,

text: Automatic

text: discovery

text: of

text: metastable

text: states

text: for

text: the

text: construction

text: of

text: Markov

text: models

text: of

text: macromolecular

text: conformational

text: dynamics,

text: J.

text: Chem.

text: Phys.

text: R.

text: Douc,

text: E.

text: Moulines,

text: and

text: D.

text: Stoffer.

text: Nonlinear

text: time

text: series:

text: theory,

text: methods

text: and

text: applications

text: with

text: examples.

text: CRC

text: Press

text: R.

text: Durrett.

text: Probability:

text: Theory

text: and

text: examples.

text: Cambridge

text: U.

text: Press,

text: edn

text: C.

text: Le

text: Bris,

text: T.

text: Lelie`vre,

text: M.

text: Luskin,

text: and

text: D.

text: Perez,

text: A

text: mathematical

text: formulation

text: of

text: the

text: parallel

text: replica

text: dynamics,

text: Monte

text: Carlo

text: Methods

text: Appl.

text: T.

text: Lelie`vre,

text: G.

text: Stoltz,

text: and

text: M.

text: Rousset.

text: Free

text: Energy

text: Computations:

text: A

text: Mathematical

text: Perspective.

text: Imperial

text: College

text: Press

text: J.H.

text: Prinz,

text: H.

text: Wu,

text: M.

text: Sarich,

text: B.

text: Keller,

text: M.

text: Senne,

text: M.

text: Held,

text: J.D.

text: Chodera,

text: C.

text: Schu¨tte,

text: and

text: F.

text: Noe´,

text: Markov

text: models

text: of

text: molecular

text: kinetics:

text: Generation

text: and

text: valida-

text: tion.

text: J.

text: Chem.

text: Phys.

text: R.Y.

text: Rubinstein

text: and

text: D.P

text: Kroese.

text: Simulation

text: and

text: the

text: Monte

text: Carlo

text: Method,

text: Wiley,

text: edn

text: C.

text: Schu¨tte

text: and

text: M.

text: Sarich.

text: Metastability

text: and

text: Markov

text: State

text: Models

text: in

text: Molecular

text: Dynamics:

text: Modeling,

text: Analysis,

text: Algorithmic

text: Approaches.

text: Courant

text: Lecture

text: Notes

text: E.

text: Scoppola.

text: Metastability

text: for

text: Markov

text: chains:

text: A

text: general

text: procedure

text: based

text: on

text: renormalization

text: group

text: ideas.

text: In

text: G.

text: Grimmett,

text: editor,

text: Probability

text: and

text: Phase

text: Transition,

text: volume

text: of

text: NATO

text: ASI

text: Series,

text: pp.

text: Springer

text: Verlag

text: G.

text: Simpson

text: and

text: M.

text: Luskin,

text: Numerical

text: analysis

text: of

text: parallel

text: replica

text: dynamics,

text: ESAIM:

text: A.F.

text: Voter,

text: Parallel

text: replica

text: method

text: for

text: dynamics

text: of

text: infrequent

text: events,

text: Phys.

text: Rev.

text: B

text: Department

text: of

text: Mathematics

text: Colorado

text: State

text: University

text: Email

text: address:

text: aristoff@math.colostate.edu