text: The theoretical properties of the PG kernel, however, are not as well understood. Andrieu et al. (2010) establish under weak conditions that the PG kernel is φ-irreducible and aperiodic ≥ for any N 2 (see Meyn and Tweedie (2009) for deﬁnitions). However, this does not provide a control for the rate of convergence of the iterates of the PG kernel to stationarity. In this work, we establish that the PG kernel is, under mild assumptions, uniformly ergodic. This interesting property has already been established in an earlier work by Chopin and Singh (2013), but we give here a more straightforward proof under weaker conditions, which in addition provides an explicit lower bound for the convergence rate. During the preparation of this manuscript, a preprint was made available by Andrieu et al. (2013), who, independently, have found similar results as presented here. Indeed, they establish basically the same lower bound on the minorizing constant for the PG kernel (which they refer to as the iterated conditional SMC kernel), though using a diﬀerent proof technique based on a “doubly conditional” SMC algorithm. There are, however, several diﬀerences between these two contributions. We focus in particular on analyzing the minorizing constant under mixing conditions for the state space model which hold very generally, even if the state space is not compact (see Section ). We then study how the number of particles N should be increased with the number of observations T. We show that under weak assumptions, it suﬃces to increase the ≥ number of particles N as Tδ where δ 1 can be determined explicitly. This is in contrast with Andrieu et al. (2013) who, eﬀectively, assume a compact state space; see Remark 3 and Section . On the other hand, Andrieu et al. (2013) study necessary (i.e., not only suﬃcient) conditions for uniform ergodicity and translate the convergence results for the PG kernel to a composite MCMC scheme for simulating both states and parameters of a state space model. Given these diﬀerences, we believe that the two contributions complement each other. This paper is organized as follows: In Section we introduce our notation, and in Section we review the PG sampler and formally deﬁne the PG Markov kernel. In Section we state the main results, starting with a minorization condition for the PG kernel followed by mixing conditions that allow for time uniform control of the convergence rate. In Section we study, in detail, two commonly used state space models (with non-compact state spaces) to illustrate how the conditions of our results can be veriﬁed in practice. The proofs of the main theorems are postponed to Sections and . 2 Notations and problem statement X Y P Let (X, ) and (Y, ) be two measurable spaces and let (X) be the set of all probability X X Y measures on (X, ). Let M be a kernel on (X, ) and G a kernel on (X, ). Assume that for ∈ · Y all x X, G(x, ) is dominated by some common nonnegative measure κ on (Y, ) and denote · ∈ × by g(x, ) its Radon-Nikodym derivative, i.e., for all (x, y) X Y, · dG(x, ) g(x, y) = · (y) . dκ( ) { ∈ N} Let (X , Y ) , t be a hidden Markov chain associated to the pair (M, G). That is, { t t∈ N} (cid:90)(cid:90) ∈ × (X , Y ) , t is a Markov chain with transition kernel deﬁned by: for all (x, y) X Y and t ∈tX ⊗ Y all C , (cid:55)→ (cid:48) (cid:48) (cid:48) ((x, y), C) M(x, dx )G(x , dy ) . C { ∈ N} The sequence X , t is usually not observed and inference should be carry out on the basis t { ∈ N} ∈ P of the observations Y , t only. With µ (X) being the initial distribution of the hidden t 3 ##LTLine##

text: The

text: theoretical

text: properties

text: of

text: the

text: PG

text: kernel,

text: however,

text: are

text: not

text: as

text: well

text: understood.

text: Andrieu

text: et

text: al.

text: establish

text: under

text: weak

text: conditions

text: that

text: the

text: PG

text: kernel

text: is

text: φ-irreducible

text: and

text: aperiodic

text: for

text: any

text: N

text: (see

text: Meyn

text: and

text: Tweedie

text: for

text: deﬁnitions).

text: However,

text: this

text: does

text: not

text: provide

text: a

text: control

text: for

text: the

text: rate

text: of

text: convergence

text: of

text: the

text: iterates

text: of

text: the

text: PG

text: kernel

text: to

text: stationarity.

text: In

text: this

text: work,

text: we

text: establish

text: that

text: the

text: PG

text: kernel

text: is,

text: under

text: mild

text: assumptions,

text: uniformly

text: ergodic.

text: This

text: interesting

text: property

text: has

text: already

text: been

text: established

text: in

text: an

text: earlier

text: work

text: by

text: Chopin

text: and

text: Singh

text: but

text: we

text: give

text: here

text: a

text: more

text: straightforward

text: proof

text: under

text: weaker

text: conditions,

text: which

text: in

text: addition

text: provides

text: an

text: explicit

text: lower

text: bound

text: for

text: the

text: convergence

text: rate.

text: During

text: the

text: preparation

text: of

text: this

text: manuscript,

text: a

text: preprint

text: was

text: made

text: available

text: by

text: Andrieu

text: et

text: al.

text: who,

text: independently,

text: have

text: found

text: similar

text: results

text: as

text: presented

text: here.

text: Indeed,

text: they

text: establish

text: basically

text: the

text: same

text: lower

text: bound

text: on

text: the

text: minorizing

text: constant

text: for

text: the

text: PG

text: kernel

text: (which

text: they

text: refer

text: to

text: as

text: the

text: iterated

text: conditional

text: SMC

text: kernel),

text: though

text: using

text: a

text: diﬀerent

text: proof

text: technique

text: based

text: on

text: a

text: “doubly

text: conditional”

text: SMC

text: algorithm.

text: There

text: are,

text: however,

text: several

text: diﬀerences

text: between

text: these

text: two

text: contributions.

text: We

text: focus

text: in

text: particular

text: on

text: analyzing

text: the

text: minorizing

text: constant

text: under

text: mixing

text: conditions

text: for

text: the

text: state

text: space

text: model

text: which

text: hold

text: very

text: generally,

text: even

text: if

text: the

text: state

text: space

text: is

text: not

text: compact

text: (see

text: Section

text: We

text: then

text: study

text: how

text: the

text: number

text: of

text: particles

text: N

text: should

text: be

text: increased

text: with

text: the

text: number

text: of

text: observations

text: T.

text: We

text: show

text: that

text: under

text: weak

text: assumptions,

text: it

text: suﬃces

text: to

text: increase

text: the

text: number

text: of

text: particles

text: N

text: as

text: Tδ

text: where

text: δ

text: can

text: be

text: determined

text: explicitly.

text: This

text: is

text: in

text: contrast

text: with

text: Andrieu

text: et

text: al.

text: who,

text: eﬀectively,

text: assume

text: a

text: compact

text: state

text: space;

text: see

text: Remark

text: and

text: Section

text: On

text: the

text: other

text: hand,

text: Andrieu

text: et

text: al.

text: study

text: necessary

text: (i.e.,

text: not

text: only

text: suﬃcient)

text: conditions

text: for

text: uniform

text: ergodicity

text: and

text: translate

text: the

text: convergence

text: results

text: for

text: the

text: PG

text: kernel

text: to

text: a

text: composite

text: MCMC

text: scheme

text: for

text: simulating

text: both

text: states

text: and

text: parameters

text: of

text: a

text: state

text: space

text: model.

text: Given

text: these

text: diﬀerences,

text: we

text: believe

text: that

text: the

text: two

text: contributions

text: complement

text: each

text: other.

text: This

text: paper

text: is

text: organized

text: as

text: follows:

text: In

text: Section

text: we

text: introduce

text: our

text: notation,

text: and

text: in

text: Section

text: we

text: review

text: the

text: PG

text: sampler

text: and

text: formally

text: deﬁne

text: the

text: PG

text: Markov

text: kernel.

text: In

text: Section

text: we

text: state

text: the

text: main

text: results,

text: starting

text: with

text: a

text: minorization

text: condition

text: for

text: the

text: PG

text: kernel

text: followed

text: by

text: mixing

text: conditions

text: that

text: allow

text: for

text: time

text: uniform

text: control

text: of

text: the

text: convergence

text: rate.

text: In

text: Section

text: we

text: study,

text: in

text: detail,

text: two

text: commonly

text: used

text: state

text: space

text: models

text: (with

text: non-compact

text: state

text: spaces)

text: to

text: illustrate

text: how

text: the

text: conditions

text: of

text: our

text: results

text: can

text: be

text: veriﬁed

text: in

text: practice.

text: The

text: proofs

text: of

text: the

text: main

text: theorems

text: are

text: postponed

text: to

text: Sections

text: and

text: Notations

text: and

text: problem

text: statement

text: X

text: Y

text: P

text: Let

text: (X,

text: and

text: (Y,

text: be

text: two

text: measurable

text: spaces

text: and

text: let

text: (X)

text: be

text: the

text: set

text: of

text: all

text: probability

text: X

text: X

text: Y

text: measures

text: on

text: (X,

text: Let

text: M

text: be

text: a

text: kernel

text: on

text: (X,

text: and

text: G

text: a

text: kernel

text: on

text: (X,

text: Assume

text: that

text: for

text: Y

text: all

text: x

text: X,

text: G(x,

text: is

text: dominated

text: by

text: some

text: common

text: nonnegative

text: measure

text: κ

text: on

text: (Y,

text: and

text: denote

text: by

text: g(x,

text: its

text: Radon-Nikodym

text: derivative,

text: i.e.,

text: for

text: all

text: (x,

text: y)

text: X

text: Y,

text: dG(x,

text: g(x,

text: y)

text: (y)

text: dκ(

text: N}

text: Let

text: (X

text: Y

text: t

text: be

text: a

text: hidden

text: Markov

text: chain

text: associated

text: to

text: the

text: pair

text: (M,

text: G).

text: That

text: is,

text: t

text: t∈

text: N}

text: (X

text: Y

text: t

text: is

text: a

text: Markov

text: chain

text: with

text: transition

text: kernel

text: deﬁned

text: by:

text: for

text: all

text: (x,

text: y)

text: X

text: Y

text: and

text: t

text: ∈tX

text: Y

text: all

text: C

text: ((x,

text: y),

text: C)

text: M(x,

text: dx

text: )G(x

text: dy

text: C

text: N}

text: The

text: sequence

text: X

text: t

text: is

text: usually

text: not

text: observed

text: and

text: inference

text: should

text: be

text: carry

text: out

text: on

text: the

text: basis

text: t

text: N}

text: P

text: of

text: the

text: observations

text: Y

text: t

text: only.

text: With

text: µ

text: (X)

text: being

text: the

text: initial

text: distribution

text: of

text: the

text: hidden

text: t

text: ##LTLine##


text: (cid:98) (cid:98) { (cid:104) (cid:105)} {F } ∈ Since by Lemma 15, Cθ Y ≥ is a ≥ -martingale and α (0, 1), we have that { (cid:104) (cid:105) } t 0:t+(cid:96) k {0F } t+(cid:96) (cid:96) 0 th(Centθ aYp0p:tl+ie(cid:96)s:)αfor(cid:20)(cid:96)≥a0llisaa>(cid:98)n0o,nnegative (cid:12)(cid:12)(cid:12)(cid:12)t+(cid:96) (cid:96)≥0-s(cid:21)uperma(cid:104)rtin(cid:98)gale. The Do(cid:12)(cid:12)(cid:12)ob maxim(cid:105) al inequality P (cid:104) (cid:105) ≥ F ≤ E (cid:104) (cid:105) F a θ sup(Cθ Y )α a − θ (Cθ Y )α − . µ ≥ t 0:t+(cid:96) t+(cid:96)(cid:63) 1 µ t 0:t+(cid:96)(cid:63) t+(cid:96)(cid:63) 1 (cid:96) (cid:96)(cid:63) (cid:20) (cid:21) (cid:104) (cid:105) Take now the expectation in(cid:98)both sides of the previous inequ(cid:98)ality and set δ = aγ/α. We obtain P (cid:104) (cid:105) ≥ ≤ − E (cid:104) (cid:105) θ sup(Cθ Y )γ δ (cid:82) δ α/γ θ (Cθ Y )α . µ ≥ t 0:t+(cid:96) µ t 0:t+(cid:96)(cid:63) (cid:96) (cid:96)(cid:63) E ≤ ∞ P Combining this wi(cid:20)th the inequality (cid:21)[U] 1(cid:18)+(cid:90) 1 [U > δ(cid:19)] dδ (cid:104)which holds for(cid:105)all nonnegative random variable U, we o(cid:98)btain under (cid:98) ∞ E (cid:104) (cid:105) ≤ − (cid:104) E (cid:104)(cid:105) (cid:105) θ sup(Cθ Y )γ 1 + δ α/γ(cid:98)dδ θ (Cθ Y )α µ ≥ t 0:t+(cid:96) µ t 0:t+(cid:96)(cid:63) (cid:96) (cid:96)(cid:63) 1 γ E (cid:104) (cid:105) = 1 + − θ (Cθ Y )α . α γ µ t 0:t+(cid:96)(cid:63) The proof follows by applying again Lemma 16 under . Proof of Theorem 6. For simplicity we will use in this proof the notations p¯θ(Y ) := pθ (Y ) (cid:26) | (cid:27) | (cid:40) 0:t π(cid:41)θ 0:t and p¯θ(Y Y − ) = pθ (Y Y − ). First note that t:s 0:t 1 πθ t:s 0:t 1 P¯θ(cid:63) p¯θ(cid:63)(Y0:T ) > ρ = P¯θ(cid:63) (cid:40)ln p¯θ(cid:63)(Y0:T ) + pθµT (Y0:T ) − 1 > ln ρ + p(cid:41)θµT (Y0:T ) − 1 pθµT (Y0:T ) pθµT (Y0:T ) p¯θ(cid:63)(Y0:T ) p¯θ(cid:63)(Y0:T ) ≤ P¯θ(cid:63) ln p¯θ(cid:63)(Y0:T ) + pθµT (Y0:T ) − 1 > ln ρ − 1 . pθµT (Y0:T ) p¯θ(cid:63)(Y0:T ) (cid:26) (cid:27)− − ≥ (cid:34) (cid:35) Now, since for all u > 0, ln(u) + u 1 1 0, we obtain for for all ρ > e = exp(1): P¯θ(cid:63) p¯θ(cid:63)(Y0:T ) > ρ ≤ 1− E¯θ(cid:63) (cid:20)ln p¯θ(cid:63)(Y0:T )(cid:21)+ pθµT (Y0:T ) − 1 pθµT (Y0:T ) ln ρ 1 pθµT (Y0:T ) p¯θ(cid:63)(Y0:T ) = 1− E¯θ(cid:63) ln p¯θ(cid:63)(Y0:T ) . ln ρ 1 pθµT (Y0:T ) This implies that for all M > 0 and all ρ > e,  (cid:26) (cid:27)     (cid:40) (cid:41) (cid:110) (cid:111) P¯θ(cid:63)((cid:15)−T,1NT (θT ) > M) ≤ EθµT (cid:104)pp¯θµθT(cid:63)((YY00::TT ))1 pp¯θµθT(cid:63)(cid:105)((YY00::TT))≤ρ 1 (cid:15)−T,1NT(cid:20)(θT)>M + (cid:21)P¯θ(cid:63) pp¯θµθT(cid:63)((YY00::TT )) > ρ ≤ ρPθµT (cid:104)(cid:15)−T,1NT (θT ) > M(cid:105) + ln ρ1− 1E¯(cid:18)θ(cid:63) ln pp¯θµθT(cid:63)(cid:20)((YY00::TT )) (cid:21)(cid:19) ≤ ρPθµT (cid:15)−T,1NT (θT ) > M + ln ρ1− 1 Tsu≥p0 E¯θ(cid:63) ln pp¯θµθT(cid:63)((YY00::TT )) . (90) 26 ##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: paragraph

text: {F

text: Since

text: by

text: Lemma

text: Cθ

text: Y

text: is

text: a

text: -martingale

text: and

text: α

text: we

text: have

text: that

text: t

text: k

text: th(Centθ

text: The

text: al

text: inequality

text: P

text: F

text: E

text: F

text: a

text: θ

text: sup(Cθ

text: Y

text: )α

text: a

text: θ

text: (Cθ

text: Y

text: )α

text: µ

text: t

text: µ

text: t

text: Take

text: now

text: the

text: expectation

text: sides

text: of

text: the

text: previous

text: and

text: set

text: δ

text: aγ/α.

text: We

text: obtain

text: P

text: E

text: θ

text: sup(Cθ

text: Y

text: )γ

text: δ

text: δ

text: α/γ

text: θ

text: (Cθ

text: Y

text: )α

text: µ

text: t

text: µ

text: t

text: E

text: P

text: Combining

text: this

text: the

text: inequality

text: [U

text: dδ

text: holds

text: nonnegative

text: random

text: variable

text: U,

text: we

text: under

text: E

text: E

text: θ

text: sup(Cθ

text: Y

text: )γ

text: δ

text: θ

text: (Cθ

text: Y

text: )α

text: µ

text: t

text: µ

text: t

text: γ

text: E

text: θ

text: (Cθ

text: Y

text: )α

text: α

text: γ

text: µ

text: t

text: The

text: proof

text: follows

text: by

text: applying

text: again

text: Lemma

text: under

text: Proof

text: of

text: Theorem

text: For

text: simplicity

text: we

text: will

text: use

text: in

text: this

text: proof

text: the

text: notations

text: p¯θ(Y

text: pθ

text: (Y

text: and

text: p¯θ(Y

text: Y

text: pθ

text: (Y

text: Y

text: First

text: note

text: that

text: t:s

text: πθ

text: t:s

text: ρ

text: pθµT

text: ln

text: ρ

text: pθµT

text: pθµT

text: ln

text: pθµT

text: ln

text: ρ

text: pθµT

text: Now,

text: since

text: for

text: all

text: u

text: ln(u)

text: u

text: we

text: obtain

text: for

text: for

text: all

text: ρ

text: e

text: ρ

text: 1−

text: pθµT

text: pθµT

text: ln

text: ρ

text: pθµT

text: 1−

text: ln

text: ln

text: ρ

text: pθµT

text: This

text: implies

text: that

text: for

text: all

text: M

text: and

text: all

text: ρ

text: e,

text: (θT

text: M)

text: EθµT

text: ρ

text: ρPθµT

text: (θT

text: ln

text: ρ1−

text: ln

text: ρPθµT

text: (θT

text: M

text: ln

text: ρ1−

text: ln

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ≥ (cid:90) (cid:89) state process, for all t 0, denote by (cid:55)→ t y p (y ) := µ(dx )g(x , y ) M(x − , dx )g(x , y ) , 0:t µ 0:t 0 0 0 s 1 s s s s=1 ⊗ the density of the observations Y with respect to κ (t+1). In what follows, we set, by abuse ∈ 0:t of notation, for all x X, p (y ) = p (y ) , (1) x 0:t δx 0:t where δx ∈is the Dirac measure at x. (cid:90) (cid:104) (cid:105) X For all y Y, deﬁne the (unnormalized) kernel Q y on (X, ) by (cid:104) (cid:105) (cid:48) (cid:48) (cid:48) Q y (x, A) = M(x, dx )g(x , y)1A(x ) , (2) ≤ ∈ − (cid:104) (cid:105) X and for all s t and all y Yt s+1, deﬁne the kernel Q y on (X, ) by s:t s:t (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) (cid:104) (cid:105) Q y (x, A) = Q y Q y . . . Q y (x, A) . (3) s:t s s+1 t (cid:104) (cid:105) In what follows, we set by convention Q y (x, A) = 1 for all s > t. With these notations, (cid:104) (cid:105) s:t ∈ ∈ P p (y ) = µQ y 1 where 1 is the(cid:40)constant function, 1(x) = 1 for all x X. For all µ (X) µ 0:t ≤ 0:≤t and for all 0 s t, denote (cid:54) | p (y )/p (y − ) , if p (y − ) = 0 , p (y y − ) := µ 0:t µ 0:s 1 µ 0:s 1 µ s:t 0:s 1 0 , otherwise | with the convention p (y y − ) = p (y ). µ 0:t 0: 1 µ 0:t A quantity of central interest i(cid:90)s the JSD, given by (cid:89) (cid:104) (cid:105) 1 t φµ,0:t y0:t (D) := p (y ) µ(dx0)g(x0, y0) M(xs−1, dxs)g(xs, ys)1D(x0:t) , (4) µ 0:t s=1 ∈ X⊗ for all D (t+1). With T being some ﬁnal time point, the PG sampler (reviewed in (cid:104) (cid:105) the subsequent section) deﬁnes a Markov kernel which is reversible with respect to φ y . µ,0:T 0:T Samples drawn from the PG kernel can thus be used to draw inference about the states (and/or parameters) of the state space model. 3 The particle Gibbs sampler Consider ﬁrst an SMC sampler targeting the sequence of JSDs deﬁned in (4). The SMC (cid:104) (cid:105) { } sampler approximates φ Y by a collection of weighted samples (Xi , ωi) N , in the µ,0:t 0:t (cid:88) 0:t t i=1 sense that (cid:80) (cid:104) (cid:105) N ωi φN Y (h) := t h(Xi ) µ,0:t 0:T N ω(cid:96) 0:t i=1 (cid:96)=1 t (cid:104) (cid:105) → R is an estimator of φ Y (h) for a measurable function h : Xt+1 . These weighted µ,0:t 0:t samples can be generated in several diﬀerent ways, see e.g. Doucet et al. (2000); Del Moral 4 ##LTLine## ##LTLine##

text: state

text: process,

text: for

text: all

text: t

text: denote

text: by

text: t

text: y

text: p

text: (y

text: µ(dx

text: )g(x

text: y

text: M(x

text: dx

text: )g(x

text: y

text: µ

text: s

text: s

text: s

text: s

text: the

text: density

text: of

text: the

text: observations

text: Y

text: with

text: respect

text: to

text: κ

text: In

text: what

text: follows,

text: we

text: set,

text: by

text: abuse

text: of

text: notation,

text: for

text: all

text: x

text: X,

text: p

label: equation

text: (y

text: p

text: (y

text: x

text: δx

text: where

text: δx

text: ∈is

text: the

text: Dirac

text: measure

text: at

text: x.

text: X

text: For

text: all

text: y

text: Y,

text: deﬁne

text: the

text: (unnormalized)

text: kernel

text: Q

text: y

text: on

text: (X,

text: by

text: Q

text: y

text: (x,

text: A)

text: M(x,

text: dx

text: )g(x

text: X

text: and

text: for

text: all

text: s

text: t

text: and

text: all

text: y

text: Yt

text: deﬁne

text: the

text: kernel

text: Q

text: y

text: on

text: (X,

text: by

text: s:t

text: s:t

text: Q

text: y

text: (x,

text: A)

text: Q

text: y

text: Q

text: y

text: Q

text: y

text: (x,

text: A)

text: s:t

text: s

text: t

text: In

text: what

text: follows,

text: we

text: set

text: by

text: convention

text: Q

text: y

text: (x,

text: A)

text: for

text: all

text: s

text: t.

text: With

text: these

text: notations,

text: s:t

text: P

text: p

text: (y

text: µQ

text: y

text: where

text: is

text: function,

text: for

text: all

text: x

text: X.

text: For

text: all

text: µ

text: (X)

text: µ

text: and

text: for

text: all

text: s

text: t,

text: denote

text: p

text: (y

text: )/p

text: (y

text: if

text: p

text: (y

text: p

text: (y

text: y

text: µ

text: µ

text: µ

text: µ

text: s:t

text: otherwise

text: with

text: the

text: convention

text: p

text: (y

text: y

text: p

text: (y

text: µ

text: µ

text: A

text: quantity

text: of

text: central

text: interest

text: the

text: JSD,

text: given

text: by

text: t

text: (D)

text: p

text: (y

text: dxs)g(xs,

text: µ

text: X⊗

text: for

text: all

text: D

text: With

text: T

text: being

text: some

text: ﬁnal

text: time

text: point,

text: the

text: PG

text: sampler

text: (reviewed

text: in

text: the

text: subsequent

text: section)

text: deﬁnes

text: a

text: Markov

text: kernel

text: which

text: is

text: reversible

text: with

text: respect

text: to

text: φ

text: y

text: Samples

text: drawn

text: from

text: the

text: PG

text: kernel

text: can

text: thus

text: be

text: used

text: to

text: draw

text: inference

text: about

text: the

text: states

text: (and/or

text: parameters)

text: of

text: the

text: state

text: space

text: model.

text: The

text: particle

text: Gibbs

text: sampler

text: Consider

text: ﬁrst

text: an

text: SMC

text: sampler

text: targeting

text: the

text: sequence

text: of

text: JSDs

text: deﬁned

text: in

text: The

text: SMC

text: sampler

text: approximates

text: φ

text: Y

text: by

text: a

text: collection

text: of

text: weighted

text: samples

text: (Xi

text: ωi)

text: N

text: in

text: the

text: t

text: sense

text: that

text: N

text: ωi

text: φN

text: Y

text: (h)

text: t

text: h(Xi

text: N

text: t

text: R

text: is

text: an

text: estimator

text: of

text: φ

text: Y

text: (h)

text: for

text: a

text: measurable

text: function

text: h

text: These

text: weighted

text: samples

text: can

text: be

text: generated

text: in

text: several

text: diﬀerent

text: ways,

text: see

text: e.g.

text: Doucet

text: et

text: al.

text: Del

text: Moral

text: ##LTLine##

text: ##LTLine##


text: (cid:104) (cid:105) (cid:48) (cid:48) | (cid:104) (cid:105)| Proof. For the bootstrap ﬁlter, w y (x, x ) = g(x , y). Therefore, w y ∞ = sup ∈ g(x, y). On ≥ x X the other hand, for (cid:96) (cid:32)m, (cid:33) (cid:90) (cid:89) − | (cid:104) (cid:105) | ≤ t+m 1 (cid:104) (cid:105) Q Y 1 ∞ σ sup g(x, Y ) γ(dx )g(x , Y )Q Y 1(x ) , t+1:t+(cid:96) + ∈ s t+m t+m t+m t+m+1:l t+m x X s=t+1 (19) and (cid:32) (cid:33) (cid:90) (cid:89) − | ≥ t+m 1 (cid:104) (cid:105) p (Y Y − ) σ− inf g(x, Y ) γ(dx )g(x , Y )Q Y 1(x ) . µ t:t+(cid:96) 0:t 1 ∈ s t+m t+m t+m t+m+1:t+(cid:96) t+m x X s=t (20) Combining (19) and (20) yields ≤ σ B δm + . (21) t,T σ− The result follows as in the proof of Proposition 4. 4.3 Moment assumption Under the strong mixing condition and the even more restrictive , we obtained non- degenerate uniform convergence bounds when the number of trajectories N depends linearly T on the number of observations T. However, these conditions are very restrictive and hardly ever satisﬁed when the state space is non-compact. We now turn to the analysis of the minorization condition under a much weaker moment assumption. However, when the strong mixing assump- tion is relaxed, we are no longer able to obtain bounds that hold uniformly with respect to the observation sequence. Instead, we will take a probabilistic approach. In Theorem 6 below, we show that the minorizing constant will be bounded away from zero, in probability, provided that N is a power of T. Moreover, the result presented in this section is not restricted to the T fully-adapted or the bootstrap PG kernel and may be obtained for virtually any proposal kernel. { ∈ N} This result holds with respect to the law of the observation process Y , t . It is t therefore of interest to carry out the analysis for a parametric family of state space models { ∈ } (Mθ, Gθ), θ Θ , where Θ is a compact subset of a Euclidean space. Informally, this allows us to analyse the ergodicity of the PG kernel, even when the algorithm is executed using a { ∈ N} misspeciﬁed model. We consider a sequence of parameters θ , T that become increasingly T √ close to some “true” parameter θ (in a sense that will be made precise in Theorem 6 below), (cid:63) converging at a rate 1/ T. The rationale for this assumption is that we are considering the large T regime and we can therefore expect θ to be close to θ . We discuss this further in T (cid:63) Remark 7 below. Note that, for a ﬁxed observation sequence Y (with ﬁnite T) we can instead 0:T appeal to Corollary 2. ∈ For all θ Θ, the kernel Mθ has a unique stationary distribution denoted as πθ. ∈ E P In what follows, for θ Θ we let θ and θ refer to the expectation and probability, × N X ⊗ Yµ ⊗N µ { ∈ N} respectively, induced on ((X Y) , ( ) ) by a Markov chain (X , Y ), t evolving t t 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: For

text: the

text: bootstrap

text: ﬁlter,

text: w

text: y

text: (x,

text: x

text: g(x

text: y).

text: Therefore,

text: w

text: y

text: sup

text: g(x,

text: y).

text: On

text: x

text: X

text: the

text: other

text: hand,

text: for

text: t+m

text: Q

text: Y

text: σ

text: sup

text: g(x,

text: Y

text: γ(dx

text: )g(x

text: Y

text: )Q

text: Y

text: s

text: t+m

text: t+m

text: t+m

text: t+m

text: x

text: X

text: and

text: t+m

text: p

text: (Y

text: Y

text: σ−

text: inf

text: g(x,

text: Y

text: γ(dx

text: )g(x

text: Y

text: )Q

text: Y

text: µ

text: s

text: t+m

text: t+m

text: t+m

text: t+m

text: x

text: X

text: s=t

text: Combining

text: and

text: yields

text: σ

text: B

text: δm

text: t,T

text: σ−

text: The

text: result

text: follows

text: as

text: in

text: the

text: proof

text: of

text: Proposition

text: Moment

text: assumption

text: Under

text: the

text: strong

text: mixing

text: condition

text: and

text: the

text: even

text: more

text: restrictive

text: we

text: obtained

text: non-

text: degenerate

text: uniform

text: convergence

text: bounds

text: when

text: the

text: number

text: of

text: trajectories

text: N

text: depends

text: linearly

text: T

text: on

text: the

text: number

text: of

text: observations

text: T.

text: However,

text: these

text: conditions

text: are

text: very

text: restrictive

text: and

text: hardly

text: ever

text: satisﬁed

text: when

text: the

text: state

text: space

text: is

text: non-compact.

text: We

text: now

text: turn

text: to

text: the

text: analysis

text: of

text: the

text: minorization

text: condition

text: under

text: a

text: much

text: weaker

text: moment

text: assumption.

text: However,

text: when

text: the

text: strong

text: mixing

text: assump-

text: tion

text: is

text: relaxed,

text: we

text: are

text: no

text: longer

text: able

text: to

text: obtain

text: bounds

text: that

text: hold

text: uniformly

text: with

text: respect

text: to

text: the

text: observation

text: sequence.

text: Instead,

text: we

text: will

text: take

text: a

text: probabilistic

text: approach.

text: In

text: Theorem

text: below,

text: we

text: show

text: that

text: the

text: minorizing

text: constant

text: will

text: be

text: bounded

text: away

text: from

text: zero,

text: in

text: probability,

text: provided

text: that

text: N

text: is

text: a

text: power

text: of

text: T.

text: Moreover,

text: the

text: result

text: presented

text: in

text: this

text: section

text: is

text: not

text: restricted

text: to

text: the

text: T

text: fully-adapted

text: or

text: the

text: bootstrap

text: PG

text: kernel

text: and

text: may

text: be

text: obtained

text: for

text: virtually

text: any

text: proposal

text: kernel.

text: N}

text: This

text: result

text: holds

text: with

text: respect

text: to

text: the

text: law

text: of

text: the

text: observation

text: process

text: Y

text: t

text: It

text: is

text: t

text: therefore

text: of

text: interest

text: to

text: carry

text: out

text: the

text: analysis

text: for

text: a

text: parametric

text: family

text: of

text: state

text: space

text: models

text: (Mθ,

text: Gθ),

text: θ

text: Θ

text: where

text: Θ

text: is

text: a

text: compact

text: subset

text: of

text: a

text: Euclidean

text: space.

text: Informally,

text: this

text: allows

text: us

text: to

text: analyse

text: the

text: ergodicity

text: of

text: the

text: PG

text: kernel,

text: even

text: when

text: the

text: algorithm

text: is

text: executed

text: using

text: a

text: N}

text: misspeciﬁed

text: model.

text: We

text: consider

text: a

text: sequence

text: of

text: parameters

text: θ

text: T

text: that

text: become

text: increasingly

text: T

text: close

text: to

text: some

text: “true”

text: parameter

text: θ

text: (in

text: a

text: sense

text: that

text: will

text: be

text: made

text: precise

text: in

text: Theorem

text: below),

text: converging

text: at

text: a

text: rate

text: T.

text: The

text: rationale

text: for

text: this

text: assumption

text: is

text: that

text: we

text: are

text: considering

text: the

text: large

text: T

text: regime

text: and

text: we

text: can

text: therefore

text: expect

text: θ

text: to

text: be

text: close

text: to

text: θ

text: We

text: discuss

text: this

text: further

text: in

text: T

text: Remark

text: below.

text: Note

text: that,

text: for

text: a

text: ﬁxed

text: observation

text: sequence

text: Y

text: (with

text: ﬁnite

text: T)

text: we

text: can

text: instead

text: appeal

text: to

text: Corollary

text: For

text: all

text: θ

text: Θ,

text: the

text: kernel

text: Mθ

text: has

text: a

text: unique

text: stationary

text: distribution

text: denoted

text: as

text: πθ.

text: E

text: P

text: In

text: what

text: follows,

text: for

text: θ

text: Θ

text: we

text: let

text: θ

text: and

text: θ

text: refer

text: to

text: the

text: expectation

text: and

text: probability,

text: N

text: X

text: Yµ

text: ⊗N

text: µ

text: N}

text: respectively,

text: induced

text: on

text: ((X

text: Y)

text: by

text: a

text: Markov

text: chain

text: (X

text: Y

text: t

text: evolving

text: t

text: t

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Two-Page Book Embeddings of 4-Planar Graphs∗ † ‡ § Michael A. Bekos 1, Martin Gronemann 2, and Chrysanthi N. Raftopoulou 3 1Wilhelm-Schickhard-Institut fu¨r Informatik, Universit¨at Tu¨bingen, Germany 2Institut fu¨r Informatik, Universit¨at zu K¨oln, Germany 3School of Applied Mathematical & Physical Sciences, NTUA, Greece. Abstract Back in the eighties, Heath [6] showed that every 3-planar graph is subhamiltonian and asked whether this result can be extended to a class of graphs of degree greater than three. In this paper we aﬃrmatively answer this question for the class of 4-planar graphs. Our contribution consists of two algorithms: The ﬁrst one is limited to triconnected graphs, but runs in linear time and uses existing methods for computing hamiltonian cycles in planar graphs. The second one, which solves the general case of the problem, is a quadratic-time algorithm based on the book embedding viewpoint of the problem. 1 Introduction Book embeddings have a long history and arise in various application areas such as VLSI design, parallel computing, design of fault-tolerant systems [4]. In a book embedding the placement of nodes is restricted to a line, the spine of the book. The edges are assigned to diﬀerent pages of the book. A page can be thought of as a half-plane bounded by the spine where the edges are drawn as circular arcs between their endpoints. We say that a graph admits a k-page book embedding or is k-page embeddable if one can assign the edges to k pages and there exists a linear ordering of the nodes on the spine such that no two edges of the same page cross. The minimum number of pages required to construct such an embedding is the book thickness or page number of a graph. The book thickness of planar graphs has received much attention in the past. Yannakakis [13] describes a linear-time algorithm to embed every planar graph into a book of four pages. We study the problem of embedding 4-planar graphs, i.e., planar graphs with maximum degree four, into books with two pages. Bernhart et al. [1] show that a graph is two-page embeddable iﬀ it is subhamiltonian. A subhamiltonian graph is a subgraph of a planar hamiltonian graph. It is NP-complete to determine whether a graph is subhamiltonian [12]. Often referred to as augmented hamiltonian cycle, a subhamiltonian cycle is a cyclic sequence of nodes in a graph that would form a hamiltonian cycle when adding the missing edges without destroying planarity. The relation between subhamiltonian cycles and two-page book embeddings is quite intuitive. The order of the nodes on the spine is equivalent to the cyclic order of the subhamiltonian cycle. The edges are partitioned by whether they lie in the interior of the cycle or not. ∗Work on this problem began at Dagstuhl Seminar 13151. We thank the organizers, participants and Prof. Dr. M. Kaufmann. †Electronic address: bekos@informatik.uni-tuebingen.de ‡Electronic address: gronemann@informatik.uni-koeln.de §Electronic address: crisraft@mail.ntua.gr 1 ##LTLine##

text: Two-Page

label: title

text: Book

text: Embeddings

text: of

text: Graphs∗

label: author

text: Michael

text: A.

text: Bekos

text: Martin

text: Gronemann

text: and

text: Chrysanthi

text: N.

text: Raftopoulou

text: fu¨r

text: Informatik,

text: Universit¨at

text: Tu¨bingen,

text: Germany

text: fu¨r

text: Informatik,

text: Universit¨at

text: zu

text: K¨oln,

text: Germany

text: of

text: Applied

text: Mathematical

text: Physical

text: Sciences,

text: NTUA,

text: Greece.

text: Abstract

text: Back

label: abstract

text: in

text: the

text: eighties,

text: Heath

text: showed

text: that

text: every

text: graph

text: is

text: subhamiltonian

text: and

text: asked

text: whether

text: this

text: result

text: can

text: be

text: extended

text: to

text: a

text: class

text: of

text: graphs

text: of

text: degree

text: greater

text: than

text: three.

text: In

text: this

text: paper

text: we

text: aﬃrmatively

text: answer

text: this

text: question

text: for

text: the

text: class

text: of

text: graphs.

text: Our

text: contribution

text: consists

text: of

text: two

text: algorithms:

text: The

text: ﬁrst

text: one

text: is

text: limited

text: to

text: triconnected

text: graphs,

text: but

text: runs

text: in

text: linear

text: time

text: and

text: uses

text: existing

text: methods

text: for

text: computing

text: hamiltonian

text: cycles

text: in

text: planar

text: graphs.

text: The

text: second

text: one,

text: which

text: solves

text: the

text: general

text: case

text: of

text: the

text: problem,

text: is

text: a

text: quadratic-time

text: algorithm

text: based

text: on

text: the

text: book

text: embedding

text: viewpoint

text: of

text: the

text: problem.

text: Introduction

text: Book

text: embeddings

text: have

text: a

text: long

text: history

text: and

text: arise

text: in

text: various

text: application

text: areas

text: such

text: as

text: VLSI

text: design,

text: parallel

text: computing,

text: design

text: of

text: fault-tolerant

text: systems

text: In

text: a

text: book

text: embedding

text: the

text: placement

text: of

text: nodes

text: is

text: restricted

text: to

text: a

text: line,

text: the

text: spine

text: of

text: the

text: book.

text: The

text: edges

text: are

text: assigned

text: to

text: diﬀerent

text: pages

text: of

text: the

text: book.

text: A

text: page

text: can

text: be

text: thought

text: of

text: as

text: a

text: half-plane

text: bounded

text: by

text: the

text: spine

text: where

text: the

text: edges

text: are

text: drawn

text: as

text: circular

text: arcs

text: between

text: their

text: endpoints.

text: We

text: say

text: that

text: a

text: graph

text: admits

text: a

text: k-page

text: book

text: embedding

text: or

text: is

text: k-page

text: embeddable

text: if

text: one

text: can

text: assign

text: the

text: edges

text: to

text: k

text: pages

text: and

text: there

text: exists

text: a

text: linear

text: ordering

text: of

text: the

text: nodes

text: on

text: the

text: spine

text: such

text: that

text: no

text: two

text: edges

text: of

text: the

text: same

text: page

text: cross.

text: The

text: minimum

text: number

text: of

text: pages

text: required

text: to

text: construct

text: such

text: an

text: embedding

text: is

text: the

text: book

text: thickness

text: or

text: page

text: number

text: of

text: a

text: graph.

text: The

text: book

text: thickness

text: of

text: planar

text: graphs

text: has

text: received

text: much

text: attention

text: in

text: the

text: past.

text: Yannakakis

text: describes

text: a

text: linear-time

text: algorithm

text: to

text: embed

text: every

text: planar

text: graph

text: into

text: a

text: book

text: of

text: four

text: pages.

text: We

text: study

text: the

text: problem

text: of

text: embedding

text: graphs,

text: i.e.,

text: planar

text: graphs

text: with

text: maximum

text: degree

text: four,

text: into

text: books

text: with

text: two

text: pages.

text: Bernhart

text: et

text: al.

text: show

text: that

text: a

text: graph

text: is

text: two-page

text: embeddable

text: iﬀ

text: it

text: is

text: subhamiltonian.

text: A

text: subhamiltonian

text: graph

text: is

text: a

text: subgraph

text: of

text: a

text: planar

text: hamiltonian

text: graph.

text: It

text: is

text: NP-complete

text: to

text: determine

text: whether

text: a

text: graph

text: is

text: subhamiltonian

text: Often

text: referred

text: to

text: as

text: augmented

text: hamiltonian

text: cycle,

text: a

text: subhamiltonian

text: cycle

text: is

text: a

text: cyclic

text: sequence

text: of

text: nodes

text: in

text: a

text: graph

text: that

text: would

text: form

text: a

text: hamiltonian

text: cycle

text: when

text: adding

text: the

text: missing

text: edges

text: without

text: destroying

text: planarity.

text: The

text: relation

text: between

text: subhamiltonian

text: cycles

text: and

text: two-page

text: book

text: embeddings

text: is

text: quite

text: intuitive.

text: The

text: order

text: of

text: the

text: nodes

text: on

text: the

text: spine

text: is

text: equivalent

text: to

text: the

text: cyclic

text: order

text: of

text: the

text: subhamiltonian

text: cycle.

text: The

text: edges

text: are

text: partitioned

text: by

text: whether

text: they

text: lie

text: in

text: the

text: interior

text: of

text: the

text: cycle

text: or

text: not.

text: ∗Work

text: on

text: this

text: problem

text: began

text: at

text: Dagstuhl

text: Seminar

text: We

text: thank

text: the

text: organizers,

text: participants

text: and

text: Prof.

text: Dr.

text: M.

text: Kaufmann.

text: †Electronic

text: address:

text: bekos@informatik.uni-tuebingen.de

text: ‡Electronic

text: address:

text: gronemann@informatik.uni-koeln.de

text: §Electronic

text: address:

text: crisraft@mail.ntua.gr

text: ##LTLine##


text: First assume that c is an anchor, i.e., w is incident to a marked edge. We place the vertices 0 of F on (cid:96) as follows: (i) w occupies the position of c and it is the rightmost vertex of F on (cid:96), c 0 c (ii) w is the leftmost vertex of F on (cid:96), (iii) w is to the left of w for i = 1, . . . , m − 1, and, 1 c i i+1 (iv) there are no vertices in between; see Fig. 13b. All edges of F are top-drawn, except for c (w , w ). This placement is always feasible, except for the case in which in the combinatorial 1 0 embedding speciﬁed by IP-2 there is an edge incident to w that is between (w , w ) and the 0 0 1 marked edge incident to w in the counterclockwise order of the edges around w when starting 0 0 from (w , w ); see Fig. 13c. In this case, we place w to the left of w , . . . , w , s.t. w is the 0 1 0 1 m 0 leftmost vertex of F . So, (w , w ) is the bottom-drawn edge of F . c 0 m c Suppose now that c is an ancillary. Let w be the closest neighbor of c to its left on (cid:96). Then, w is the parent of c in the tree in which c belongs to and (w , w) is top-drawn. We place the 0 vertices of F as follows: (i) w occupies the position of c and it is the leftmost vertex of F on c 0 c (cid:96), (ii) w is the rightmost vertex of F on (cid:96), (iii) w is to the left of w , i = 1, . . . , m − 1, and, m c i i+1 (iv) there are no vertices in between. All edges of F are top-drawn, except for (w , w ). This c 0 m placement is infeasible only when in the combinatorial embedding speciﬁed by IP-2 there is an (cid:48) edge incident to w , say (w , w ), and between (w , w ) and (w , w) in the clockwise order of 0 0 0 m 0 (cid:48) the edges around w when starting from (w , w ) (see Fig. 13d). In this case, (w , w ) cannot 0 0 m 0 be drawn on the top-page, as required for edges incident to ancillaries. More precisely, since c has only its parent to its left among the block-vertices of the anchored tree it belongs to, it (cid:48) (cid:48) follows that, w is to the right of c. Hence, (w , w ) cannot be drawn on the top-page, without 0 deviating the combinatorial embedding speciﬁed by IP-2. Since G is biconnected, c is adjacent (cid:48)(cid:48) (cid:48)(cid:48) (cid:48) to at least another block-vertex, say w , s.t. w ∈/ {w, w }. The following lemma takes care of this case. Lemma 14. Ancillary c can be repositioned on (cid:96), s.t.: (i) c is placed between two consecutive anchors of T . (ii) The combinatorial embedding speciﬁed by IP-2 is preserved and the edges (cid:48) (cid:48)(cid:48) (w , w), (w , w ) and (c, w ) are top-drawn and crossing-free. (iii) w is leftmost vertex of F 0 0 0 c and w is to the left of w , i = 1, . . . , m−1; All edges of F are top-drawn, except for (w , w ). i i+1 c 0 m (cid:48) (cid:48)(cid:48) (cid:48) Proof. w is the parent of c and w , w are children of c in T , with w being the ﬁrst child of c. (cid:48)(cid:48) (cid:48) (cid:48)(cid:48) For our proof, w is its second child. So, (c, w), (c, w ) and (c, w ) are consecutive around c as (cid:48) (cid:48)(cid:48) (cid:48) (cid:48)(cid:48) in Fig. 13d. Let T (w ) and T (w ) be subtrees of T rooted at w and w , resp. Initially, c is to (cid:48) (cid:48) (cid:48)(cid:48) the left of all vertices of T (w ), all vertices of T (w ) are to the left of all vertices of T (w ) and there are no ancillaries of T in between. We place c between the rightmost (leftmost) anchor (cid:48) (cid:48)(cid:48) of T (w ) (T (w )); see Fig. 13e. So, c is placed between two consecutive anchors of T . If we place the vertices of F , with w being leftmost on F and w to the left of w , then (w , w), (cid:48) (cid:48)(cid:48) c 0 c i i+1 0 (w , w ) and (c, w ) are drawn on the top-page and the embedding is preserved. 0 If we process all ancillaries that have to be repositioned from right to left along (cid:96), then by Lemma 14 we obtain a planar drawing in which the embedding speciﬁed by IP-2 is preserved once the outerface of each block-vertex is drawn and all edges that connect block-vertices are eventually drawn on the top-page. w 0 Initially, we assumed that F is simple. If not so, F consists of c c smaller simple subcycles, s.t. (i) any two subcycles share at most root one vertex of F and (ii) any vertex of F is incident to at most c c two subcycles. Hence, the “tangency graph” of these subcycles (which has a vertex for each subcycle and an edge between every pair of subcycles that share a vertex) is a tree. Deﬁne w0 as in Figure 14: Fc is not simple the case of simple cycle and let the tangency tree be rooted at the cycle containing w . Due to degree restriction, w cannot be incident to two subcycles. We 0 0 draw the subcycles of F in the order implied by the Breadth First Search (BFS) traversal of c the tangency tree. The ﬁrst one (incident to w ) is drawn as in the case of simple cycle. Each 0 next subcycle is plugged into the drawing, as shown in Fig. 14. 15 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: First

text: assume

text: that

text: c

text: is

text: an

text: anchor,

text: i.e.,

text: w

text: is

text: incident

text: to

text: a

text: marked

text: edge.

text: We

text: place

text: the

text: vertices

text: of

text: F

text: on

text: as

text: follows:

text: (i)

text: w

text: occupies

text: the

text: position

text: of

text: c

text: and

text: it

text: is

text: the

text: rightmost

text: vertex

text: of

text: F

text: on

text: c

text: c

text: (ii)

text: w

text: is

text: the

text: leftmost

text: vertex

text: of

text: F

text: on

text: (iii)

text: w

text: is

text: to

text: the

text: left

text: of

text: w

text: for

text: i

text: m

text: and,

text: c

text: i

text: (iv)

text: there

text: are

text: no

text: vertices

text: in

text: between;

text: see

text: Fig.

text: All

text: edges

text: of

text: F

text: are

text: top-drawn,

text: except

text: for

text: c

text: (w

text: w

text: This

text: placement

text: is

text: always

text: feasible,

text: except

text: for

text: the

text: case

text: in

text: which

text: in

text: the

text: combinatorial

text: embedding

text: speciﬁed

text: by

text: there

text: is

text: an

text: edge

text: incident

text: to

text: w

text: that

text: is

text: between

text: (w

text: w

text: and

text: the

text: marked

text: edge

text: incident

text: to

text: w

text: in

text: the

text: counterclockwise

text: order

text: of

text: the

text: edges

text: around

text: w

text: when

text: starting

text: from

text: (w

text: w

text: see

text: Fig.

text: In

text: this

text: case,

text: we

text: place

text: w

text: to

text: the

text: left

text: of

text: w

text: w

text: s.t.

text: w

text: is

text: the

text: m

text: leftmost

text: vertex

text: of

text: F

text: So,

text: (w

text: w

text: is

text: the

text: bottom-drawn

text: edge

text: of

text: F

text: c

text: m

text: c

text: Suppose

text: now

text: that

text: c

text: is

text: an

text: ancillary.

text: Let

text: w

text: be

text: the

text: closest

text: neighbor

text: of

text: c

text: to

text: its

text: left

text: on

text: Then,

text: w

text: is

text: the

text: parent

text: of

text: c

text: in

text: the

text: tree

text: in

text: which

text: c

text: belongs

text: to

text: and

text: (w

text: w)

text: is

text: top-drawn.

text: We

text: place

text: the

text: vertices

text: of

text: F

text: as

text: follows:

text: (i)

text: w

text: occupies

text: the

text: position

text: of

text: c

text: and

text: it

text: is

text: the

text: leftmost

text: vertex

text: of

text: F

text: on

text: c

text: c

text: (ii)

text: w

text: is

text: the

text: rightmost

text: vertex

text: of

text: F

text: on

text: (iii)

text: w

text: is

text: to

text: the

text: left

text: of

text: w

text: i

text: m

text: and,

text: m

text: c

text: i

text: (iv)

text: there

text: are

text: no

text: vertices

text: in

text: between.

text: All

text: edges

text: of

text: F

text: are

text: top-drawn,

text: except

text: for

text: (w

text: w

text: This

text: c

text: m

text: placement

text: is

text: infeasible

text: only

text: when

text: in

text: the

text: combinatorial

text: embedding

text: speciﬁed

text: by

text: there

text: is

text: an

text: edge

text: incident

text: to

text: w

text: say

text: (w

text: w

text: and

text: between

text: (w

text: w

text: and

text: (w

text: w)

text: in

text: the

text: clockwise

text: order

text: of

text: m

text: the

text: edges

text: around

text: w

text: when

text: starting

text: from

text: (w

text: w

text: (see

text: Fig.

text: In

text: this

text: case,

text: (w

text: w

text: cannot

text: m

text: be

text: drawn

text: on

text: the

text: top-page,

text: as

text: required

text: for

text: edges

text: incident

text: to

text: ancillaries.

text: More

text: precisely,

text: since

text: c

text: has

text: only

text: its

text: parent

text: to

text: its

text: left

text: among

text: the

text: block-vertices

text: of

text: the

text: anchored

text: tree

text: it

text: belongs

text: to,

text: it

text: follows

text: that,

text: w

text: is

text: to

text: the

text: right

text: of

text: c.

text: Hence,

text: (w

text: w

text: cannot

text: be

text: drawn

text: on

text: the

text: top-page,

text: without

text: deviating

text: the

text: combinatorial

text: embedding

text: speciﬁed

text: by

text: Since

text: G

text: is

text: biconnected,

text: c

text: is

text: adjacent

text: to

text: at

text: least

text: another

text: block-vertex,

text: say

text: w

text: s.t.

text: w

text: {w,

text: w

text: The

text: following

text: lemma

text: takes

text: care

text: of

text: this

text: case.

text: Lemma

text: Ancillary

text: c

text: can

text: be

text: repositioned

text: on

text: s.t.:

text: (i)

text: c

text: is

text: placed

text: between

text: two

text: consecutive

text: anchors

text: of

text: T

text: (ii)

text: The

text: combinatorial

text: embedding

text: speciﬁed

text: by

text: is

text: preserved

text: and

text: the

text: edges

text: (w

text: w),

text: (w

text: w

text: and

text: (c,

text: w

text: are

text: top-drawn

text: and

text: crossing-free.

text: (iii)

text: w

text: is

text: leftmost

text: vertex

text: of

text: F

text: c

text: and

text: w

text: is

text: to

text: the

text: left

text: of

text: w

text: i

text: All

text: edges

text: of

text: F

text: are

text: top-drawn,

text: except

text: for

text: (w

text: w

text: i

text: c

text: m

text: Proof.

text: w

text: is

text: the

text: parent

text: of

text: c

text: and

text: w

text: w

text: are

text: children

text: of

text: c

text: in

text: T

text: with

text: w

text: being

text: the

text: ﬁrst

text: child

text: of

text: c.

text: For

text: our

text: proof,

text: w

text: is

text: its

text: second

text: child.

text: So,

text: (c,

text: w),

text: (c,

text: w

text: and

text: (c,

text: w

text: are

text: consecutive

text: around

text: c

text: as

text: in

text: Fig.

text: Let

text: T

text: (w

text: and

text: T

text: (w

text: be

text: subtrees

text: of

text: T

text: rooted

text: at

text: w

text: and

text: w

text: resp.

text: Initially,

text: c

text: is

text: to

text: the

text: left

text: of

text: all

text: vertices

text: of

text: T

text: (w

text: all

text: vertices

text: of

text: T

text: (w

text: are

text: to

text: the

text: left

text: of

text: all

text: vertices

text: of

text: T

text: (w

text: and

text: there

text: are

text: no

text: ancillaries

text: of

text: T

text: in

text: between.

text: We

text: place

text: c

text: between

text: the

text: rightmost

text: (leftmost)

text: anchor

text: of

text: T

text: (w

text: (T

text: (w

text: see

text: Fig.

text: So,

text: c

text: is

text: placed

text: between

text: two

text: consecutive

text: anchors

text: of

text: T

text: If

text: we

text: place

text: the

text: vertices

text: of

text: F

text: with

text: w

text: being

text: leftmost

text: on

text: F

text: and

text: w

text: to

text: the

text: left

text: of

text: w

text: then

text: (w

text: w),

text: c

text: c

text: i

text: (w

text: w

text: and

text: (c,

text: w

text: are

text: drawn

text: on

text: the

text: top-page

text: and

text: the

text: embedding

text: is

text: preserved.

text: If

text: we

text: process

text: all

text: ancillaries

text: that

text: have

text: to

text: be

text: repositioned

text: from

text: right

text: to

text: left

text: along

text: then

text: by

text: Lemma

text: we

text: obtain

text: a

text: planar

text: drawing

text: in

text: which

text: the

text: embedding

text: speciﬁed

text: by

text: is

text: preserved

text: once

text: the

text: outerface

text: of

text: each

text: block-vertex

text: is

text: drawn

text: and

text: all

text: edges

text: that

text: connect

text: block-vertices

text: are

text: eventually

text: drawn

text: on

text: the

text: top-page.

text: w

text: Initially,

text: we

text: assumed

text: that

text: F

text: is

text: simple.

text: If

text: not

text: so,

text: F

text: consists

text: of

text: c

text: c

text: smaller

text: simple

text: subcycles,

text: s.t.

text: (i)

text: any

text: two

text: subcycles

text: share

text: at

text: most

text: root

text: one

text: vertex

text: of

text: F

text: and

text: (ii)

text: any

text: vertex

text: of

text: F

text: is

text: incident

text: to

text: at

text: most

text: c

text: c

text: two

text: subcycles.

text: Hence,

text: the

text: “tangency

text: graph”

text: of

text: these

text: subcycles

text: (which

text: has

text: a

text: vertex

text: for

text: each

text: subcycle

text: and

text: an

text: edge

text: between

text: every

text: pair

text: of

text: subcycles

text: that

text: share

text: a

text: vertex)

text: is

text: a

text: tree.

text: Deﬁne

text: as

text: in

text: Figure

text: Fc

text: is

text: not

text: simple

text: the

text: case

text: of

text: simple

text: cycle

text: and

text: let

text: the

text: tangency

text: tree

text: be

text: rooted

text: at

text: the

text: cycle

text: containing

text: w

text: Due

text: to

text: degree

text: restriction,

text: w

text: cannot

text: be

text: incident

text: to

text: two

text: subcycles.

text: We

text: draw

text: the

text: subcycles

text: of

text: F

text: in

text: the

text: order

text: implied

text: by

text: the

text: Breadth

text: First

text: Search

text: (BFS)

text: traversal

text: of

text: c

text: the

text: tangency

text: tree.

text: The

text: ﬁrst

text: one

text: (incident

text: to

text: w

text: is

text: drawn

text: as

text: in

text: the

text: case

text: of

text: simple

text: cycle.

text: Each

text: next

text: subcycle

text: is

text: plugged

text: into

text: the

text: drawing,

text: as

text: shown

text: in

text: Fig.

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: The general idea of our algorithm is as follows: First remove from G cycle C delimiting out the outerface of G and contract each bridge-block1 of the remaining graph into a single vertex. Let F be the implied graph, which is a forest in general, since G − C is not necessarily out connected. Cycle C is embedded, s.t.: (i) the order of the vertices of C along the spine is out out ﬁxed (and follows the one in which the vertices of C appear along C ), and, (ii) all edges out out of C are on the same page, except for the one that connects its outermost vertices. Then, out we describe how to embed without crossings: (i) the chords of C , (ii) forest F , and, (iii) the out edges between C and F . To obtain a two-page book embedding of G, we replace each vertex out of F with a cycle (embedded similarly to C ), whose length equals to the length of the cycle out delimiting the outerface of the bridge-block it corresponds to in G−C , and recursively embed out its interior. More formally, consider an arbitrary simple cycle C : v → v → . . . → v → v of G. The 1 2 k 1 removal of C results in two planar subgraphs G (C) and G (C) of G that are the components in out of G−C that lie in the interior and exterior of C in G, resp. Note that G (C) and G (C) are in out not necessarily connected. Let G (C) (G (C), resp.) be the subgraph of G induced by C and in out G (C) (G (C), resp.). For the recursive step, we assume the following invariant properties: in out IP-1: The order of the vertices of G (C) along the spine (cid:96) is ﬁxed and the page in which each out edge of G (C) is drawn (i.e., top or bottom) is determined s.t. the book embedding of out G (C) is planar. In other words, we assume that we have already produced a two-page out book embedding for G (C), in which no edge crosses the spine. out IP-2: The combinatorial embedding of G (C) is consistent with a given planar combinatorial out embedding of G. IP-3: The vertices of C occupy consecutive positions along (cid:96), s.t. v (v , resp.) is the leftmost 1 k (rightmost, resp.) along (cid:96). Moreover, all edges of C are on the same page, except for the one that connects v and v . Say w.l.o.g. that (v , v ) is on the top-page (or top- 1 k 1 k drawn), while the remaining edges of C, namely edges (v , v ) for 1 ≤ i < k, are on the i i+1 bottom-page (or bottom-drawn); see Fig.9. IP-4: If C is not identiﬁed with the cycle delimiting the outerface of G, the degree of either v 1 or v is at most 3 in G (C). Say w.l.o.g. that v is of degree at most 3. k in k IP-5: If vertex v has degree 4 in G (C), then it is adjacent to zero or two chords of C. 1 in v v v v 1 2 k−1 k ‘ Figure 9: Illustration of invariant property IP-3. We explicitly notice that the combinatorial embedding speciﬁed in IP-2 is maintained throughout the whole drawing process. This combined with the fact that every edge entirely lies on one page (i.e., no edge crosses the spine; see IP-1) is suﬃcient to ensure planarity. In the following, we describe in detail how to recursively produce a two-page book embedding of G (C). Note that we ﬁrst present the recursive step of our algorithm and then its base, since in this approach shows better how the diﬀerent ideas ﬂow one after the other. Let v be a vertex i 1The bridge-blocks of a connected graph G are the connected components formed by deleting all bridges of G. The bridge-blocks and the bridges of G have a natural tree structure, called bridge-block tree. 8 ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: The

text: general

text: idea

text: of

text: our

text: algorithm

text: is

text: as

text: follows:

text: First

text: remove

text: from

text: G

text: cycle

text: C

text: delimiting

text: out

text: the

text: outerface

text: of

text: G

text: and

text: contract

text: each

text: of

text: the

text: remaining

text: graph

text: into

text: a

text: single

text: vertex.

text: Let

text: F

text: be

text: the

text: implied

text: graph,

text: which

text: is

text: a

text: forest

text: in

text: general,

text: since

text: G

text: C

text: is

text: not

text: necessarily

text: out

text: connected.

text: Cycle

text: C

text: is

text: embedded,

text: s.t.:

text: (i)

text: the

text: order

text: of

text: the

text: vertices

text: of

text: C

text: along

text: the

text: spine

text: is

text: out

text: out

text: ﬁxed

text: (and

text: follows

text: the

text: one

text: in

text: which

text: the

text: vertices

text: of

text: C

text: appear

text: along

text: C

text: and,

text: (ii)

text: all

text: edges

text: out

text: out

text: of

text: C

text: are

text: on

text: the

text: same

text: page,

text: except

text: for

text: the

text: one

text: that

text: connects

text: its

text: outermost

text: vertices.

text: Then,

text: out

text: we

text: describe

text: how

text: to

text: embed

text: without

text: crossings:

text: (i)

text: the

text: chords

text: of

text: C

text: (ii)

text: forest

text: F

text: and,

text: (iii)

text: the

text: out

text: edges

text: between

text: C

text: and

text: F

text: To

text: obtain

text: a

text: two-page

text: book

text: embedding

text: of

text: G,

text: we

text: replace

text: each

text: vertex

text: out

text: of

text: F

text: with

text: a

text: cycle

text: (embedded

text: similarly

text: to

text: C

text: whose

text: length

text: equals

text: to

text: the

text: length

text: of

text: the

text: cycle

text: out

text: delimiting

text: the

text: outerface

text: of

text: the

text: bridge-block

text: it

text: corresponds

text: to

text: in

text: G−C

text: and

text: recursively

text: embed

text: out

text: its

text: interior.

text: More

text: formally,

text: consider

text: an

text: arbitrary

text: simple

text: cycle

text: C

text: v

text: v

text: v

text: v

text: of

text: G.

text: The

text: k

text: removal

text: of

text: C

text: results

text: in

text: two

text: planar

text: subgraphs

text: G

text: (C)

text: and

text: G

text: (C)

text: of

text: G

text: that

text: are

text: the

text: components

text: in

text: out

text: of

text: G−C

text: that

text: lie

text: in

text: the

text: interior

text: and

text: exterior

text: of

text: C

text: in

text: G,

text: resp.

text: Note

text: that

text: G

text: (C)

text: and

text: G

text: (C)

text: are

text: in

text: out

text: not

text: necessarily

text: connected.

text: Let

text: G

text: (C)

text: (G

text: (C),

text: resp.)

text: be

text: the

text: subgraph

text: of

text: G

text: induced

text: by

text: C

text: and

text: in

text: out

text: G

text: (C)

text: (G

text: (C),

text: resp.).

text: For

text: the

text: recursive

text: step,

text: we

text: assume

text: the

text: following

text: invariant

text: properties:

text: in

text: out

text: The

text: order

text: of

text: the

text: vertices

text: of

text: G

text: (C)

text: along

text: the

text: spine

text: is

text: ﬁxed

text: and

text: the

text: page

text: in

text: which

text: each

text: out

text: edge

text: of

text: G

text: (C)

text: is

text: drawn

text: (i.e.,

text: top

text: or

text: bottom)

text: is

text: determined

text: s.t.

text: the

text: book

text: embedding

text: of

text: out

text: G

text: (C)

text: is

text: planar.

text: In

text: other

text: words,

text: we

text: assume

text: that

text: we

text: have

text: already

text: produced

text: a

text: two-page

text: out

text: book

text: embedding

text: for

text: G

text: (C),

text: in

text: which

text: no

text: edge

text: crosses

text: the

text: spine.

text: out

text: The

text: combinatorial

text: embedding

text: of

text: G

text: (C)

text: is

text: consistent

text: with

text: a

text: given

text: planar

text: combinatorial

text: out

text: embedding

text: of

text: G.

text: The

text: vertices

text: of

text: C

text: occupy

text: consecutive

text: positions

text: along

text: s.t.

text: v

text: (v

text: resp.)

text: is

text: the

text: leftmost

text: k

text: (rightmost,

text: resp.)

text: along

text: Moreover,

text: all

text: edges

text: of

text: C

text: are

text: on

text: the

text: same

text: page,

text: except

text: for

text: the

text: one

text: that

text: connects

text: v

text: and

text: v

text: Say

text: w.l.o.g.

text: that

text: (v

text: v

text: is

text: on

text: the

text: top-page

text: (or

text: top-

text: k

text: k

text: drawn),

text: while

text: the

text: remaining

text: edges

text: of

text: C,

text: namely

text: edges

text: (v

text: v

text: for

text: i

text: k,

text: are

text: on

text: the

text: i

text: bottom-page

text: (or

text: bottom-drawn);

text: see

text: If

text: C

text: is

text: not

text: identiﬁed

text: with

text: the

text: cycle

text: delimiting

text: the

text: outerface

text: of

text: G,

text: the

text: degree

text: of

text: either

text: v

text: or

text: v

text: is

text: at

text: most

text: in

text: G

text: (C).

text: Say

text: w.l.o.g.

text: that

text: v

text: is

text: of

text: degree

text: at

text: most

text: k

text: in

text: k

text: If

text: vertex

text: v

text: has

text: degree

text: in

text: G

text: (C),

text: then

text: it

text: is

text: adjacent

text: to

text: zero

text: or

text: two

text: chords

text: of

text: C.

text: in

text: v

text: v

text: v

text: v

text: k

text: Figure

text: Illustration

text: of

text: invariant

text: property

text: We

text: explicitly

text: notice

text: that

text: the

text: combinatorial

text: embedding

text: speciﬁed

text: in

text: is

text: maintained

text: throughout

text: the

text: whole

text: drawing

text: process.

text: This

text: combined

text: with

text: the

text: fact

text: that

text: every

text: edge

text: entirely

text: lies

text: on

text: one

text: page

text: (i.e.,

text: no

text: edge

text: crosses

text: the

text: spine;

text: see

text: is

text: suﬃcient

text: to

text: ensure

text: planarity.

text: In

text: the

text: following,

text: we

text: describe

text: in

text: detail

text: how

text: to

text: recursively

text: produce

text: a

text: two-page

text: book

text: embedding

text: of

text: G

text: (C).

text: Note

text: that

text: we

text: ﬁrst

text: present

text: the

text: recursive

text: step

text: of

text: our

text: algorithm

text: and

text: then

text: its

text: base,

text: since

text: in

text: this

text: approach

text: shows

text: better

text: how

text: the

text: diﬀerent

text: ideas

text: ﬂow

text: one

text: after

text: the

text: other.

text: Let

text: v

text: be

text: a

text: vertex

text: i

text: bridge-blocks

text: of

text: a

text: connected

text: graph

text: G

text: are

text: the

text: connected

text: components

text: formed

text: by

text: deleting

text: all

text: bridges

text: of

text: G.

text: The

text: bridge-blocks

text: and

text: the

text: bridges

text: of

text: G

text: have

text: a

text: natural

text: tree

text: structure,

text: called

text: bridge-block

text: tree.

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: 2 tential (cid:15) = 1/(2m a2), where m = m m /(m + m ) The self-energies (1) and (2) determine the dressed 0 r r B F B F − is the reduced mass determined by the boson and fermion Green’s functions G via the Dyson’s equation G 1 = − − s s masses m and m , and we have set ¯h = 1. The repul- G0 1 Σ . The dressed Green’s functions G , in turn, B F s s s sive potential between bosons, which is necessary for allow one to calculate the boson and fermion momentum the stability of the system in the resonance region, can distribution functions n (k) through the equations: s (cid:88) be dropped out from our consideration in the molecular limit of interest to the present paper. A natural length scale of our system, where fermions n (k) = −T(cid:88) G (k, ω ) eiων0+ (4) are the majority species, is provided by the inverse of B B ν ≡ the Fermi wave-vector k (6π2n )1/3 (n being the ν fermion number density).FOne may Fus−e thenFthe dimen- nF(k) = T GF(k, ωn) eiωn0+ , (5) sionless coupling parameter g = (k a) 1 to describe the n F strength of the interaction. In terms of this parameter, (cid:29) the molecular limit corresponds to the condition g 1, from which the boson and fermion number densities such that the radius of the bound state (which coin- are obtained by integrating over momenta. cides with the scattering length a, for a positive) is much − ∝ − smaller than the average interparticle distance ( k 1). The full numerical solution of Eqs. (1) (5) was tackled F in our previous works [? ? ]. Here we are interested in [Note that in some of our previous works [? ? ? ] we deriving analytic expressions in the molecular limit of the used a diﬀerent deﬁnition of k (in terms of the total den- F interaction g. In this limit the binding energy (cid:15) is the sity n = n + n , n being the boson number density), (cid:29) ≡ 0 F B B largest energy scale: (cid:15) T, E , with E k2/(2m ). which coincides with the present one only for nF = nB.] 0 F ≤F F F In addition, for the mixtures with n n of interest The thermodynamic and spectral properties of a Bose- B F to the present paper, the bosonic chemical potential µ Fermi mixture in the normal phase (i.e. above the con- − B approaches (cid:15) in the molecular limit, and is thus large densation critical temperature) were studied in our pre- 0 and negative, while the fermion chemical potential re- vious works [? ? ? ] by using a T-matrix approximation mains of the order of the Fermi energy, and is then small for the self-energies. The corresponding equations for compared to the binding energy. This hierarchy between the bosonic and fermionic self-energies Σ and Σ at ﬁ- B F diﬀerent energy scales will allow us to derive the asymp- nite temperature read (setting the Boltzmann constant kB = 1): (cid:90) (cid:88) totic expressions in the molecular limit. B. The pair propagator − dP ΣB(k, ων) = (cid:90) (2π)3 T Γ(P, Ωm) We focus ﬁrst on the pair propagator Γ(P, Ωm). In (cid:88)m order to perform the frequency sum in Eqs. (1) and (2) × − − G0 (P k, Ω ω ) (1) for the self-energies, we need to know the analytic proper- F m ν dP ties of the extension Γ(P, z) of the pair propagator to the ΣF(k, ωn) = (2π)3 T Γ(P, Ωm) whole complex (frequency) plane. The→analytic extension m Γ(P, z) is deﬁned by replacing iΩ z on the right- × − − m G0 (P k, Ω ω ) (2) hand side of Eq. (3). It is easy to verify directly from B m n Eq. (3) that Γ(P, z) has a branch-cut on the real axis for ≥ − ≡ Re z 2µ + P2/(2M), where M m + m [? ]. In where the pair propag(cid:26)ator Γ(P(cid:90), Ω ) is given by B F m addition, for suﬃciently strong attraction, the pair prop- agator Γ(P, z) has a pole, which is associated to molec- (cid:34) − m dp (cid:35)(cid:41) ular binding. In order to determine this pole, we ﬁrst Γ(P, Ωm) = 2πra + (2π)3 integrate the terms in Eq. (3) that do not contain(cid:54) the − −1 Fermi or Bose functions [≤thi−s can be done for Imz = 0 × 1 f(ξF− ) + b(ξB) − 2m or for Imz = 0 and Re z 2µ + P2/(2M)]. The pair P p − p r . (3) ξF− + ξB iΩ p2 propagator can be written then P p p m (cid:40) (cid:114) In the above expressions, ω = 2πνT and ω = (2n + ν n 1)πT, Ωm = (2m + 1)πT are bosonic and fermionic Mat- Γ(P, z) = − mr − m√3r/2 (cid:27)P2 − 2µ − z subara frequencies, respectively, (ν, n, m being integer 2πa 2 π 2M numbers), while f(x) and b(x) are the Fermi and Bose − distribution functions at temperature T [f(x) = (ex/T + − 1 − − − − + I (P, z) I (P, z) , (6) 1) 1, b(x) = (ex/T 1) 1]. In Eq. (3) ξs = p2/2m µ B F p s s is the free dispersion relative to the chemical potential µ s for the species s = B, F, while the bare Green’s functions − ≡ appearing in Eqs. (1) and (2) are given by G0 (k, ω ) 1 = where µ (µ + µ )/2, while I (P, z) and I (P, z) − − − B ν B F F B iω ξB and G0 (k, ω ) 1 = iω ξF. are deﬁned by: ν k F n n k ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: tential

text: where

text: m

text: m

text: m

text: /(m

text: m

text: The

text: self-energies

text: and

text: determine

text: the

text: dressed

text: r

text: r

text: B

text: F

text: B

text: F

text: is

text: the

text: reduced

text: mass

text: determined

text: by

text: the

text: boson

text: and

text: fermion

text: Green’s

text: functions

text: G

text: via

text: the

text: Dyson’s

text: equation

text: G

text: s

text: s

text: masses

text: m

text: and

text: m

text: and

text: we

text: have

text: set

text: ¯h

text: The

text: repul-

text: Σ

text: The

text: dressed

text: Green’s

text: functions

text: G

text: in

text: turn,

text: B

text: F

text: s

text: s

text: s

text: sive

text: potential

text: between

text: bosons,

text: which

text: is

text: necessary

text: for

text: allow

text: one

text: to

text: calculate

text: the

text: boson

text: and

text: fermion

text: momentum

text: the

text: stability

text: of

text: the

text: system

text: in

text: the

text: resonance

text: region,

text: can

text: distribution

text: functions

text: n

text: (k)

text: through

text: the

text: equations:

text: s

text: be

text: dropped

text: out

text: from

text: our

text: consideration

text: in

text: the

text: molecular

text: limit

text: of

text: interest

text: to

text: the

text: present

text: paper.

text: A

text: natural

text: length

text: scale

text: of

text: our

text: system,

text: where

text: fermions

text: n

text: (k)

text: G

text: (k,

text: ω

text: are

text: the

text: majority

text: species,

text: is

text: provided

text: by

text: the

text: inverse

text: of

text: B

text: B

text: ν

text: the

text: Fermi

text: wave-vector

text: k

text: (n

text: being

text: the

text: ν

text: fermion

text: number

text: density).FOne

text: may

text: Fus−e

text: thenFthe

text: dimen-

text: nF(k)

text: T

text: GF(k,

text: ωn)

text: sionless

text: coupling

text: parameter

text: g

text: (k

text: a)

text: to

text: describe

text: the

text: n

text: F

text: strength

text: of

text: the

text: interaction.

text: In

text: terms

text: of

text: this

text: parameter,

text: the

text: molecular

text: limit

text: corresponds

text: to

text: the

text: condition

text: g

text: from

text: which

text: the

text: boson

text: and

text: fermion

text: number

text: densities

text: such

text: that

text: the

text: radius

text: of

text: the

text: bound

text: state

text: (which

text: coin-

text: are

text: obtained

text: by

text: integrating

text: over

text: momenta.

text: cides

text: with

text: the

text: scattering

text: length

text: a,

text: for

text: a

text: positive)

text: is

text: much

text: smaller

text: than

text: the

text: average

text: interparticle

text: distance

text: k

text: The

text: full

text: numerical

text: solution

text: of

text: Eqs.

text: was

text: tackled

text: F

text: in

text: our

text: previous

text: works

text: Here

text: we

text: are

text: interested

text: in

text: [Note

text: that

text: in

text: some

text: of

text: our

text: previous

text: works

text: we

text: deriving

text: analytic

text: expressions

text: in

text: the

text: molecular

text: limit

text: of

text: the

text: used

text: a

text: diﬀerent

text: deﬁnition

text: of

text: k

text: (in

text: terms

text: of

text: the

text: total

text: den-

text: F

text: interaction

text: g.

text: In

text: this

text: limit

text: the

text: binding

text: energy

text: is

text: the

text: sity

text: n

text: n

text: n

text: n

text: being

text: the

text: boson

text: number

text: density),

text: F

text: B

text: B

text: largest

text: energy

text: scale:

text: T,

text: E

text: with

text: E

text: which

text: coincides

text: with

text: the

text: present

text: one

text: only

text: for

text: nF

text: nB.]

text: F

text: ≤F

text: F

text: F

text: In

text: addition,

text: for

text: the

text: mixtures

text: with

text: n

text: n

text: of

text: interest

text: The

text: thermodynamic

text: and

text: spectral

text: properties

text: of

text: a

text: Bose-

text: B

text: F

text: to

text: the

text: present

text: paper,

text: the

text: bosonic

text: chemical

text: potential

text: µ

text: Fermi

text: mixture

text: in

text: the

text: normal

text: phase

text: (i.e.

text: above

text: the

text: con-

text: B

text: approaches

text: in

text: the

text: molecular

text: limit,

text: and

text: is

text: thus

text: large

text: densation

text: critical

text: temperature)

text: were

text: studied

text: in

text: our

text: pre-

text: and

text: negative,

text: while

text: the

text: fermion

text: chemical

text: potential

text: re-

text: vious

text: works

text: by

text: using

text: a

text: T-matrix

text: approximation

text: mains

text: of

text: the

text: order

text: of

text: the

text: Fermi

text: energy,

text: and

text: is

text: then

text: small

text: for

text: the

text: self-energies.

text: The

text: corresponding

text: equations

text: for

text: compared

text: to

text: the

text: binding

text: energy.

text: This

text: hierarchy

text: between

text: the

text: bosonic

text: and

text: fermionic

text: self-energies

text: Σ

text: and

text: Σ

text: at

text: ﬁ-

text: B

text: F

text: diﬀerent

text: energy

text: scales

text: will

text: allow

text: us

text: to

text: derive

text: the

text: asymp-

text: nite

text: temperature

text: read

text: (setting

text: the

text: Boltzmann

text: constant

text: kB

text: totic

text: expressions

text: in

text: the

text: molecular

text: limit.

text: B.

text: The

text: pair

text: propagator

text: dP

text: ΣB(k,

text: ων)

text: T

text: Γ(P,

text: Ωm)

text: We

text: focus

text: ﬁrst

text: on

text: the

text: pair

text: propagator

text: Γ(P,

text: Ωm).

text: In

text: order

text: to

text: perform

text: the

text: frequency

text: sum

text: in

text: Eqs.

text: and

text: (P

text: k,

text: Ω

text: ω

text: for

text: the

text: self-energies,

text: we

text: need

text: to

text: know

text: the

text: analytic

text: proper-

text: F

text: m

text: ν

text: dP

text: ties

text: of

text: the

text: extension

text: Γ(P,

text: z)

text: of

text: the

text: pair

text: propagator

text: to

text: the

text: ΣF(k,

text: ωn)

text: T

text: Γ(P,

text: Ωm)

text: whole

text: complex

text: (frequency)

text: plane.

text: The→analytic

text: extension

text: m

text: Γ(P,

text: z)

text: is

text: deﬁned

text: by

text: replacing

text: iΩ

text: z

text: on

text: the

text: right-

text: m

text: (P

text: k,

text: Ω

text: ω

text: hand

text: side

text: of

text: Eq.

text: It

text: is

text: easy

text: to

text: verify

text: directly

text: from

text: B

text: m

text: n

text: Eq.

text: that

text: Γ(P,

text: z)

text: has

text: a

text: branch-cut

text: on

text: the

text: real

text: axis

text: for

text: Re

text: z

text: 2µ

text: where

text: M

text: m

text: m

text: In

text: where

text: the

text: pair

text: Ω

text: is

text: given

text: by

text: B

text: F

text: m

text: addition,

text: for

text: suﬃciently

text: strong

text: attraction,

text: the

text: pair

text: prop-

text: agator

text: Γ(P,

text: z)

text: has

text: a

text: pole,

text: which

text: is

text: associated

text: to

text: molec-

text: m

text: dp

text: ular

text: binding.

text: In

text: order

text: to

text: determine

text: this

text: pole,

text: we

text: ﬁrst

text: Γ(P,

text: Ωm)

text: integrate

text: the

text: terms

text: in

text: Eq.

text: that

text: do

text: not

text: the

text: −1

text: Fermi

text: or

text: Bose

text: functions

text: [≤thi−s

text: can

text: be

text: done

text: for

text: Imz

text: f(ξF−

text: b(ξB)

text: or

text: for

text: Imz

text: and

text: Re

text: z

text: 2µ

text: The

text: pair

text: P

text: p

text: p

text: r

text: ξF−

text: ξB

text: iΩ

text: propagator

text: can

text: be

text: written

text: then

text: P

text: p

text: p

text: m

text: In

text: the

text: above

text: expressions,

text: ω

text: 2πνT

text: and

text: ω

text: ν

text: n

text: Ωm

text: are

text: bosonic

text: and

text: fermionic

text: Mat-

text: Γ(P,

text: z)

text: mr

text: 2µ

text: z

text: subara

text: frequencies,

text: respectively,

text: (ν,

text: n,

text: m

text: being

text: integer

text: π

text: numbers),

text: while

text: f(x)

text: and

text: b(x)

text: are

text: the

text: Fermi

text: and

text: Bose

text: distribution

text: functions

text: at

text: temperature

text: T

text: [f(x)

text: (ex/T

text: I

text: (P,

text: z)

text: I

text: (P,

text: z)

text: b(x)

text: (ex/T

text: In

text: Eq.

text: ξs

text: µ

text: B

text: F

text: p

text: s

text: s

text: is

text: the

text: free

text: dispersion

text: relative

text: to

text: the

text: chemical

text: potential

text: µ

text: s

text: for

text: the

text: species

text: s

text: B,

text: F,

text: while

text: the

text: bare

text: Green’s

text: functions

text: appearing

text: in

text: Eqs.

text: and

text: are

text: given

text: by

text: (k,

text: ω

text: where

text: µ

text: (µ

text: µ

text: while

text: I

text: (P,

text: z)

text: and

text: I

text: (P,

text: z)

text: B

text: ν

text: B

text: F

text: F

text: B

text: iω

text: ξB

text: and

text: (k,

text: ω

text: iω

text: ξF.

text: are

text: deﬁned

text: by:

text: ν

text: k

text: F

text: n

text: n

text: k

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 12 Fig. ?? correspond to the mixtures 23Na-40K, 87Rb-40K, 1 (a) and 23Na-6Li, of relevance to current experiments [? ], m /m =0.2 B F [? ], [? ]. It should be stressed, in this respect, that 23/40 0.8 1 while the Feshbach resonances used for the ﬁrst two mix- 87/40 tures are broad [? ? ], the one currently used for the (r)α 0.6 23/6 2ﬁ3rNstat-w6Loimmiixxttuurreesitshneasrirnogwle-[?ch]a.nTnehledreefsocrreip, twiohnileadfoorptthede 0.4 in the present work is fully adequate [? ], for the last α=0.90 one our analysis has to be regarded as more qualitative. 0.2 g=4 We notice ﬁnally that out of these three mixtures, the 23Na-40K mixture looks as as the most promising one for 0 0 0.2 0.4 0.6 0.8 1 1.2 the experimental observation of the indirect Pauli exclu- r sion eﬀect, since it leads to a wider depleted region in the bosonic momentum distribution. 0.0005 (b) m /m =0.2 B F IV. CONCLUDING REMARKS 23/40 0.0004 1 87/40 In summary, we have shown how, within a T-matrix k) 0.0003 23/6 diagrammatic approach, a Fermi-Fermi mixture emerges p( traB eﬀectively from a Bose-Fermi mixture for suﬃciently n 0.0002 strong attraction. In this limit, we have derived simple expressions for the bosonic and fermionic self-energies, α=0.90 0.0001 momentum distribution functions, and chemical poten- g=4 tials. In particular, we have obtained an expression for 0 the bosonic momentum distribution function that shows 0 0.5 1 1.5 2 2.5 3 3.5 4 analytically the presence of a completely depleted re- k gion at low momenta when n < n /2. The occurrence B F of this region is the ﬁngerprint of what we called the FIG. 7. (Color online) (a) Local density imbalance α(r), and indirect Pauli exclusion eﬀect. We have conﬁrmed the (b) trap-averaged bosonic momentum distribution function ntrap(k) at g = 4 and α = 0.9 for diﬀerent values of the mass presence of such a region also with a dedicated QMC B ratio m /m . The wave-vector k is in units of k , while r is simulation. This required us to address the non-trivial B F F in units of R . problem of symmetrizing with respect to the bosonic F coordinates a trial wave function where the bosons are correlated with fermions in a molecular bound state. To local density imbalance depends on three diﬀerent phys- this end, we have introduced a wave function where the ical parameters: the global population imbalance α, the symmetrization is performed within each molecular or- boson-fermion coupling g and the mass ratio mB/mF. bital rather than globally, as to keep the computing time One has then to tune appropriately these parameters. manageable. Obviously, a large global population imbalance increases Finally, we have discussed the possibility of observing the local one, as it is also evident from Fig. ??. the indirect Pauli exclusion eﬀect in a trapped system, Figure ?? shows instead that, for a given population by extending within a local density approximation our imbalance, increasing the coupling strength g has a mod- calculations to such an inhomogeneous situation. We est eﬀect on α(r), while the momentum distribution func- have found that mixtures where the bosons are lighter tion is reduced at low k (and increased at large k, outside than the fermions enhance the size and visibility of the the range shown in Fig. ??), reﬂecting the behavior of the depleted region: the mixture 23Na-40K currently under internal molecular wave function (38). study at the MIT [? ] appears particularly interesting in The dependence on the mass ratio m /m is stud- B F this respect. ied ﬁnally in Fig. ??. One can see that for given cou- ACKNOWLEDGMENTS pling strength and population imbalance (here g = 4 and α = 0.9), decreasing the mass ratio m /m increases B F the local population imbalance, thus making more evi- G.B. acknowledges useful discussions with D.E. Galli. dent the presence of the empty region at low momenta. Part of the QMC simulations were performed on the Su- Note that three out of the ﬁve mass ratios considered in perB cluster at EPFL. ∗ [2] D. B. M. Dickerscheid, D. van Oosten, E. J. Tillema, and H. T. C. Stoof, Phys. Rev. Lett. 94, 230404 (2005). [1] S. Powell, S. Sachdev, and H. P. Buchler, Phys. Rev. B 72, 02[435] 3A4.(S2t0o0r5o)z.henko, P. Schuck, T. Suzuki, H. Yabu, and J. Dukelsky, Phys. Rev. A 71, 063617 (2005). ##LTFigure## ##LTLine## ##LTLine## ##LTLine##

text: Fig.

text: correspond

text: to

text: the

text: mixtures

font: default

text: (a)

text: and

text: of

text: relevance

text: to

text: current

text: experiments

text: m

text: /m

text: B

text: F

text: It

text: should

text: be

text: stressed,

text: in

text: this

text: respect,

text: that

text: while

text: the

text: Feshbach

text: resonances

text: used

text: for

text: the

text: ﬁrst

text: two

text: mix-

text: tures

text: are

text: broad

text: the

text: one

text: currently

text: used

text: for

text: the

text: (r)α

text: twiohnileadfoorptthede

text: in

text: the

text: present

text: work

text: is

text: fully

text: adequate

text: for

text: the

text: last

text: one

text: our

text: analysis

text: has

text: to

text: be

text: regarded

text: as

text: more

text: qualitative.

text: We

text: notice

text: ﬁnally

text: that

text: out

text: of

text: these

text: three

text: mixtures,

text: the

text: mixture

text: looks

text: as

text: as

text: the

text: most

text: promising

text: one

text: for

text: the

text: experimental

text: observation

text: of

text: the

text: indirect

text: Pauli

text: exclu-

text: r

text: sion

text: eﬀect,

text: since

text: it

text: leads

text: to

text: a

text: wider

text: depleted

text: region

text: in

text: the

text: bosonic

text: momentum

text: distribution.

text: (b)

text: m

text: /m

text: B

text: F

text: IV.

text: CONCLUDING

text: REMARKS

text: In

text: summary,

text: we

text: have

text: shown

text: how,

text: within

text: a

text: T-matrix

text: k)

text: diagrammatic

text: approach,

text: a

text: Fermi-Fermi

text: mixture

text: emerges

text: p(

text: traB

text: eﬀectively

text: from

text: a

text: Bose-Fermi

text: mixture

text: for

text: suﬃciently

text: n

text: strong

text: attraction.

text: In

text: this

text: limit,

text: we

text: have

text: derived

text: simple

text: expressions

text: for

text: the

text: bosonic

text: and

text: fermionic

text: self-energies,

text: momentum

text: distribution

text: functions,

text: and

text: chemical

text: poten-

text: tials.

text: In

text: particular,

text: we

text: have

text: obtained

text: an

text: expression

text: for

text: the

text: bosonic

text: momentum

text: distribution

text: function

text: that

text: shows

text: analytically

text: the

text: presence

text: of

text: a

text: completely

text: depleted

text: re-

text: k

text: gion

text: at

text: low

text: momenta

text: when

text: n

text: n

text: The

text: occurrence

text: B

text: F

text: of

text: this

text: region

text: is

text: the

text: ﬁngerprint

text: of

text: what

text: we

text: called

text: the

text: FIG.

text: (Color

text: online)

text: (a)

text: Local

text: density

text: imbalance

text: α(r),

text: and

text: indirect

text: Pauli

text: exclusion

text: eﬀect.

text: We

text: have

text: conﬁrmed

text: the

text: (b)

text: trap-averaged

text: bosonic

text: momentum

text: distribution

text: function

text: ntrap(k)

text: at

text: g

text: and

text: α

text: for

text: diﬀerent

text: values

text: of

text: the

text: mass

text: presence

text: of

text: such

text: a

text: region

text: also

text: with

text: a

text: dedicated

text: QMC

text: B

text: ratio

text: m

text: /m

text: The

text: wave-vector

text: k

text: is

text: in

text: units

text: of

text: k

text: while

text: r

text: is

text: simulation.

text: This

text: required

text: us

text: to

text: address

text: the

text: non-trivial

text: B

text: F

text: F

text: in

text: units

text: of

text: R

text: problem

text: of

text: symmetrizing

text: with

text: respect

text: to

text: the

text: bosonic

text: F

text: coordinates

text: a

text: trial

text: wave

text: function

text: where

text: the

text: bosons

text: are

text: correlated

text: with

text: fermions

text: in

text: a

text: molecular

text: bound

text: state.

text: To

text: local

text: density

text: imbalance

text: depends

text: on

text: three

text: diﬀerent

text: phys-

text: this

text: end,

text: we

text: have

text: introduced

text: a

text: wave

text: function

text: where

text: the

text: ical

text: parameters:

text: the

text: global

text: population

text: imbalance

text: α,

text: the

text: symmetrization

text: is

text: performed

text: within

text: each

text: molecular

text: or-

text: boson-fermion

text: coupling

text: g

text: and

text: the

text: mass

text: ratio

text: mB/mF.

text: bital

text: rather

text: than

text: globally,

text: as

text: to

text: keep

text: the

text: computing

text: time

text: One

text: has

text: then

text: to

text: tune

text: appropriately

text: these

text: parameters.

text: manageable.

text: Obviously,

text: a

text: large

text: global

text: population

text: imbalance

text: increases

text: Finally,

text: we

text: have

text: discussed

text: the

text: possibility

text: of

text: observing

text: the

text: local

text: one,

text: as

text: it

text: is

text: also

text: evident

text: from

text: Fig.

text: the

text: indirect

text: Pauli

text: exclusion

text: eﬀect

text: in

text: a

text: trapped

text: system,

text: Figure

text: shows

text: instead

text: that,

text: for

text: a

text: given

text: population

text: by

text: extending

text: within

text: a

text: local

text: density

text: approximation

text: our

text: imbalance,

text: increasing

text: the

text: coupling

text: strength

text: g

text: has

text: a

text: mod-

text: calculations

text: to

text: such

text: an

text: inhomogeneous

text: situation.

text: We

text: est

text: eﬀect

text: on

text: α(r),

text: while

text: the

text: momentum

text: distribution

text: func-

text: have

text: found

text: that

text: mixtures

text: where

text: the

text: bosons

text: are

text: lighter

text: tion

text: is

text: reduced

text: at

text: low

text: k

text: (and

text: increased

text: at

text: large

text: k,

text: outside

text: than

text: the

text: fermions

text: enhance

text: the

text: size

text: and

text: visibility

text: of

text: the

text: the

text: range

text: shown

text: in

text: Fig.

text: reﬂecting

text: the

text: behavior

text: of

text: the

text: depleted

text: region:

text: the

text: mixture

text: currently

text: under

text: internal

text: molecular

text: wave

text: function

text: study

text: at

text: the

text: MIT

text: appears

text: particularly

text: interesting

text: in

text: The

text: dependence

text: on

text: the

text: mass

text: ratio

text: m

text: /m

text: is

text: stud-

text: B

text: F

text: this

text: respect.

text: ied

text: ﬁnally

text: in

text: Fig.

text: One

text: can

text: see

text: that

text: for

text: given

text: cou-

text: ACKNOWLEDGMENTS

text: pling

text: strength

text: and

text: population

text: imbalance

text: (here

text: g

text: and

text: α

text: decreasing

text: the

text: mass

text: ratio

text: m

text: /m

text: increases

text: B

text: F

text: the

text: local

text: population

text: imbalance,

text: thus

text: making

text: more

text: evi-

text: G.B.

text: acknowledges

text: useful

text: discussions

text: with

text: D.E.

text: Galli.

text: dent

text: the

text: presence

text: of

text: the

text: empty

text: region

text: at

text: low

text: momenta.

text: Part

text: of

text: the

text: QMC

text: simulations

text: were

text: performed

text: on

text: the

text: Su-

text: Note

text: that

text: three

text: out

text: of

text: the

text: ﬁve

text: mass

text: ratios

text: considered

text: in

text: perB

text: cluster

text: at

text: EPFL.

text: D.

text: B.

text: M.

text: Dickerscheid,

text: D.

text: van

text: Oosten,

text: E.

text: J.

text: Tillema,

text: and

text: H.

text: T.

text: C.

text: Stoof,

text: Phys.

text: Rev.

text: Lett.

text: S.

text: Powell,

text: S.

text: Sachdev,

text: and

text: H.

text: P.

text: Buchler,

text: Phys.

text: Rev.

text: B

text: P.

text: Schuck,

text: T.

text: Suzuki,

text: H.

text: Yabu,

text: and

text: J.

text: Dukelsky,

text: Phys.

text: Rev.

text: A

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##