text: | a realization o of the variables O. The problem is to compute arg max p(H = h O = o) or h equivalently the argument of: (cid:104) (cid:89) (cid:105) T max (ψ (h )ψ (o , h )) (ψ (h − , h )ψ (o , h )) (5) h1,...,hT H1 1 O1,H1 1 1 Hi−1,Hi i 1 i Oi,Hi i i i=2 The number of possible realizations of H is exponential in T . Nevertheless this optimization problem can be solved in a number of operations linear in T using the well-known Viterbi al- gorithm (Rabiner, 1989). This algorithm, based on dynamic programming, performs successive eliminations (by maximization) of all hidden variables, starting with H , then H − , and ﬁnishing T T 1 by H , to compute the most likely sequence of hidden variables. By using distributivity between 1 the max and the product operators, the elimination of variable H can be done by rewriting equa- T tion (5) as: (cid:104) max (cid:89)ψ(cid:0) (h )ψ (o , h ) (cid:1)(cid:105) h1,...,hT−1 H1 1 O1,H1 1 1 − T 1 (cid:124) (cid:123)(cid:122) (cid:125) ψ (h − , h )ψ (o , h ). max ψ (h − , h )ψ (o , h ) Hi−1,Hi i 1 i Oi,Hi i i hT HT−1,HT T 1 T OT,HT T T i=2 New potential function The new potential function created by maximizing on H depends only on variable H − , so T T 1 that variables H , O and potential functions involving them have been removed from the opti- T T mization problem. This is a simple application of the general variable elimination algorithm that we describe in the next section. 3.2 General principle of variable elimination In Section , we have seen that counting and optimization tasks can be formalized by the same generic algebraic formulation ⊕ (cid:12) ( ψ ) (6) ∈B B xA B ⊂ where A V . The trick behind variable elimination (Bertele´ and Brioshi, 1972) relies on a clever use of the (cid:12) ⊕ (cid:12) (cid:12) ⊕ distributivity property. Indeed, evaluating (a b) (a c) as a (b c) requires fewer operations. Since distributivity applies both for counting and optimizing tasks, variable elimination can be applied to both tasks. It also means that if variable elimination is efﬁcient for one task it will also be efﬁcient for the other one. As in the HMC example, the principle of the variable elimination algorithm for counting or optimizing consists in eliminating variables one by one in expression (6). 9

text: a

text: realization

text: o

text: of

text: the

text: variables

text: O.

text: The

text: problem

text: is

text: to

text: compute

text: arg

text: max

text: p(H

text: h

text: O

text: o)

text: or

text: h

text: equivalently

text: the

text: argument

text: of:

text: T

text: max

text: (ψ

text: (h

text: )ψ

text: (o

text: h

text: (ψ

text: (h

text: h

text: )ψ

text: (o

text: h

text: i

text: i

text: Oi,Hi

text: i

text: i

text: The

text: number

text: of

text: possible

text: realizations

text: of

text: H

text: is

text: exponential

text: in

text: T

text: Nevertheless

text: this

text: optimization

text: problem

text: can

text: be

text: solved

text: in

text: a

text: number

text: of

text: operations

text: linear

text: in

text: T

text: using

text: the

text: well-known

text: Viterbi

text: al-

text: gorithm

text: (Rabiner,

text: This

text: algorithm,

text: based

text: on

text: dynamic

text: programming,

text: performs

text: successive

text: eliminations

text: (by

text: maximization)

text: of

text: all

text: hidden

text: variables,

text: starting

text: with

text: H

text: then

text: H

text: and

text: ﬁnishing

text: T

text: T

text: by

text: H

text: to

text: compute

text: the

text: most

text: likely

text: sequence

text: of

text: hidden

text: variables.

text: By

text: using

text: distributivity

text: between

text: the

text: max

text: and

text: the

text: product

text: operators,

text: the

text: elimination

text: of

text: variable

text: H

text: can

text: be

text: done

text: by

text: rewriting

text: equa-

text: T

text: tion

text: as:

text: max

text: (h

text: )ψ

text: (o

text: h

text: T

text: ψ

text: (h

text: h

text: )ψ

text: (o

text: h

text: max

text: ψ

text: (h

text: h

text: )ψ

text: (o

text: h

text: i

text: i

text: Oi,Hi

text: i

text: i

text: hT

text: T

text: T

text: OT,HT

text: T

text: T

text: New

text: potential

text: function

text: The

text: new

text: potential

text: function

text: created

text: by

text: maximizing

text: on

text: H

text: depends

text: only

text: on

text: variable

text: H

text: so

text: T

text: T

text: that

text: variables

text: H

text: O

text: and

text: potential

text: functions

text: involving

text: them

text: have

text: been

text: removed

text: from

text: the

text: opti-

text: T

text: T

text: mization

text: problem.

text: This

text: is

text: a

text: simple

text: application

text: of

text: the

text: general

text: variable

text: elimination

text: algorithm

text: that

text: we

text: describe

text: in

text: the

text: next

text: section.

text: General

text: principle

text: of

text: variable

text: elimination

text: In

text: Section

text: we

text: have

text: seen

text: that

text: counting

text: and

text: optimization

text: tasks

text: can

text: be

text: formalized

text: by

text: the

text: same

text: generic

text: algebraic

text: formulation

text: ψ

text: ∈B

text: B

text: xA

text: B

text: where

text: A

text: V

text: The

text: trick

text: behind

text: variable

text: elimination

text: (Bertele´

text: and

text: Brioshi,

text: relies

text: on

text: a

text: clever

text: use

text: of

text: the

text: distributivity

text: property.

text: Indeed,

text: evaluating

text: (a

text: b)

text: (a

text: c)

text: as

text: a

text: (b

text: c)

text: requires

text: fewer

text: operations.

text: Since

text: distributivity

text: applies

text: both

text: for

text: counting

text: and

text: optimizing

text: tasks,

text: variable

text: elimination

text: can

text: be

text: applied

text: to

text: both

text: tasks.

text: It

text: also

text: means

text: that

text: if

text: variable

text: elimination

text: is

text: efﬁcient

text: for

text: one

text: task

text: it

text: will

text: also

text: be

text: efﬁcient

text: for

text: the

text: other

text: one.

text: As

text: in

text: the

text: HMC

text: example,

text: the

text: principle

text: of

text: the

text: variable

text: elimination

text: algorithm

text: for

text: counting

text: or

text: optimizing

text: consists

text: in

text: eliminating

text: variables

text: one

text: by

text: one

text: in

text: expression


text: 2 2 2 3 3 3 1 1 4 4 4 5 5 5 Figure 3: Elimination of variable X replaces the four pairwise potential functions involving vari- 1 able X with a new potential ψ , involving the four neighbors of vertex 1 in the original graph. 1 N1 The new edges created between these four vertices are called ﬁll-in edges (dashed edges in the middle ﬁgure). ∈ Elimination of the ﬁrst variable, say X , i A, is performed by merging all potential functions ⊕ i involving X and applying operator to thes(cid:18)e potential functions. (cid:19)Using commutativity and i xi associativity equation (6) can be rewritten as follows: ⊕ (cid:12) ⊕ ⊕ (cid:12) (cid:12) ( ψ ) = ( ψ )( ψ ) ∈B B ∈B\B B ∈B B xA B xA\{i} xi B i B i (cid:104) (cid:105) Then using distributivity we obtain ⊕ (cid:12) ⊕ (cid:12) ⊕ (cid:12) (cid:124) (cid:123)(cid:122) (cid:125) (cid:12) ( ψ ) = ( ψ ) ( ψ ) ∈B B ∈B\B B ∈B B xA B xA\{i} B i xi B i New potential function ψNi This shows that the elimination of X results in a new graphical model where the variable X ∈ B i i and the potential functions ψ , B have been removed and replaced by a new potential ψ B i Ni which does not involve X , but its neighboring vertices. The graph associated to the new graphical i model is similar to the graph of the original model except that vertex X has been removed and i that the neighbors N of X are now connected together in a clique. The new edges between i i the neighbors of X are called ﬁll-in edges. For instance, when eliminating variable X in the i 1 graph of Figure 3 (left), potential functions ψ , ψ , ψ and ψ are replaced by ψ = ⊕ (cid:12) (cid:12) (cid:12) 1,2 1,3 1,4 1,5 2,3,4,5 (ψ ψ ψ ψ ). The new graph is shown in Figure 3, right part. x1 1,2 1,3 1,4 1,4 ⊕ (cid:12) × When the ﬁrst elimination step is applied with = + and = , the probability distribution deﬁned by this new graphical model is the marginal distribution p(x \{ }) of the original distri- V i bution p. The complete elimination can be obtained by successively eliminating all variables in X . The result is a graphical model over X \ which is the marginal distribution p(x \ ). When A V A V A A = V , the result is a model with a single constant potential function with value Z. ⊕ (cid:12) × If instead is max, and = (or + with a log transformation of the potential functions) and A = V , the last potential function obtained after elimination of the last variable is equal to the maximum of the non normalized distribution. So evaluating Z or the maximal probability of a graphical model can be both obtained with the same variable elimination algorithm, just changing 10 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: paragraph

text: Figure

text: Elimination

label: caption

text: of

text: variable

text: X

text: replaces

text: the

text: four

text: pairwise

text: potential

text: functions

text: involving

text: vari-

text: able

text: X

text: with

text: a

text: new

text: potential

text: ψ

text: involving

text: the

text: four

text: neighbors

text: of

text: vertex

text: in

text: the

text: original

text: graph.

text: The

text: new

text: edges

text: created

text: between

text: these

text: four

text: vertices

text: are

text: called

text: ﬁll-in

text: edges

text: (dashed

text: edges

text: in

text: the

text: middle

text: ﬁgure).

text: Elimination

text: of

text: the

text: ﬁrst

text: variable,

text: say

text: X

text: i

text: A,

text: is

text: performed

text: by

text: merging

text: all

text: potential

text: functions

text: i

text: involving

text: X

text: and

text: applying

text: operator

text: to

text: potential

text: functions.

text: commutativity

text: and

text: i

text: xi

text: associativity

text: equation

text: can

text: be

text: rewritten

text: as

text: follows:

text: ψ

text: ψ

text: ψ

text: ∈B

text: B

text: ∈B\B

text: B

text: ∈B

text: B

text: xA

text: B

text: xA\{i}

text: xi

text: B

text: i

text: B

text: i

text: Then

text: using

text: distributivity

text: we

text: obtain

text: ψ

text: ψ

text: ψ

text: ∈B

text: B

text: ∈B\B

text: B

text: ∈B

text: B

text: xA

text: B

text: xA\{i}

text: B

text: i

text: xi

text: B

text: i

text: New

text: potential

text: function

text: ψNi

text: This

text: shows

text: that

text: the

text: elimination

text: of

text: X

text: results

text: in

text: a

text: new

text: graphical

text: model

text: where

text: the

text: variable

text: X

text: B

text: i

text: i

text: and

text: the

text: potential

text: functions

text: ψ

text: B

text: have

text: been

text: removed

text: and

text: replaced

text: by

text: a

text: new

text: potential

text: ψ

text: B

text: i

text: Ni

text: which

text: does

text: not

text: involve

text: X

text: but

text: its

text: neighboring

text: vertices.

text: The

text: graph

text: associated

text: to

text: the

text: new

text: graphical

text: i

text: model

text: is

text: similar

text: to

text: the

text: graph

text: of

text: the

text: original

text: model

text: except

text: that

text: vertex

text: X

text: has

text: been

text: removed

text: and

text: i

text: that

text: the

text: neighbors

text: N

text: of

text: X

text: are

text: now

text: connected

text: together

text: in

text: a

text: clique.

text: The

text: new

text: edges

text: between

text: i

text: i

text: the

text: neighbors

text: of

text: X

text: are

text: called

text: ﬁll-in

text: edges.

text: For

text: instance,

text: when

text: eliminating

text: variable

text: X

text: in

text: the

text: i

text: graph

text: of

text: Figure

text: (left),

text: potential

text: functions

text: ψ

text: ψ

text: ψ

text: and

text: ψ

text: are

text: replaced

text: by

text: ψ

text: (ψ

text: ψ

text: ψ

text: ψ

text: The

text: new

text: graph

text: is

text: shown

text: in

text: Figure

text: right

text: part.

text: When

text: the

text: ﬁrst

text: elimination

text: step

text: is

text: applied

text: with

text: and

text: the

text: probability

text: distribution

text: deﬁned

text: by

text: this

text: new

text: graphical

text: model

text: is

text: the

text: marginal

text: distribution

text: p(x

text: of

text: the

text: original

text: distri-

text: V

text: i

text: bution

text: p.

text: The

text: complete

text: elimination

text: can

text: be

text: obtained

text: by

text: successively

text: eliminating

text: all

text: variables

text: in

text: X

text: The

text: result

text: is

text: a

text: graphical

text: model

text: over

text: X

text: which

text: is

text: the

text: marginal

text: distribution

text: p(x

text: When

text: A

text: V

text: A

text: V

text: A

text: A

text: V

text: the

text: result

text: is

text: a

text: model

text: with

text: a

text: single

text: constant

text: potential

text: function

text: with

text: value

text: Z.

text: If

text: instead

text: is

text: max,

text: and

text: (or

text: with

text: a

text: log

text: transformation

text: of

text: the

text: potential

text: functions)

text: and

text: A

text: V

text: the

text: last

text: potential

text: function

text: obtained

text: after

text: elimination

text: of

text: the

text: last

text: variable

text: is

text: equal

text: to

text: the

text: maximum

text: of

text: the

text: non

text: normalized

text: distribution.

text: So

text: evaluating

text: Z

text: or

text: the

text: maximal

text: probability

text: of

text: a

text: graphical

text: model

text: can

text: be

text: both

text: obtained

text: with

text: the

text: same

text: variable

text: elimination

text: algorithm,

text: just

text: changing

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: A&A proofs: manuscript no. Gundlach_etal_2015_arxiv_version experimentally showed that Eq. 1 is quantitatively correct (see dust-aggregate layer and at two diﬀerent heliocentric distances their Fig. 17). The smallest dust-aggregate radius that can be (at 1 AU and 2 AU; see Figs. 1a and 1b). released from the surface by the sublimation of the ices is given For another test of the validity of the approximation, we cal- if the gas pressure p equals the tensile strength of the aggregate culated the resulting gas pressure for CO ice (at 2 AU and 3 AU; × 2 − layer (E(cid:32)q. 1),(cid:33) latent heat of sublimation: Λ = 5.7 105 J kg 1; Mavko et al. 2009, see Figs. 1c and 1d) and for CO ice (at 3 AU and 4 AU; la- × − − tent heat of sublimation: Λ = 3.0 105 J kg 1; Brown & Ziegler p 1 3/2 1979, see Figs. 1e and 1f). These two volatile materials were smin = Y φ . (2) chosen because of their relatively high abundance in comets and because model calculations suggest that volatile species incor- porated in planets after their formation are mainly composed of For cometary surface layers formed by gravitational instabil- ity (i.e., for dust aggregate layers), the tensile strength is very H2O, CO2, CO, CH3OH, and NH3 (Marboeuf et al. 2014). ∼ A comparison of the derived gas pressure at the ice-dust in- low ( 1 Pa) and somewhat counterintuitively decreases with in- terface using the thermophysical model (solid blue curves in Fig. creasing dust-aggregate size (Skorov & Blum 2012; Blum et al. 1) with the approximation of Eq. 3 (dashed black line; derived 2014). Hence, it is easier to release larger dust aggregates than for the temperature of the ice-dust interface at which the high- smaller ones. For example, a densely packed aggregate layer est pressure is reached in the thermophysical model) yields the with a volume-ﬁlling factor of 0.6 consisting of 100 µm-sized deviations indicated by the arrows in Fig. 1. The pressure ra- dust aggregates possesses a tensile strength of 4.5 Pa, whereas tio between the approximation and the thermophysical model increasing the aggregate size to 1 cm yields a tensile strength of indicated in Fig. 1 was calculated for the maxima of the pres- 0.2 Pa. sure curves, because the maximum yields the smallest aggregate The gas pressure p of the sublimating ice, covered by a size that can be released by the gas pressure. For the considered porous dust layer, depends on its transport characteristics (gas cases, the maximum gas pressure is typically reached for a dust permeability) and on the energy supplied to the region. The lat- layer thickness between two and ﬁve aggregate layers. ter depends on the heliocentric distance, on the nucleus albedo, Figure shows 1 that the deviation from the thermophysical on the thickness, and on the heat conductivity of the covering model to the approximation of Eq. 3 increases with increasing dust layer. A detailed heat-conductivity model for granular ma- heliocentric distance. This can be explained by the following terials in vacuum was presented by Gundlach & Blum (2012) considerations. For reasonable dust-aggregate sizes and surface and Gundlach & Blum (2013). Together with the available en- temperatures, the heat conductivity is dominated by radiative ergy for the sublimation process, the permeability of the cover- transport and, thus, increases strongly with increasing tempera- ing dust layer determines the pressure build-up at the depth of ture, that is, with decreasing heliocentric distance (see Gundlach the ice-dust interface (Gundlach et al. 2011; Blum et al. 2014, & Blum 2012; Gundlach & Blum 2013, for details). Therefore, 2015). In the following, this detailed model is referred to as the the fraction of absorbed energy that is transported into the inte- thermophysical model. rior of the comet nucleus and, thus, used to evaporate volatile In general, the derivation of the gas pressure at the ice- ices, also increases with decreasing heliocentric distance. On dust interface should be determined from full consideration of the other hand, for increasing heliocentric distances, the relative the conservation of energy, momentum, and mass for solid and importance of thermal reradiation of the surface into deep space gaseous phases. However, such a detailed consideration is far increases (see Blum et al. 2015, for details). beyond the scope of this paper. We wish to simplify the physical For example, the smallest aggregate size increases from model as much as possible (keep it reasonable) to highlight the 2 mm to 6 mm for H O ice activity at 1 AU if the thermophysi- new qualitative results. For this reason, we simpliﬁed the deriva- 2 cal model is used instead of the approximation. At 2 AU and for tion of the gas pressure at the ice-dust interface by the approxi- H O ice sublimation, the smallest aggregate size changes from mation that the incoming energy that is absorbed by the nucleus 2 18 mm (approximation) to 174 mm (thermophysical model). is entirely used for the sublimation of the volatiles (i.e., thermal The calculations shown in Fig. 1 were only performed for reradiation of the comet nucleus and energy dissipation by its one aggregate size of 1 mm because the systematic simulations core are neglected). The reasonableness of this simpliﬁcation is illustrated below. With this assumption, the gas pressure at the showed that starting from an aggregate radius of 15 µm, the vari- ation of the aggregate size does not considerably inﬂuence the ice-dust interface i(cid:32)s giv(cid:33)en by(cid:114) resulting pressure at the ice-dust interface (see Fig. 2). With the knowledge of the gas pressure at the ice-dust inter- p = ( 1 − A ) IE aaEh 2 Λ1 2 π kmTice , (3) fcwaaicnteh,btiehteriestlepenoasssiesledibslfetrroetmongdtthehreiovsfeutrthfheaecdesumbstay-lalcegosgmtredpguaasrttie-naglgagtyhreeerg.gaates psirzeesstuhraet Strictly speaking, the assumption that all absorbed energy is where A is the Bond albedo of the surface material, I is the used by the sublimation of the ice gives us the highest eﬀective E solar constant, a is the distance of the Earth to the Sun, a is sublimation rate (i.e., highest mass loss per second) and not pres- E h the heliocentric distance of the comet, Λ is the latent heat of the sure. However, numerical tests agree with the values retrieved sublimating ice, k is the Boltzmann constant, T is the tempera- from Eq. 3 (see Fig. 1). Considering the thermal emission in ice ture of the evaporating ice, and m is the mass of the evaporating the energy budget leads to a reduction of the eﬀective loss mass. molecules. The role of this dissipation channel was discussed by Blum et al. To illustrate the plausibility of this simpliﬁcation, the results (2015), where it was shown that this eﬀect is weak close to the of Eq. 3 are compared with the corresponding pressure obtained Sun and increases with heliocentric distance. Because the tensile from the sophisticated thermophysical model for H O ice (latent strength of the covering aggregate layer is a decreasing function × − 2 heat of sublimation: Λ = 2.6 106 J kg 1; Orosei et al. 1995) of aggregate size (see Eq. 1), the larger grains can be lifted eas- at the ice-dust interface for diﬀerent thicknesses of the covering ily and their size is only restricted by the cometary gravity. In Article number, page 4 of 8page.8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A&A

text: proofs:

text: manuscript

text: no.

text: experimentally

text: showed

text: that

text: Eq.

text: is

text: quantitatively

text: correct

text: (see

text: dust-aggregate

text: layer

text: and

text: at

text: two

text: diﬀerent

text: heliocentric

text: distances

text: their

text: Fig.

text: The

text: smallest

text: dust-aggregate

text: radius

text: that

text: can

text: be

text: (at

text: AU

text: and

text: AU;

text: see

text: Figs.

text: and

text: released

text: from

text: the

text: surface

text: by

text: the

text: sublimation

text: of

text: the

text: ices

text: is

text: given

text: For

text: another

text: test

text: of

text: the

text: validity

text: of

text: the

text: approximation,

text: we

text: cal-

text: if

text: the

text: gas

text: pressure

text: p

text: equals

text: the

text: tensile

text: strength

text: of

text: the

text: aggregate

text: culated

text: the

text: resulting

text: gas

text: pressure

text: for

text: CO

text: ice

text: (at

text: AU

text: and

text: AU;

font: TEQMIX+txsy

text: layer

label: equation

text: latent

text: heat

text: of

text: sublimation:

text: Λ

text: J

text: kg

text: Mavko

text: et

text: al.

text: see

text: Figs.

text: and

text: and

text: for

text: CO

text: ice

text: (at

text: AU

text: and

text: AU;

text: la-

text: tent

text: heat

text: of

text: sublimation:

text: Λ

text: J

text: kg

text: Brown

text: Ziegler

text: p

text: see

text: Figs.

text: and

text: These

text: two

text: volatile

text: materials

text: were

text: smin

text: Y

text: φ

text: chosen

text: because

text: of

text: their

text: relatively

text: high

text: abundance

text: in

text: comets

text: and

text: because

text: model

text: calculations

text: suggest

text: that

text: volatile

text: species

text: incor-

text: porated

text: in

text: planets

text: after

text: their

text: formation

text: are

text: mainly

text: composed

text: of

text: For

text: cometary

text: surface

text: layers

text: formed

text: by

text: gravitational

text: instabil-

text: ity

text: (i.e.,

text: for

text: dust

text: aggregate

text: layers),

text: the

text: tensile

text: strength

text: is

text: very

text: CO,

text: and

text: (Marboeuf

text: et

text: al.

text: A

text: comparison

text: of

text: the

text: derived

text: gas

text: pressure

text: at

text: the

text: ice-dust

text: in-

text: low

text: Pa)

text: and

text: somewhat

text: counterintuitively

text: decreases

text: with

text: in-

text: terface

text: using

text: the

text: thermophysical

text: model

text: (solid

text: blue

text: curves

text: in

text: Fig.

text: creasing

text: dust-aggregate

text: size

text: (Skorov

text: Blum

text: Blum

text: et

text: al.

text: with

text: the

text: approximation

text: of

text: Eq.

text: (dashed

text: black

text: line;

text: derived

text: Hence,

text: it

text: is

text: easier

text: to

text: release

text: larger

text: dust

text: aggregates

text: than

text: for

text: the

text: temperature

text: of

text: the

text: ice-dust

text: interface

text: at

text: which

text: the

text: high-

text: smaller

text: ones.

text: For

text: example,

text: a

text: densely

text: packed

text: aggregate

text: layer

text: est

text: pressure

text: is

text: reached

text: in

text: the

text: thermophysical

text: model)

text: yields

text: the

text: with

text: a

text: volume-ﬁlling

text: factor

text: of

text: consisting

text: of

text: µm-sized

text: deviations

text: indicated

text: by

text: the

text: arrows

text: in

text: Fig.

text: The

text: pressure

text: ra-

text: dust

text: aggregates

text: possesses

text: a

text: tensile

text: strength

text: of

text: Pa,

text: whereas

text: tio

text: between

text: the

text: approximation

text: and

text: the

text: thermophysical

text: model

text: increasing

text: the

text: aggregate

text: size

text: to

text: cm

text: yields

text: a

text: tensile

text: strength

text: of

text: indicated

text: in

text: Fig.

text: was

text: calculated

text: for

text: the

text: maxima

text: of

text: the

text: pres-

text: Pa.

text: sure

text: curves,

text: because

text: the

text: maximum

text: yields

text: the

text: smallest

text: aggregate

text: The

text: gas

text: pressure

text: p

text: of

text: the

text: sublimating

text: ice,

text: covered

text: by

text: a

text: size

text: that

text: can

text: be

text: released

text: by

text: the

text: gas

text: pressure.

text: For

text: the

text: considered

text: porous

text: dust

text: layer,

text: depends

text: on

text: its

text: transport

text: characteristics

text: (gas

text: cases,

text: the

text: maximum

text: gas

text: pressure

text: is

text: typically

text: reached

text: for

text: a

text: dust

text: permeability)

text: and

text: on

text: the

text: energy

text: supplied

text: to

text: the

text: region.

text: The

text: lat-

text: layer

text: thickness

text: between

text: two

text: and

text: ﬁve

text: aggregate

text: layers.

text: ter

text: depends

text: on

text: the

text: heliocentric

text: distance,

text: on

text: the

text: nucleus

text: albedo,

text: Figure

text: shows

text: that

text: the

text: deviation

text: from

text: the

text: thermophysical

text: on

text: the

text: thickness,

text: and

text: on

text: the

text: heat

text: conductivity

text: of

text: the

text: covering

text: model

text: to

text: the

text: approximation

text: of

text: Eq.

text: increases

text: with

text: increasing

text: dust

text: layer.

text: A

text: detailed

text: heat-conductivity

text: model

text: for

text: granular

text: ma-

text: heliocentric

text: distance.

text: This

text: can

text: be

text: explained

text: by

text: the

text: following

text: terials

text: in

text: vacuum

text: was

text: presented

text: by

text: Gundlach

text: Blum

text: considerations.

text: For

text: reasonable

text: dust-aggregate

text: sizes

text: and

text: surface

text: and

text: Gundlach

text: Blum

text: Together

text: with

text: the

text: available

text: en-

text: temperatures,

text: the

text: heat

text: conductivity

text: is

text: dominated

text: by

text: radiative

text: ergy

text: for

text: the

text: sublimation

text: process,

text: the

text: permeability

text: of

text: the

text: cover-

text: transport

text: and,

text: thus,

text: increases

text: strongly

text: with

text: increasing

text: tempera-

text: ing

text: dust

text: layer

text: determines

text: the

text: pressure

text: build-up

text: at

text: the

text: depth

text: of

text: ture,

text: that

text: is,

text: with

text: decreasing

text: heliocentric

text: distance

text: (see

text: Gundlach

text: the

text: ice-dust

text: interface

text: (Gundlach

text: et

text: al.

text: Blum

text: et

text: al.

text: Blum

text: Gundlach

text: Blum

text: for

text: details).

text: Therefore,

text: In

text: the

text: following,

text: this

text: detailed

text: model

text: is

text: referred

text: to

text: as

text: the

text: the

text: fraction

text: of

text: absorbed

text: energy

text: that

text: is

text: transported

text: into

text: the

text: inte-

text: thermophysical

text: model.

text: rior

text: of

text: the

text: comet

text: nucleus

text: and,

text: thus,

text: used

text: to

text: evaporate

text: volatile

text: In

text: general,

text: the

text: derivation

text: of

text: the

text: gas

text: pressure

text: at

text: the

text: ice-

text: ices,

text: also

text: increases

text: with

text: decreasing

text: heliocentric

text: distance.

text: On

text: dust

text: interface

text: should

text: be

text: determined

text: from

text: full

text: consideration

text: of

text: the

text: other

text: hand,

text: for

text: increasing

text: heliocentric

text: distances,

text: the

text: relative

text: the

text: conservation

text: of

text: energy,

text: momentum,

text: and

text: mass

text: for

text: solid

text: and

text: importance

text: of

text: thermal

text: reradiation

text: of

text: the

text: surface

text: into

text: deep

text: space

text: gaseous

text: phases.

text: However,

text: such

text: a

text: detailed

text: consideration

text: is

text: far

text: increases

text: (see

text: Blum

text: et

text: al.

text: for

text: details).

text: beyond

text: the

text: scope

text: of

text: this

text: paper.

text: We

text: wish

text: to

text: simplify

text: the

text: physical

text: For

text: example,

text: the

text: smallest

text: aggregate

text: size

text: increases

text: from

text: model

text: as

text: much

text: as

text: possible

text: (keep

text: it

text: reasonable)

text: to

text: highlight

text: the

text: mm

text: to

text: mm

text: for

text: H

text: O

text: ice

text: activity

text: at

text: AU

text: if

text: the

text: thermophysi-

text: new

text: qualitative

text: results.

text: For

text: this

text: reason,

text: we

text: simpliﬁed

text: the

text: deriva-

text: cal

text: model

text: is

text: used

text: instead

text: of

text: the

text: approximation.

text: At

text: AU

text: and

text: for

text: tion

text: of

text: the

text: gas

text: pressure

text: at

text: the

text: ice-dust

text: interface

text: by

text: the

text: approxi-

text: H

text: O

text: ice

text: sublimation,

text: the

text: smallest

text: aggregate

text: size

text: changes

text: from

text: mation

text: that

text: the

text: incoming

text: energy

text: that

text: is

text: absorbed

text: by

text: the

text: nucleus

text: mm

text: (approximation)

text: to

text: mm

text: (thermophysical

text: model).

text: is

text: entirely

text: used

text: for

text: the

text: sublimation

text: of

text: the

text: volatiles

text: (i.e.,

text: thermal

text: The

text: calculations

text: shown

text: in

text: Fig.

text: were

text: only

text: performed

text: for

text: reradiation

text: of

text: the

text: comet

text: nucleus

text: and

text: energy

text: dissipation

text: by

text: its

text: one

text: aggregate

text: size

text: of

text: mm

text: because

text: the

text: systematic

text: simulations

text: core

text: are

text: neglected).

text: The

text: reasonableness

text: of

text: this

text: simpliﬁcation

text: is

text: illustrated

text: below.

text: With

text: this

text: assumption,

text: the

text: gas

text: pressure

text: at

text: the

text: showed

text: that

text: starting

text: from

text: an

text: aggregate

text: radius

text: of

text: µm,

text: the

text: vari-

text: ation

text: of

text: the

text: aggregate

text: size

text: does

text: not

text: considerably

text: inﬂuence

text: the

text: ice-dust

text: interface

text: resulting

text: pressure

text: at

text: the

text: ice-dust

text: interface

text: (see

text: Fig.

text: With

text: the

text: knowledge

text: of

text: the

text: gas

text: pressure

text: at

text: the

text: ice-dust

text: inter-

text: p

text: A

text: IE

text: aaEh

text: Λ1

text: π

text: kmTice

text: psirzeesstuhraet

text: Strictly

text: speaking,

text: the

text: assumption

text: that

text: all

text: absorbed

text: energy

text: is

text: where

text: A

text: is

text: the

text: Bond

text: albedo

text: of

text: the

text: surface

text: material,

text: I

text: is

text: the

text: used

text: by

text: the

text: sublimation

text: of

text: the

text: ice

text: gives

text: us

text: the

text: highest

text: eﬀective

text: E

text: solar

text: constant,

text: a

text: is

text: the

text: distance

text: of

text: the

text: Earth

text: to

text: the

text: Sun,

text: a

text: is

text: sublimation

text: rate

text: (i.e.,

text: highest

text: mass

text: loss

text: per

text: second)

text: and

text: not

text: pres-

text: E

text: h

text: the

text: heliocentric

text: distance

text: of

text: the

text: comet,

text: Λ

text: is

text: the

text: latent

text: heat

text: of

text: the

text: sure.

text: However,

text: numerical

text: tests

text: agree

text: with

text: the

text: values

text: retrieved

text: sublimating

text: ice,

text: k

text: is

text: the

text: Boltzmann

text: constant,

text: T

text: is

text: the

text: tempera-

text: from

text: Eq.

text: (see

text: Fig.

text: Considering

text: the

text: thermal

text: emission

text: in

text: ice

text: ture

text: of

text: the

text: evaporating

text: ice,

text: and

text: m

text: is

text: the

text: mass

text: of

text: the

text: evaporating

text: the

text: energy

text: budget

text: leads

text: to

text: a

text: reduction

text: of

text: the

text: eﬀective

text: loss

text: mass.

text: molecules.

text: The

text: role

text: of

text: this

text: dissipation

text: channel

text: was

text: discussed

text: by

text: Blum

text: et

text: al.

text: To

text: illustrate

text: the

text: plausibility

text: of

text: this

text: simpliﬁcation,

text: the

text: results

text: where

text: it

text: was

text: shown

text: that

text: this

text: eﬀect

text: is

text: weak

text: close

text: to

text: the

text: of

text: Eq.

text: are

text: compared

text: with

text: the

text: corresponding

text: pressure

text: obtained

text: Sun

text: and

text: increases

text: with

text: heliocentric

text: distance.

text: Because

text: the

text: tensile

text: from

text: the

text: sophisticated

text: thermophysical

text: model

text: for

text: H

text: O

text: ice

text: (latent

text: strength

text: of

text: the

text: covering

text: aggregate

text: layer

text: is

text: a

text: decreasing

text: function

text: heat

text: of

text: sublimation:

text: Λ

text: J

text: kg

text: Orosei

text: et

text: al.

text: of

text: aggregate

text: size

text: (see

text: Eq.

text: the

text: larger

text: grains

text: can

text: be

text: lifted

text: eas-

text: at

text: the

text: ice-dust

text: interface

text: for

text: diﬀerent

text: thicknesses

text: of

text: the

text: covering

text: ily

text: and

text: their

text: size

text: is

text: only

text: restricted

text: by

text: the

text: cometary

text: gravity.

text: In

text: Article

text: number,

text: page

text: of

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 5 Commutativity: Proof of Theorems 7(b,c) and 8 ∼ From now on we assume that (ρ, ) is weakly commutative. Therefore, for any walk τ = ∼ → → (cid:54) (cid:48) → (cid:48) → f g g f . . . σ σ σ . . . with f = g there exists another walk τ = . . . σ σ σ . . . obtained from 1 2 3 1 2 3 → → f g τ by applying the SWAP operator to the subwalk σ1 σ2 σ3. Such operation will be called a valid swap applied to τ. A mapping Φ on a set of walks that works by applying some sequence of (cid:48) valid swaps will be called a swapping mapping. Note that if τ = Φ(τ) then the ﬁrst and the last (cid:48) • (cid:48) • (cid:48) ∼ states of τ coincide with that of τ, and λ (cid:48) = λ where τ = W , τ = W . Furthermore, if (ρ, ) is (cid:48) W W strongly commutative then p(τ ) = p(τ). ∈ We now deal with the case when Λ is an arbitrary deterministic strategy, and so walks τ Bad(t) are not necessarily π-stable. Our approach will be to construct a bijective swapping mapping Φ ∈ that sends walks τ Bad(t) to some canonical walks, namely either to π-stable walks (which will work only in the atomic case) or to the reverse of such walks (which will work in the general case). 5.1 Proof of Theorem 7(b) ∼ In this section we assume that (ρ, ) is atomic. This gives the following observation. → → Proposition 17 ([1]). Walk τ = σ w1 σ . . . σ wt σ can be uniquely reconstructed from the 1 2 t t+1 sequence of ﬂaws w . . . w and the ﬁnal state σ . 1 t t+1 Proof. By atomicity, state σ can be uniquely reconstructed from the ﬂaw w and the state σ . i − i i+1 Applying this argument for i = t, t 1, . . . , 1 gives the claim. The proposition allows us to write walks more compactly as τ = w . . . w [σ ]. Also, Lemma 10 1 t t+1 gives for a walk τ = W [σ ] that t+1 ≤ · · p(τ) γinit λ ω(σ ) (10) W t+1 In Section 2 we will prove the following result. ∼ Theorem 18. Suppose that (ρ, ) is atomic and weakly commutative. There exists a set of π-stable → walks Badπ(t) and a swapping mapping Φ : Bad(t) Badπ(t) which is a bijection. We can now prove Theorem 7(b): (cid:88) (cid:88) ≥ (≤a) · · P r[#steps t] = (cid:88)p(τ) γinit λ ω(σ(cid:88)) (cid:88) (cid:88) W ∈ ∈ τ Bad(t) τ=W[σ] Bad(t) · · ≤ · · (=b) (cid:88) γinit (cid:88)λ ω(σ) γinit (cid:88) λ ω(σ) W W ∈ ∈ ∈ ∈ τ=W[σ] Badπ(t) R Indinit W Stabπ(R,t) σ Ω ≤ · ≤ · · − γinit λ γinit µ(R) θt = θt T W ∈ ∈ ∈ R Indinit W Stabπ(R,t) R Indinit where in (a) we used eq. (10), (b) follows from Theorem 18, and the rest is similar to the derivation in Section 2. 12 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: section

text: Commutativity:

text: Proof

text: of

text: Theorems

text: and

text: From

text: now

text: on

text: we

text: assume

text: that

text: (ρ,

text: is

text: weakly

text: commutative.

text: Therefore,

text: for

text: any

text: walk

text: τ

font: default

text: f

text: g

text: g

text: f

text: σ

text: σ

text: σ

text: with

text: f

text: g

text: there

text: exists

text: another

text: walk

text: τ

text: σ

text: σ

text: σ

text: obtained

text: from

text: f

text: g

text: τ

text: by

text: applying

text: the

text: SWAP

text: operator

text: to

text: the

text: subwalk

text: σ1

text: σ2

text: Such

text: operation

text: will

text: be

text: called

text: a

text: valid

text: swap

text: applied

text: to

text: τ.

text: A

text: mapping

text: Φ

text: on

text: a

text: set

text: of

text: walks

text: that

text: works

text: by

text: applying

text: some

text: sequence

text: of

text: valid

text: swaps

text: will

text: be

text: called

text: a

text: swapping

text: mapping.

text: Note

text: that

text: if

text: τ

text: Φ(τ)

text: then

text: the

text: ﬁrst

text: and

text: the

text: last

text: states

text: of

text: τ

text: coincide

text: with

text: that

text: of

text: τ,

text: and

text: λ

text: λ

text: where

text: τ

text: W

text: τ

text: W

text: Furthermore,

text: if

text: (ρ,

text: is

text: W

text: W

text: strongly

text: commutative

text: then

text: p(τ

text: p(τ).

text: We

text: now

text: deal

text: with

text: the

text: case

text: when

text: Λ

text: is

text: an

text: arbitrary

text: deterministic

text: strategy,

text: and

text: so

text: walks

text: τ

text: Bad(t)

text: are

text: not

text: necessarily

text: π-stable.

text: Our

text: approach

text: will

text: be

text: to

text: construct

text: a

text: bijective

text: swapping

text: mapping

text: Φ

text: that

text: sends

text: walks

text: τ

text: Bad(t)

text: to

text: some

text: canonical

text: walks,

text: namely

text: either

text: to

text: π-stable

text: walks

text: (which

text: will

text: work

text: only

text: in

text: the

text: atomic

text: case)

text: or

text: to

text: the

text: reverse

text: of

text: such

text: walks

text: (which

text: will

text: work

text: in

text: the

text: general

text: case).

text: Proof

text: of

text: Theorem

text: In

text: this

text: section

text: we

text: assume

text: that

text: (ρ,

text: is

text: atomic.

text: This

text: gives

text: the

text: following

text: observation.

text: Proposition

text: Walk

text: τ

text: σ

text: σ

text: σ

text: wt

text: σ

text: can

text: be

text: uniquely

text: reconstructed

text: from

text: the

text: t

text: sequence

text: of

text: ﬂaws

text: w

text: w

text: and

text: the

text: ﬁnal

text: state

text: σ

text: t

text: Proof.

text: By

text: atomicity,

text: state

text: σ

text: can

text: be

text: uniquely

text: reconstructed

text: from

text: the

text: ﬂaw

text: w

text: and

text: the

text: state

text: σ

text: i

text: i

text: Applying

text: this

text: argument

text: for

text: i

text: t,

text: t

text: gives

text: the

text: claim.

text: The

text: proposition

text: allows

text: us

text: to

text: write

text: walks

text: more

text: compactly

text: as

text: τ

text: w

text: w

text: [σ

text: Also,

text: Lemma

text: t

text: gives

text: for

text: a

text: walk

text: τ

text: W

text: [σ

text: that

text: p(τ)

text: γinit

text: λ

text: ω(σ

text: W

text: In

text: Section

text: we

text: will

text: prove

text: the

text: following

text: result.

text: Theorem

text: Suppose

text: that

text: (ρ,

text: is

text: atomic

text: and

text: weakly

text: commutative.

text: There

text: exists

text: a

text: set

text: of

text: π-stable

text: walks

text: Badπ(t)

text: and

text: a

text: swapping

text: mapping

text: Φ

text: Bad(t)

text: Badπ(t)

text: which

text: is

text: a

text: bijection.

text: We

text: can

text: now

text: prove

text: Theorem

text: (≤a)

text: P

text: r[#steps

text: t]

text: γinit

text: λ

text: W

text: τ

text: Bad(t)

text: τ=W[σ]

text: Bad(t)

text: (=b)

text: γinit

text: ω(σ)

text: γinit

text: λ

text: ω(σ)

text: W

text: W

text: τ=W[σ]

text: Badπ(t)

text: R

text: Indinit

text: W

text: Stabπ(R,t)

text: σ

text: Ω

text: γinit

text: λ

text: γinit

text: µ(R)

text: θt

text: θt

text: T

text: W

text: R

text: Indinit

text: W

text: Stabπ(R,t)

text: R

text: Indinit

text: where

text: in

text: (a)

text: we

text: used

text: eq.

text: (b)

text: follows

text: from

text: Theorem

text: and

text: the

text: rest

text: is

text: similar

text: to

text: the

text: derivation

text: in

text: Section

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: − → ∈ Y w deterministic strategy, the ﬂaw w in the expression τ = τˆ σ must be the same for all τ . Y { − → | ∈ } ⊆ ⊆ w Thus, = τˆ σ σ Y for some set of ﬂaws Y F . In fact, we must have Y A(w, σˆ) − where σˆ is the ﬁnal state of τˆ . X − X − Y ∪ { −} (cid:34) (cid:35) Deﬁne (cid:88)= ( (cid:88)) τˆ . W(cid:88)e have (cid:88) − − − − · | − ≤ p(τ) p(τ) = p(τ) p(τˆ ) = p(τˆ ) ρ(σ w, σˆ) 1 0 ∈X ∈X− ∈Y ∈ τ τ τ σ Y X − X − It is straightforward to check that set is valid, and W is a preﬁx of every walk in . Using X − X the induction hypothesis for and the inequality above gives the claim for . Consider executions of Algorithm 2 consisting of at least s rounds. For each such execution let − τ be the walk containing ﬂaws addressed in the ﬁrst s 1 rounds and the ﬁrst ﬂaw addressed in round s. Let BadPar(s) be the set of such walks τ. • We say that a word U ∼= u1 . . . us is∈a c−hain of a walk τ = w1 . . . wt if U is a subsequence of the sequence w . . . w and u = u for i [s 1]. 1 t i i+1 ∈ Proposition 21. (a) For each τ BadPar(s) the length of a longest chain in τ equals s. (b) Set BadPar(s) is valid. Proof. Part (a) follows directly from Proposition 15 and the deﬁnition of a stable walk. Let us prove (b). By construction, all walks in BadPar(s) follow the same deterministic strategy used in (cid:48) ∈ (cid:48) ∈ Algorithm 2. Now consider a walk τ BadPar(s). By the deﬁnition of τ BadPar(s), any proper (cid:48) − preﬁx τ of τ corresponds to an execution of Algorithm 2 with at most r 1 rounds, and so the − ∈ length of a longest chain in τ is at most r 1. Thus, τ / BadPar(s). ∈ ∈ For a ﬂaw f F let BadParf(s) be the set of walks τ BadPar(s) that contain a chain of length X s that ends with f. We now apply Theorem 19 with the set f = BadParf(s). Since every walk ∈ ∈ X τ BadParf(s) has a chain of length s that ends with f, so does ev|ery |w≥alk τ πf (ap∈pXlying a swapping mapping to τ does not aﬀect the chain). This (cid:83)means that W f s for each τ f. ∈ { } (cid:104) (cid:105) ∈ X τ π For a word W Stabπ( f , s) let W f be theXset of walks τ πf t(cid:104)hat(cid:105)satisfy REV[Wτf] = W . By Theorem 19 and the argument above we have f = ∈ { } W f. We can thus write (cid:88) (cid:88) (cid:88) (cid:88)π W Stabπ( f (cid:88),s) p(τ) (=a) p(τ) = p(τ) (≤b) γinit · λ (≤c) γinit · µ · θs W f ∈ ∈X ∈ { } ∈(cid:104) (cid:105) ∈ { } τ BadParf(s) τ πf W Stabπ( f ,s) τ W f W Stabπ( f ,s) (cid:83) ∼ where in (a) we used bijectiveness of Φf and strong commutativity of (ρ, ), in (b) we used The- (cid:104) (cid:105) orem 20 (and the fact that W f is a valid set by Theorem 19(b)), and in (c) we used Theorem 14. By Proposition 21, BadPar(s)(cid:88)= ∈ BadPar(cid:88)f(s), th(cid:88)erefore (cid:88) f F ≥ ≤ ≤ ≤ · · − P r[#rounds s] p(τ) p(τ) γinit µ θs = θs T f ∈ ∈ ∈ ∈ τ BadPar(s) f F τ BadParf(s) f F where T is given by the expression in (6). 14 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Y

text: w

text: deterministic

text: strategy,

text: the

text: ﬂaw

text: w

text: in

text: the

text: expression

text: τ

text: τˆ

text: σ

text: must

text: be

text: the

text: same

text: for

text: all

text: τ

text: Y

text: w

text: Thus,

text: τˆ

text: σ

text: σ

text: Y

text: for

text: some

text: set

text: of

text: ﬂaws

text: Y

text: F

text: In

text: fact,

text: we

text: must

text: have

text: Y

text: A(w,

text: σˆ)

text: where

text: σˆ

text: is

text: the

text: ﬁnal

text: state

text: of

text: τˆ

text: X

text: X

text: Y

text: Deﬁne

text: τˆ

text: have

text: p(τ)

text: p(τ)

text: p(τ)

text: p(τˆ

text: p(τˆ

text: ρ(σ

text: w,

text: σˆ)

text: ∈X

text: ∈X−

text: ∈Y

text: τ

text: τ

text: τ

text: σ

text: Y

text: X

text: X

text: It

text: is

text: straightforward

text: to

text: check

text: that

text: set

text: is

text: valid,

text: and

text: W

text: is

text: a

text: preﬁx

text: of

text: every

text: walk

text: in

text: Using

text: X

text: X

text: the

text: induction

text: hypothesis

text: for

text: and

text: the

text: inequality

text: above

text: gives

text: the

text: claim

text: for

text: Consider

text: executions

text: of

text: Algorithm

text: consisting

text: of

text: at

text: least

text: s

text: rounds.

text: For

text: each

text: such

text: execution

text: let

text: τ

text: be

text: the

text: walk

text: containing

text: ﬂaws

text: addressed

text: in

text: the

text: ﬁrst

text: s

text: rounds

text: and

text: the

text: ﬁrst

text: ﬂaw

text: addressed

text: in

text: round

text: s.

text: Let

text: BadPar(s)

text: be

text: the

text: set

text: of

text: such

text: walks

text: τ.

text: We

text: say

text: that

text: a

text: word

text: U

text: us

text: is∈a

text: c−hain

text: of

text: a

text: walk

text: τ

text: wt

text: if

text: U

text: is

text: a

text: subsequence

text: of

text: the

text: sequence

text: w

text: w

text: and

text: u

text: u

text: for

text: i

text: [s

text: t

text: i

text: Proposition

text: (a)

text: For

text: each

text: τ

text: BadPar(s)

text: the

text: length

text: of

text: a

text: longest

text: chain

text: in

text: τ

text: equals

text: s.

text: (b)

text: Set

text: BadPar(s)

text: is

text: valid.

text: Proof.

text: Part

text: (a)

text: follows

text: directly

text: from

text: Proposition

text: and

text: the

text: deﬁnition

text: of

text: a

text: stable

text: walk.

text: Let

text: us

text: prove

text: (b).

text: By

text: construction,

text: all

text: walks

text: in

text: BadPar(s)

text: follow

text: the

text: same

text: deterministic

text: strategy

text: used

text: in

text: Algorithm

text: Now

text: consider

text: a

text: walk

text: τ

text: BadPar(s).

text: By

text: the

text: deﬁnition

text: of

text: τ

text: BadPar(s),

text: any

text: proper

text: preﬁx

text: τ

text: of

text: τ

text: corresponds

text: to

text: an

text: execution

text: of

text: Algorithm

text: with

text: at

text: most

text: r

text: rounds,

text: and

text: so

text: the

text: length

text: of

text: a

text: longest

text: chain

text: in

text: τ

text: is

text: at

text: most

text: r

text: Thus,

text: τ

text: BadPar(s).

text: For

text: a

text: ﬂaw

text: f

text: F

text: let

text: BadParf(s)

text: be

text: the

text: set

text: of

text: walks

text: τ

text: BadPar(s)

text: that

text: contain

text: a

text: chain

text: of

text: length

text: X

text: s

text: that

text: ends

text: with

text: f.

text: We

text: now

text: apply

text: Theorem

text: with

text: the

text: set

text: f

text: BadParf(s).

text: Since

text: every

text: walk

text: X

text: τ

text: BadParf(s)

text: has

text: a

text: chain

text: of

text: length

text: s

text: that

text: ends

text: with

text: f,

text: so

text: does

text: ev|ery

text: |w≥alk

text: τ

text: πf

text: (ap∈pXlying

text: a

text: swapping

text: mapping

text: to

text: τ

text: does

text: not

text: aﬀect

text: the

text: chain).

text: This

text: that

text: W

text: f

text: s

text: for

text: each

text: τ

text: f.

text: X

text: τ

text: π

text: For

text: a

text: word

text: W

text: Stabπ(

text: f

text: s)

text: let

text: W

text: f

text: be

text: theXset

text: of

text: walks

text: τ

text: πf

text: REV[Wτf]

text: W

text: By

text: Theorem

text: and

text: the

text: argument

text: above

text: we

text: have

text: f

text: W

text: f.

text: We

text: can

text: thus

text: write

text: W

text: Stabπ(

text: f

text: p(τ)

text: (=a)

text: p(τ)

text: p(τ)

text: (≤b)

text: γinit

text: λ

text: (≤c)

text: γinit

text: µ

text: θs

text: W

text: f

text: ∈X

text: τ

text: BadParf(s)

text: τ

text: πf

text: W

text: Stabπ(

text: f

text: ,s)

text: τ

text: W

text: f

text: W

text: Stabπ(

text: f

text: ,s)

text: where

text: in

text: (a)

text: we

text: used

text: bijectiveness

text: of

text: Φf

text: and

text: strong

text: commutativity

text: of

text: (ρ,

text: in

text: (b)

text: we

text: used

text: The-

text: orem

text: (and

text: the

text: fact

text: that

text: W

text: f

text: is

text: a

text: valid

text: set

text: by

text: Theorem

text: and

text: in

text: (c)

text: we

text: used

text: Theorem

text: By

text: Proposition

text: f

text: F

text: P

text: r[#rounds

text: s]

text: p(τ)

text: p(τ)

text: γinit

text: µ

text: θs

text: θs

text: T

text: f

text: τ

text: BadPar(s)

text: f

text: F

text: τ

text: BadParf(s)

text: f

text: F

text: where

text: T

text: is

text: given

text: by

text: the

text: expression

text: in

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 5.5 Proof of Theorem 18 (swapping mapping for the atomic case) We can extend a “valid swap” oper∼ation to words in a natural way: it is a transformation of (cid:55)→ (cid:54) ≡ (cid:48) (cid:48) the form . . . fg . . . . . . gf . . . where f = g. We will write W W if W can be obtained from W ≡ via a sequence of valid swaps. Clearly, “ ” is an equivalence relation. It can be seen that a walk (cid:48) (cid:48) ≡ (cid:48) τ = W [σ] can be transformed to a walk τ = W [σ] if and only if W W . In this case we will (cid:48) ≡ ≡ write τ τ; again, “ ” is an equivalence relation on the set of walks. Lemma 22. For any word W there exists a sequence of valid swaps that transforms W to a π-stable word. Proof. It suﬃces to show that W can be transformed to a stable word via valid swaps. (Trans- forming a stable word W to a π-stable word is straightforward: if W = W . . . W is the partition 1 s described in Deﬁnition 13 then we simply need to apply swaps inside each word W to “sort” it (cid:22) r according to ; any such swap will be valid by the property of W ). π r Let W = wˆ . . . wˆ . We will prove by induction on i = 1, . . . , t that W can be transformed via 1 t (cid:48) valid swaps to a word W = w . . . w . . . w such that the preﬁx w . . . w is a stable word. The base 1 i t − 1 i ∈ case i = 1 is trivial. Suppose the claim holds for i 1, and let us show it for i [2, t]. (cid:48) By the induction hypothesis, W can be transformed to a word W = w . . . w − f . . . w such that 1 i 1 t w1 . . . wi−1 is a stable word. Let w1 . . . wi−1 = W1 . . . Ws be the corresponding p∼artition described in Deﬁnition 13. Let W be the rightmost word that contains a ﬂaw g with f = g. (If such word r ∈ (cid:48) doesn’t exist then we set r = 0; thus, r [0, s]). If r = s then we can leave the word W as it is - it satisﬁes the induction hypothesis for i. ∈ − Suppose that r [0, s 1]. Then we repeatedly swap f with the left neighbor, stopping when f gets between words W and W (or at the ﬁrst position, if r = 0). By the deﬁnition of r, these r r+1 are valid swaps. The new word now satisﬁes the induction hypothesis for i (ﬂaw f will be assigned to word W ). r+1 ∈ The lemma means that there exists a swapping mapping Φ that sends any walk τ = W [σ] (cid:48) (cid:48) Bad(t) to a π-stable walk τ = W [σ]. Next, we will show that any such mapping is injective on Bad(t). (cid:48) ≡ (cid:48) Lemma 23. Suppose that walks τ, τ follow the same deterministic strategy and τ τ . Then (cid:48) τ = τ . | | | (cid:48)| Proof. We use induction on the length of τ. The base case is trivial: if τ = τ = 0 then condition ≡ (cid:48) (cid:48) τ τ implies that τ = τ = [σ] for some state σ. ≡ (cid:48) (cid:48) Suppose that τ = fW [σ]. Condition τ τ means that τ and τ start at the same state. (cid:48) (cid:48) Therefore, since τ and τ follow the same deterministic strategy, the ﬁrst ﬂaw addressed in τ is (cid:48) (cid:48) (cid:48) the same as in τ. Thus, τ = fW [σ]. Clearly, walks W [σ] and W [σ] follow the same deterministic ≡ (cid:48) (cid:48) strategy. We will show below that W [σ] W [σ]; this will mean that W [σ] = W [σ] by the induction hypothesis, thus giving the desired result. ≡ (cid:48) ≡ (cid:48) We need to show that W W . We know that fW fW , therefore there exists a sequence (cid:48) of words U(1), . . . , U(k) with U(1) = fW , U(k) = fW such that U(i+1) is obtained from U(i) via a single valid swap operation. Let V (i) be the word obtained from U(i) by moving the ﬁrst occurence ∈ of ﬂaw f in U(i) to the ﬁrst position. Thus, for each i [k] we have V (i) = fW (k) for some word W (k). It can be seen that either V (i+1) = V (i) (if the valid swap operation applied to U(i) involved the ﬁrst occurence of f) or V (i+1) is obtained from V (i) via a valid swap (otherwise). Thus, either W (i+1) = W (i) or W (i+1) is obtained from W (i) via a valid swap. It remains to notice that (cid:48) W (1) = W and W (k) = W . 15 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof

text: of

text: Theorem

text: (swapping

text: mapping

text: for

text: the

text: atomic

text: case)

text: We

text: can

text: extend

text: a

text: “valid

text: swap”

text: oper∼ation

text: to

text: words

text: in

text: a

text: natural

text: way:

text: it

text: is

text: a

text: transformation

text: of

text: the

text: form

text: fg

text: gf

text: where

text: f

text: g.

text: We

text: will

text: write

text: W

text: W

text: if

text: W

text: can

text: be

text: obtained

text: from

text: W

text: via

text: a

text: sequence

text: of

text: valid

text: swaps.

text: Clearly,

text: is

text: an

text: equivalence

text: relation.

text: It

text: can

text: be

text: seen

text: that

text: a

text: walk

text: τ

text: W

text: [σ]

text: can

text: be

text: transformed

text: to

text: a

text: walk

text: τ

text: W

text: [σ]

text: if

text: and

text: only

text: if

text: W

text: W

text: In

text: this

text: case

text: we

text: will

text: write

text: τ

text: τ;

text: again,

text: is

text: an

text: equivalence

text: relation

text: on

text: the

text: set

text: of

text: walks.

text: Lemma

text: For

text: any

text: word

text: W

text: there

text: exists

text: a

text: sequence

text: of

text: valid

text: swaps

text: that

text: transforms

text: W

text: to

text: a

text: π-stable

text: word.

text: Proof.

text: It

text: suﬃces

text: to

text: show

text: that

text: W

text: can

text: be

text: transformed

text: to

text: a

text: stable

text: word

text: via

text: valid

text: swaps.

text: (Trans-

text: forming

text: a

text: stable

text: word

text: W

text: to

text: a

text: π-stable

text: word

text: is

text: straightforward:

text: if

text: W

text: W

text: W

text: is

text: the

text: partition

text: s

text: described

text: in

text: Deﬁnition

text: then

text: we

text: simply

text: need

text: to

text: apply

text: swaps

text: inside

text: each

text: word

text: W

text: to

text: “sort”

text: it

text: r

text: according

text: to

text: any

text: such

text: swap

text: will

text: be

text: valid

text: by

text: the

text: property

text: of

text: W

text: π

text: r

text: Let

text: W

text: wˆ

text: wˆ

text: We

text: will

text: prove

text: by

text: induction

text: on

text: i

text: t

text: that

text: W

text: can

text: be

text: transformed

text: via

text: t

text: valid

text: swaps

text: to

text: a

text: word

text: W

text: w

text: w

text: w

text: such

text: that

text: the

text: preﬁx

text: w

text: w

text: is

text: a

text: stable

text: word.

text: The

text: base

text: i

text: t

text: i

text: case

text: i

text: is

text: trivial.

text: Suppose

text: the

text: claim

text: holds

text: for

text: i

text: and

text: let

text: us

text: show

text: it

text: for

text: i

text: t].

text: By

text: the

text: induction

text: hypothesis,

text: W

text: can

text: be

text: transformed

text: to

text: a

text: word

text: W

text: w

text: w

text: f

text: w

text: such

text: that

text: i

text: t

text: is

text: a

text: stable

text: word.

text: Let

text: Ws

text: be

text: the

text: corresponding

text: p∼artition

text: described

text: in

text: Deﬁnition

text: Let

text: W

text: be

text: the

text: rightmost

text: word

text: that

text: contains

text: a

text: ﬂaw

text: g

text: with

text: f

text: g.

text: (If

text: such

text: word

text: r

text: doesn’t

text: exist

text: then

text: we

text: set

text: r

text: thus,

text: r

text: s]).

text: If

text: r

text: s

text: then

text: we

text: can

text: leave

text: the

text: word

text: W

text: as

text: it

text: is

text: it

text: satisﬁes

text: the

text: induction

text: hypothesis

text: for

text: i.

text: Suppose

text: that

text: r

text: s

text: Then

text: we

text: repeatedly

text: swap

text: f

text: with

text: the

text: left

text: neighbor,

text: stopping

text: when

text: f

text: gets

text: between

text: words

text: W

text: and

text: W

text: (or

text: at

text: the

text: ﬁrst

text: position,

text: if

text: r

text: By

text: the

text: deﬁnition

text: of

text: r,

text: these

text: r

text: are

text: valid

text: swaps.

text: The

text: new

text: word

text: now

text: satisﬁes

text: the

text: induction

text: hypothesis

text: for

text: i

text: (ﬂaw

text: f

text: will

text: be

text: assigned

text: to

text: word

text: W

text: The

text: lemma

text: means

text: that

text: there

text: exists

text: a

text: swapping

text: mapping

text: Φ

text: that

text: sends

text: any

text: walk

text: τ

text: W

text: [σ]

text: Bad(t)

text: to

text: a

text: π-stable

text: walk

text: τ

text: W

text: [σ].

text: Next,

text: we

text: will

text: show

text: that

text: any

text: such

text: mapping

text: is

text: injective

text: on

text: Bad(t).

text: Lemma

text: Suppose

text: that

text: walks

text: τ,

text: τ

text: follow

text: the

text: same

text: deterministic

text: strategy

text: and

text: τ

text: τ

text: Then

text: τ

text: τ

text: Proof.

text: We

text: use

text: induction

text: on

text: the

text: length

text: of

text: τ.

text: The

text: base

text: case

text: is

text: trivial:

text: if

text: τ

text: τ

text: then

text: condition

text: τ

text: τ

text: implies

text: that

text: τ

text: τ

text: [σ]

text: for

text: some

text: state

text: σ.

text: Suppose

text: that

text: τ

text: fW

text: [σ].

text: Condition

text: τ

text: τ

text: means

text: that

text: τ

text: and

text: τ

text: start

text: at

text: the

text: same

text: state.

text: Therefore,

text: since

text: τ

text: and

text: τ

text: follow

text: the

text: same

text: deterministic

text: strategy,

text: the

text: ﬁrst

text: ﬂaw

text: addressed

text: in

text: τ

text: is

text: the

text: same

text: as

text: in

text: τ.

text: Thus,

text: τ

text: fW

text: [σ].

text: Clearly,

text: walks

text: W

text: [σ]

text: and

text: W

text: [σ]

text: follow

text: the

text: same

text: deterministic

text: strategy.

text: We

text: will

text: show

text: below

text: that

text: W

text: [σ]

text: W

text: [σ];

text: this

text: will

text: mean

text: that

text: W

text: [σ]

text: W

text: [σ]

text: by

text: the

text: induction

text: hypothesis,

text: thus

text: giving

text: the

text: desired

text: result.

text: We

text: need

text: to

text: show

text: that

text: W

text: W

text: We

text: know

text: that

text: fW

text: fW

text: therefore

text: there

text: exists

text: a

text: sequence

text: of

text: words

text: U(k)

text: with

text: fW

text: U(k)

text: fW

text: such

text: that

text: is

text: obtained

text: from

text: U(i)

text: via

text: a

text: single

text: valid

text: swap

text: operation.

text: Let

text: V

text: (i)

text: be

text: the

text: word

text: obtained

text: from

text: U(i)

text: by

text: moving

text: the

text: ﬁrst

text: occurence

text: of

text: ﬂaw

text: f

text: in

text: U(i)

text: to

text: the

text: ﬁrst

text: position.

text: Thus,

text: for

text: each

text: i

text: [k]

text: we

text: have

text: V

text: (i)

text: fW

text: (k)

text: for

text: some

text: word

text: W

text: (k).

text: It

text: can

text: be

text: seen

text: that

text: either

text: V

text: V

text: (i)

text: (if

text: the

text: valid

text: swap

text: operation

text: applied

text: to

text: U(i)

text: involved

text: the

text: ﬁrst

text: occurence

text: of

text: f)

text: or

text: V

text: is

text: obtained

text: from

text: V

text: (i)

text: via

text: a

text: valid

text: swap

text: (otherwise).

text: Thus,

text: either

text: W

text: W

text: (i)

text: or

text: W

text: is

text: obtained

text: from

text: W

text: (i)

text: via

text: a

text: valid

text: swap.

text: It

text: remains

text: to

text: notice

text: that

text: W

text: W

text: and

text: W

text: (k)

text: W

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Deﬁnition 26. Consider a walk τ containing fˆ. A pair (f, g) of named ﬂaws is called a swappable • (cid:54)∼ pair in τ if it can be swapped in τ (i.e. τ = . . . fg . . . and f = g) and either ∈ − × (i) (f, g) (V W ) W , or ∈ τ × τ τ (ii) (f, g) Wτ Wτ and their order in Stabπ(τ) is diﬀerent: Stabπ(τ) = . . . g . . . f . . .. The position of the rightmost swappable pair in τ will be denoted as k(τ), where the position of (f, g) in τ is the number of named ﬂaws that precede g in τ. If τ does not contain a swappable pair ∈ | | − then k(τ) = 0. Thus, k(τ) [0, τ 1]. It can be seen that the procedure of repeatedly applying swaps to swappable pairs in τ must (cid:0) (cid:1) terminate. Indeed, swapping a pair of the form (i) moves a named ﬂaw in W to the left, which τ can happen only a ﬁnite number of times. Similarly, swapping a pair of the form (ii) decreases the { } ∈ number of pairs f, g Wτ whose relative order in W is not consistent with the relative order 2 τ in Stabπ(τ), which again can happen only a ﬁnite number of times. (Note, swaps of the other type do not aﬀect these arguments). • Lemma 27. Consider a walk τ = AU containing fˆ where A, U some words, and there are no swappable pairs inside U. Then U = BC where sequence B is a subsequence of Stabπ(τ), and C does not contain named ﬂaws from W . | | • τ • In particular, if A = 0 and τ = U does not contain a swappable pair then τ = Stabπ(τ)C. Proof. Let u , . . . , u be the named ﬂaws from W that occur in U (listed in the order of their 1 m τ appearan∈ce in U). We c∈laim that u1 . . . um is a preﬁx of U∈. Indeed, suppo(cid:54)∼se not, then U = . . . fui . . . where f / W and u W . This means that (f, u ) / E , and so f = u . But then (f, u ) is a τ i τ i τ i i swappable pair in U - a contradiction. • We obtained a decomposition τ = ABC where B = u . . . u . It remains to show that B is a 1 m ∈ − subsequence of Stabπ(τ). For that it suﬃces to prove that for any i [m 1] the relative order of ui and ui+∼1 in B is the same as in Stabπ(τ). Suppose not, i.e. Stabπ(τ) = . . . ui+1 . . . ui . . .. We must have u = u (otherwise (u , u ) would be a swappable pair in τ, contradicting the assumption). i i+1 ∈ i i+1 Therefore, (u , u ) E , implying that d (u ) > d (u ). Inspecting Deﬁnition 24, we conclude i i+1 τ τ i τ i+1 that ui should be to the left of ui+1 in Stabπ(τ). We obtained a contradiction. Results so far can be used to obtain a mapping Φfˆ and set X fˆ = Φfˆ(X fˆ) that satisfy condition π (a) of Theorem 19. To satisfy bijectiveness and condition (b), we need to be careful with the order in which we apply swaps to swappable pairs. We will use the following algorithm. First, let X X = fˆ, and then for p = 0, 1, 2, . . . do the following: 0 • Let k = max ∈X k(τ). If k = 0 then terminate. τ p • ∈ X For each τ do the following: if k(τ) = k then swap the pair (f, g) at position k in τ, p X otherwise leave τ unchanged. Let be the new set of walks. p+1 X { ∈ X | } Let us ﬁx a word W (over named ﬂaws), and deﬁne p[W ] = τ p Stabπ(τ) = W for an ≥ X ⊆ X index p 0. Theorem 19 will follow from the following result (note that set [W ] fˆ is valid 0 by the assumption of the theorem). X X X X Lemma 28. If set [W ] is valid then so is [W ], and the mapping from [W ] to [W ] p p+1 p p+1 deﬁned by the algorithm above is injective. ◦ ◦ ∈ X Proof. First, let us prove injectiveness. Suppose that two distinct walks τ , τ¯ [W ] are trans- ∈ X ◦ ◦ p formed to the same walk τ [W ]. At least one of one walks τ , τ¯ must have changed. Assume p+1 17 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Deﬁnition

text: Consider

text: a

text: walk

text: τ

text: containing

text: fˆ.

text: A

text: pair

text: (f,

text: g)

text: of

text: named

text: ﬂaws

text: is

text: called

text: a

text: swappable

text: pair

text: in

text: τ

text: if

text: it

text: can

text: be

text: swapped

text: in

text: τ

text: (i.e.

text: τ

text: fg

text: and

text: f

text: g)

text: and

text: either

text: (i)

text: (f,

text: g)

text: (V

text: W

text: W

text: or

text: τ

text: τ

text: τ

text: (ii)

text: (f,

text: g)

text: Wτ

text: Wτ

text: and

text: their

text: order

text: in

text: Stabπ(τ)

text: is

text: diﬀerent:

text: Stabπ(τ)

text: g

text: f

text: The

text: position

text: of

text: the

text: rightmost

text: swappable

text: pair

text: in

text: τ

text: will

text: be

text: denoted

text: as

text: k(τ),

text: where

text: the

text: position

text: of

text: (f,

text: g)

text: in

text: τ

text: is

text: the

text: number

text: of

text: named

text: ﬂaws

text: that

text: precede

text: g

text: in

text: τ.

text: If

text: τ

text: does

text: not

text: contain

text: a

text: swappable

text: pair

text: then

text: k(τ)

text: Thus,

text: k(τ)

text: τ

text: It

text: can

text: be

text: seen

text: that

text: the

text: procedure

text: of

text: repeatedly

text: applying

text: swaps

text: to

text: swappable

text: pairs

text: in

text: τ

text: must

text: terminate.

text: Indeed,

text: swapping

text: a

text: pair

text: of

text: the

text: form

text: (i)

text: moves

text: a

text: named

text: ﬂaw

text: in

text: W

text: to

text: the

text: left,

text: which

text: τ

text: can

text: happen

text: only

text: a

text: ﬁnite

text: number

text: of

text: times.

text: Similarly,

text: swapping

text: a

text: pair

text: of

text: the

text: form

text: (ii)

text: decreases

text: the

text: number

text: of

text: pairs

text: f,

text: g

text: Wτ

text: whose

text: relative

text: order

text: in

text: W

text: is

text: not

text: consistent

text: with

text: the

text: relative

text: order

text: τ

text: in

text: Stabπ(τ),

text: which

text: again

text: can

text: happen

text: only

text: a

text: ﬁnite

text: number

text: of

text: times.

text: (Note,

text: swaps

text: of

text: the

text: other

text: type

text: do

text: not

text: aﬀect

text: these

text: arguments).

text: Lemma

text: Consider

text: a

text: walk

text: τ

text: AU

text: containing

text: fˆ

text: where

text: A,

text: U

text: some

text: words,

text: and

text: there

text: are

text: no

text: swappable

text: pairs

text: inside

text: U.

text: Then

text: U

text: BC

text: where

text: sequence

text: B

text: is

text: a

text: subsequence

text: of

text: Stabπ(τ),

text: and

text: C

text: does

text: not

text: contain

text: named

text: ﬂaws

text: from

text: W

text: τ

text: In

text: particular,

text: if

text: A

text: and

text: τ

text: U

text: does

text: not

text: contain

text: a

text: swappable

text: pair

text: then

text: τ

text: Stabπ(τ)C.

text: Proof.

text: Let

text: u

text: u

text: be

text: the

text: named

text: ﬂaws

text: from

text: W

text: that

text: occur

text: in

text: U

text: (listed

text: in

text: the

text: order

text: of

text: their

text: m

text: τ

text: appearan∈ce

text: in

text: U).

text: We

text: c∈laim

text: that

text: um

text: is

text: a

text: preﬁx

text: of

text: U∈.

text: Indeed,

text: not,

text: then

text: U

text: fui

text: where

text: f

text: W

text: and

text: u

text: W

text: This

text: means

text: that

text: (f,

text: u

text: E

text: and

text: so

text: f

text: u

text: But

text: then

text: (f,

text: u

text: is

text: a

text: τ

text: i

text: τ

text: i

text: τ

text: i

text: i

text: swappable

text: pair

text: in

text: U

text: a

text: contradiction.

text: We

text: obtained

text: a

text: decomposition

text: τ

text: ABC

text: where

text: B

text: u

text: u

text: It

text: remains

text: to

text: show

text: that

text: B

text: is

text: a

text: m

text: subsequence

text: of

text: Stabπ(τ).

text: For

text: that

text: it

text: suﬃces

text: to

text: prove

text: that

text: for

text: any

text: i

text: [m

text: the

text: relative

text: order

text: of

text: ui

text: and

text: in

text: B

text: is

text: the

text: same

text: as

text: in

text: Stabπ(τ).

text: Suppose

text: not,

text: i.e.

text: Stabπ(τ)

text: ui

text: We

text: must

text: have

text: u

text: u

text: (otherwise

text: (u

text: u

text: would

text: be

text: a

text: swappable

text: pair

text: in

text: τ,

text: contradicting

text: the

text: assumption).

text: i

text: i

text: Therefore,

text: (u

text: u

text: E

text: implying

text: that

text: d

text: (u

text: d

text: (u

text: Inspecting

text: Deﬁnition

text: we

text: conclude

text: i

text: τ

text: τ

text: i

text: τ

text: that

text: ui

text: should

text: be

text: to

text: the

text: left

text: of

text: in

text: Stabπ(τ).

text: We

text: obtained

text: a

text: contradiction.

text: Results

text: so

text: far

text: can

text: be

text: used

text: to

text: obtain

text: a

text: mapping

text: Φfˆ

text: and

text: set

text: X

text: fˆ

text: Φfˆ(X

text: fˆ)

text: that

text: satisfy

text: condition

text: π

text: (a)

text: of

text: Theorem

text: To

text: satisfy

text: bijectiveness

text: and

text: condition

text: (b),

text: we

text: need

text: to

text: be

text: careful

text: with

text: the

text: order

text: in

text: which

text: we

text: apply

text: swaps

text: to

text: swappable

text: pairs.

text: We

text: will

text: use

text: the

text: following

text: algorithm.

text: First,

text: let

text: X

text: X

text: fˆ,

text: and

text: then

text: for

text: p

text: do

text: the

text: following:

text: Let

text: k

text: max

text: ∈X

text: k(τ).

text: If

text: k

text: then

text: terminate.

text: τ

text: p

text: X

text: For

text: each

text: τ

text: do

text: the

text: following:

text: if

text: k(τ)

text: k

text: then

text: swap

text: the

text: pair

text: (f,

text: g)

text: at

text: position

text: k

text: in

text: τ,

text: p

text: X

text: otherwise

text: leave

text: τ

text: unchanged.

text: Let

text: be

text: the

text: new

text: set

text: of

text: walks.

text: X

text: X

text: Let

text: us

text: ﬁx

text: a

text: word

text: W

text: (over

text: named

text: ﬂaws),

text: and

text: deﬁne

text: p[W

text: τ

text: p

text: Stabπ(τ)

text: W

text: for

text: an

text: X

text: X

text: index

text: p

text: Theorem

text: will

text: follow

text: from

text: the

text: following

text: result

text: (note

text: that

text: set

text: [W

text: fˆ

text: is

text: valid

text: by

text: the

text: assumption

text: of

text: the

text: theorem).

text: X

text: X

text: X

text: X

text: Lemma

text: If

text: set

text: [W

text: is

text: valid

text: then

text: so

text: is

text: [W

text: and

text: the

text: mapping

text: from

text: [W

text: to

text: [W

text: p

text: p

text: deﬁned

text: by

text: the

text: algorithm

text: above

text: is

text: injective.

text: X

text: Proof.

text: First,

text: let

text: us

text: prove

text: injectiveness.

text: Suppose

text: that

text: two

text: distinct

text: walks

text: τ

text: τ¯

text: [W

text: are

text: trans-

text: X

text: p

text: formed

text: to

text: the

text: same

text: walk

text: τ

text: [W

text: At

text: least

text: one

text: of

text: one

text: walks

text: τ

text: τ¯

text: must

text: have

text: changed.

text: Assume

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:54) ◦ ◦ • (cid:54)∼ • w.l.o.g. that τ = τ . Thus, walk τ = AfgB with f = g is transformed to a walk τ = AgfB. We ◦ ◦ X cannot have τ¯ = τ (then walks τ , τ would both be in [W ], but they do not follow the same ◦ • p ◦ same deterministic strategy - a contradiction). Thus, τ¯ = AfgB, and τ was obtained from τ¯ by ◦ ◦ swapping f and g. Since the SWAP operation from Deﬁnition 3 is injective, we obtain that τ = τ¯ . X Now suppose that [W ] is not valid. Then it contains walks τ, τ¯ of the form p+1 • τ = w . . . w fg . . . • 1 (cid:96) τ¯ = w . . . w ¯fg¯ . . . 1 (cid:96) (cid:54) such that f = ¯f, and the states in τ to the left of f match the corresponding states in τ¯ to the left of ¯f. Here we assume some of the symbols f, g, ¯f, g¯ can equal ∅, which means that they don’t exist. We also assume that f = ∅ ⇒ g = ∅ and ¯f = ∅ ⇒ g¯ = ∅. ◦ ◦ X Let τ and τ¯ be respectively the walks in [W ] that were transformed to τ and τ¯. Since X p (cid:54) ◦ [W ] is valid, at least one of them must have changed. Assume w.l.o.g. that τ = τ . We know p that ∗ ◦ ◦ ( ) τ and τ¯ follow the same deterministic strategy, and they are not proper preﬁxes of each other; ∗∗ ( ) named ﬂaws w , . . . , w , f are distinct. 1 (cid:96) We will also implicitly use the fact that the ﬁrst (cid:96) + 1 states of τ match those of τ¯, and also that swapping adjacent ﬂaws only aﬀects the state between them in a deterministic way, as speciﬁed by the mapping SWAP. Four cases are possible: • ∈ − ◦ • The swapped pair in τ was (w , w ) for i [(cid:96) 1], and so τ = w . . . w w . . . w fg . . .. ∗ ∗∗ i i+1 (cid:54) ◦ ◦ • 1 i+1 i (cid:96) Using ( ) and ( ), we conclude that τ¯ = τ¯ , and so τ¯ = w . . . w w . . . w ¯fg¯ . . .. (Recall X 1 i+1 i ∗ (cid:96) that swaps are applied at the same position for walks in ). Condition ( ) now gives f = ¯f. p • ◦ • ∗ ∗∗ The swapped pair in τ was (w , f), and so τ = w . . . fw g . . .. Using ( ) and ( ), we conclude (cid:54) ◦ ◦ • (cid:96) 1 ∗ (cid:96) that τ¯ = τ¯ , and so τ¯ = w . . . ¯fw g¯ . . .. Condition ( ) now gives f = ¯f. 1 (cid:96) • ◦ • ∈ The swapped pair in τ was (f, g), and so τ = w . . . w gf . . . and f W ◦. Since there are ◦ 1 (cid:96) ◦ • τ no swappable pairs in τ to the right of (g, f), Lemma 27 gives that τ = w . . . w gBC where ◦ 1 (cid:96) B is a subsequence of Stabπ(τ ) and C does not contain named ﬂaws from Wτ◦. Note that B starts with f. ∗ ◦ • By property ( ) we get that τ¯ = w . . . w g . . .. Using Lemma 27 as before, we obtain that ◦ • 1 (cid:96) ◦ τ¯ = w1 . . . w(cid:96)gB¯C¯ where B¯ is a subsequence of Stabπ(τ¯ ) and C¯ does not contain named ﬂaws from W ◦. τ¯ ◦ ◦ ∈ X ◦ ◦ We now observe that τ , τ¯ p[W ], i.e. S◦tab◦π(τ ) = Stabπ(τ¯ ) = W . Therefore, Wτ◦ = W ◦. This fact together with the forms of τ , τ¯ given above implies that B is a permutation τ¯ ◦ ◦ of B¯. We also know that both B and B¯ are subsequences of Stabπ(τ ) = Stabπ(τ¯ ) = W and all elements of W are distinct. Thus, we can conclude that B = B¯. ◦ • ◦ We showed that τ¯ = w . . . w gf . . .. Since (g, f) is a swappable pair in τ , it is also a ◦ 1 (cid:96) ◦ • swappable pair in τ¯ (at the same position as in τ ). Therefore, τ¯ = w . . . w fg . . ., and so 1 (cid:96) f = ¯f. 18

text: w.l.o.g.

text: that

text: τ

text: τ

text: Thus,

text: walk

text: τ

text: AfgB

text: with

text: f

text: g

text: is

text: transformed

text: to

text: a

text: walk

text: τ

text: AgfB.

text: We

text: X

text: cannot

text: have

text: τ¯

text: τ

text: (then

text: walks

text: τ

text: τ

text: would

text: both

text: be

text: in

text: [W

text: but

text: they

text: do

text: not

text: follow

text: the

text: same

text: p

text: same

text: deterministic

text: strategy

text: a

text: contradiction).

text: Thus,

text: τ¯

text: AfgB,

text: and

text: τ

text: was

text: obtained

text: from

text: τ¯

text: by

text: swapping

text: f

text: and

text: g.

text: Since

text: the

text: SWAP

text: operation

text: from

text: Deﬁnition

text: is

text: injective,

text: we

text: obtain

text: that

text: τ

text: τ¯

text: X

text: Now

text: suppose

text: that

text: [W

text: is

text: not

text: valid.

text: Then

text: it

text: contains

text: walks

text: τ,

text: τ¯

text: of

text: the

text: form

text: τ

text: w

text: w

text: fg

text: τ¯

text: w

text: w

text: ¯fg¯

text: such

text: that

text: f

text: ¯f,

text: and

text: the

text: states

text: in

text: τ

text: to

text: the

text: left

text: of

text: f

text: match

text: the

text: corresponding

text: states

text: in

text: τ¯

text: to

text: the

text: left

text: of

text: ¯f.

text: Here

text: we

text: assume

text: some

text: of

text: the

text: symbols

text: f,

text: g,

text: ¯f,

text: g¯

text: can

text: equal

text: which

text: means

text: that

text: they

text: don’t

text: exist.

text: We

text: also

text: assume

text: that

text: f

text: g

text: and

text: ¯f

text: g¯

text: X

text: Let

text: τ

text: and

text: τ¯

text: be

text: respectively

text: the

text: walks

text: in

text: [W

text: that

text: were

text: transformed

text: to

text: τ

text: and

text: τ¯.

text: Since

text: X

text: p

text: [W

text: is

text: valid,

text: at

text: least

text: one

text: of

text: them

text: must

text: have

text: changed.

text: Assume

text: w.l.o.g.

text: that

text: τ

text: τ

text: We

text: know

text: p

text: that

text: τ

text: and

text: τ¯

text: follow

text: the

text: same

text: deterministic

text: strategy,

text: and

text: they

text: are

text: not

text: proper

text: preﬁxes

text: of

text: each

text: other;

text: named

text: ﬂaws

text: w

text: w

text: f

text: are

text: distinct.

text: We

text: will

text: also

text: implicitly

text: use

text: the

text: fact

text: that

text: the

text: ﬁrst

text: states

text: of

text: τ

text: match

text: those

text: of

text: τ¯,

text: and

text: also

text: that

text: swapping

text: adjacent

text: ﬂaws

text: only

text: aﬀects

text: the

text: state

text: between

text: them

text: in

text: a

text: deterministic

text: way,

text: as

text: speciﬁed

text: by

text: the

text: mapping

text: SWAP.

text: Four

text: cases

text: are

text: possible:

text: The

text: swapped

text: pair

text: in

text: τ

text: was

text: (w

text: w

text: for

text: i

text: and

text: so

text: τ

text: w

text: w

text: w

text: w

text: fg

text: i

text: i

text: Using

text: and

text: we

text: conclude

text: that

text: τ¯

text: τ¯

text: and

text: so

text: τ¯

text: w

text: w

text: w

text: w

text: ¯fg¯

text: (Recall

text: X

text: i

text: that

text: swaps

text: are

text: applied

text: at

text: the

text: same

text: position

text: for

text: walks

text: in

text: Condition

text: now

text: gives

text: f

text: ¯f.

text: p

text: The

text: swapped

text: pair

text: in

text: τ

text: was

text: (w

text: f),

text: and

text: so

text: τ

text: w

text: fw

text: g

text: Using

text: and

text: we

text: conclude

text: that

text: τ¯

text: τ¯

text: and

text: so

text: τ¯

text: w

text: ¯fw

text: g¯

text: Condition

text: now

text: gives

text: f

text: ¯f.

text: The

text: swapped

text: pair

text: in

text: τ

text: was

text: (f,

text: g),

text: and

text: so

text: τ

text: w

text: w

text: gf

text: and

text: f

text: W

text: Since

text: there

text: are

text: τ

text: no

text: swappable

text: pairs

text: in

text: τ

text: to

text: the

text: right

text: of

text: (g,

text: f),

text: Lemma

text: gives

text: that

text: τ

text: w

text: w

text: gBC

text: where

text: B

text: is

text: a

text: subsequence

text: of

text: Stabπ(τ

text: and

text: C

text: does

text: not

text: contain

text: named

text: ﬂaws

text: from

text: Wτ◦.

text: Note

text: that

text: B

text: starts

text: with

text: f.

text: By

text: property

text: we

text: get

text: that

text: τ¯

text: w

text: w

text: g

text: Using

text: Lemma

text: as

text: before,

text: we

text: obtain

text: that

text: τ¯

text: where

text: B¯

text: is

text: a

text: subsequence

text: of

text: Stabπ(τ¯

text: and

text: C¯

text: does

text: not

text: contain

text: named

text: ﬂaws

text: from

text: W

text: τ¯

text: X

text: We

text: now

text: observe

text: that

text: τ

text: τ¯

text: p[W

text: i.e.

text: S◦tab◦π(τ

text: Stabπ(τ¯

text: W

text: Therefore,

text: Wτ◦

text: W

text: This

text: fact

text: together

text: with

text: the

text: forms

text: of

text: τ

text: τ¯

text: given

text: above

text: implies

text: that

text: B

text: is

text: a

text: permutation

text: τ¯

text: of

text: B¯.

text: We

text: also

text: know

text: that

text: both

text: B

text: and

text: B¯

text: are

text: subsequences

text: of

text: Stabπ(τ

text: Stabπ(τ¯

text: W

text: and

text: all

text: elements

text: of

text: W

text: are

text: distinct.

text: Thus,

text: we

text: can

text: conclude

text: that

text: B

text: B¯.

text: We

text: showed

text: that

text: τ¯

text: w

text: w

text: gf

text: Since

text: (g,

text: f)

text: is

text: a

text: swappable

text: pair

text: in

text: τ

text: it

text: is

text: also

text: a

text: swappable

text: pair

text: in

text: τ¯

text: (at

text: the

text: same

text: position

text: as

text: in

text: τ

text: Therefore,

text: τ¯

text: w

text: w

text: fg

text: and

text: so

text: f

text: ¯f.


text: To our knowledge, our commutativity condition captures all previously known cases when the ﬂaw selection rules was allowed to be arbitrary. Other related work Applications that involve non-Cartesian spaces Ω (such as permutations, matchings and spanning trees) have often been tackled via the Lopsided LLL [6]; we refer to [14, 15] for a comprehensive survey. On the level of techniques there is some connection between this paper and a recent work by Knuth [10]; we discuss this in Section 2. 2 Background and preliminaries First, we give a formal description of the algorithm from [9, 2]. Assume that for each object ∈ ∈ ⊆ σ Ω and each ﬂaw f F there is a non-empty set of actions A(f, σ) Ω that can be taken σ (cid:48)| (cid:48) ∈ for “addressing” ﬂaw f at σ, and a probability distribution ρ(σ f, σ) over σ A(f, σ). Note, by ·| deﬁnition A(f, σ) is the support of distribution ρ( f, σ). The collection of all resampling oracles ∈ will be denoted as ρ. We ﬁx some probability distribution ω on Ω with ω(σ) > 0 for all σ Ω (it will be used later for formulating various conditions). Note that our notation is quite diﬀerent from that of Harvey and Vondr´ak [9].2 The algorithm can now be stated as follows. Algorithm 1 Random walk. Input: initial distribution ωinit over Ω, strategy Λ. ∈ 1: sample σ Ω according to ωinit 2: while Fσ non-em∈pty do 3: select ﬂaw(cid:48) ∈f Fσ according to Λ (cid:48)| ← (cid:48) 4: sample σ A(f, σ) according to distribution ρ(σ f, σ), set σ σ . 5: end while Clearly, if the algorithm terminates then it produces a ﬂawless object σ. The works [1, 9, 2] used speciﬁc strategies Λ. As stated in the introduction, our goal is to understand when an arbitrary strategy can be used. This means that ﬂaw f in line 3 is selected according to some distribution ∈ which is a function of the entire past execution history3. Note that if ﬂaw f F in line 3 depends σ only on σ then the algorithm can be viewed a random walk in a Markov chain with states Ω, while in a more general case the walk can be non-Markovian. 2.1 Walks and the potential causality graph → (cid:48) (cid:48) f We say that σ σ is a (valid) walk if it is possible to get from state σ to σ by “addressing” ∈ (cid:48) ∈ ﬂaw f as described in the algorithm, i.e. if two conditions hold: f F and σ A(f, σ). Whenever σ → (cid:48) f we write σ σ , we mean that it is a valid walk. In many applications resampling oracles satisfy a special condition called atomicity [1]. ∈ (cid:48) ∈ ∈ Deﬁnition 1. ρ is called atomic if for any f F and σ Ω there exists at most one object σ Ω → (cid:48) f such that σ σ . ∼ Next, we need to describe “dependences” between ﬂaws in F . Let be some symmetric relation ∼ on F (so that (F, ) is an undirected graph). It is assumed to be ﬁxed throughout the paper. For 2 “Flaws” f correspond to “bad events” E in [9]. The distribution over Ω was denoted in [9] as µ, the states of i ∈ Ω as ω, and the resampling oracle for the bad event E at state ω Ω as r (ω). i i 3The description of the algorithm in [16] says “pick an arbitrary violated event”. This is consistent with our deﬁnition of an “arbitrary strategy”: in the analysis Moser and Tardos mention that this selection must come from some ﬁxed procedure (either deterministic or randomized), so that expected values are well-deﬁned. 3 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: To

text: our

text: knowledge,

text: our

text: commutativity

text: condition

text: captures

text: all

text: previously

text: known

text: cases

text: when

text: the

text: ﬂaw

text: selection

text: rules

text: was

text: allowed

text: to

text: be

text: arbitrary.

text: Other

text: related

text: work

text: Applications

text: that

text: involve

text: non-Cartesian

text: spaces

text: Ω

text: (such

text: as

text: permutations,

text: matchings

text: and

text: spanning

text: trees)

text: have

text: often

text: been

text: tackled

text: via

text: the

text: Lopsided

text: LLL

text: we

text: refer

text: to

text: for

text: a

text: comprehensive

text: survey.

text: On

text: the

text: level

text: of

text: techniques

text: there

text: is

text: some

text: connection

text: between

text: this

text: paper

text: and

text: a

text: recent

text: work

text: by

text: Knuth

text: we

text: discuss

text: this

text: in

text: Section

text: Background

text: and

text: preliminaries

text: First,

text: we

text: give

text: a

text: formal

text: description

text: of

text: the

text: algorithm

text: from

text: Assume

text: that

text: for

text: each

text: object

text: σ

text: Ω

text: and

text: each

text: ﬂaw

text: f

text: F

text: there

text: is

text: a

text: non-empty

text: set

text: of

text: actions

text: A(f,

text: σ)

text: Ω

text: that

text: can

text: be

text: taken

text: σ

text: for

text: “addressing”

text: ﬂaw

text: f

text: at

text: σ,

text: and

text: a

text: probability

text: distribution

text: ρ(σ

text: f,

text: σ)

text: over

text: σ

text: A(f,

text: σ).

text: Note,

text: by

text: deﬁnition

text: A(f,

text: σ)

text: is

text: the

text: support

text: of

text: distribution

text: ρ(

text: f,

text: σ).

text: The

text: collection

text: of

text: all

text: resampling

text: oracles

text: will

text: be

text: denoted

text: as

text: ρ.

text: We

text: ﬁx

text: some

text: probability

text: distribution

text: ω

text: on

text: Ω

text: with

text: ω(σ)

text: for

text: all

text: σ

text: Ω

text: (it

text: will

text: be

text: used

text: later

text: for

text: formulating

text: various

text: conditions).

text: Note

text: that

text: our

text: notation

text: is

text: quite

text: diﬀerent

text: from

text: that

text: of

text: Harvey

text: and

text: Vondr´ak

text: The

text: algorithm

text: can

text: now

text: be

text: stated

text: as

text: follows.

text: Algorithm

text: Random

text: walk.

text: Input:

text: initial

text: distribution

text: ωinit

text: over

text: Ω,

text: strategy

text: Λ.

text: sample

text: σ

text: Ω

text: according

text: to

text: ωinit

text: while

text: Fσ

text: non-em∈pty

text: do

text: select

text: ∈f

text: Fσ

text: according

text: to

text: Λ

text: sample

text: σ

text: A(f,

text: σ)

text: according

text: to

text: distribution

text: ρ(σ

text: f,

text: σ),

text: set

text: σ

text: σ

text: end

text: while

text: Clearly,

text: if

text: the

text: algorithm

text: terminates

text: then

text: it

text: produces

text: a

text: ﬂawless

text: object

text: σ.

text: The

text: works

text: used

text: speciﬁc

text: strategies

text: Λ.

text: As

text: stated

text: in

text: the

text: introduction,

text: our

text: goal

text: is

text: to

text: understand

text: when

text: an

text: arbitrary

text: strategy

text: can

text: be

text: used.

text: This

text: means

text: that

text: ﬂaw

text: f

text: in

text: line

text: is

text: selected

text: according

text: to

text: some

text: distribution

text: which

text: is

text: a

text: function

text: of

text: the

text: entire

text: past

text: execution

text: Note

text: that

text: if

text: ﬂaw

text: f

text: F

text: in

text: line

text: depends

text: σ

text: only

text: on

text: σ

text: then

text: the

text: algorithm

text: can

text: be

text: viewed

text: a

text: random

text: walk

text: in

text: a

text: Markov

text: chain

text: with

text: states

text: Ω,

text: while

text: in

text: a

text: more

text: general

text: case

text: the

text: walk

text: can

text: be

text: non-Markovian.

text: Walks

text: and

text: the

text: potential

text: causality

text: graph

text: f

text: We

text: say

text: that

text: σ

text: σ

text: is

text: a

text: (valid)

text: walk

text: if

text: it

text: is

text: possible

text: to

text: get

text: from

text: state

text: σ

text: to

text: σ

text: by

text: “addressing”

text: ﬂaw

text: f

text: as

text: described

text: in

text: the

text: algorithm,

text: i.e.

text: if

text: two

text: conditions

text: hold:

text: f

text: F

text: and

text: σ

text: A(f,

text: σ).

text: Whenever

text: σ

text: f

text: we

text: write

text: σ

text: σ

text: we

text: mean

text: that

text: it

text: is

text: a

text: valid

text: walk.

text: In

text: many

text: applications

text: resampling

text: oracles

text: satisfy

text: a

text: special

text: condition

text: called

text: atomicity

text: Deﬁnition

text: ρ

text: is

text: called

text: atomic

text: if

text: for

text: any

text: f

text: F

text: and

text: σ

text: Ω

text: there

text: exists

text: at

text: most

text: one

text: object

text: σ

text: Ω

text: f

text: such

text: that

text: σ

text: σ

text: Next,

text: we

text: need

text: to

text: describe

text: “dependences”

text: between

text: ﬂaws

text: in

text: F

text: Let

text: be

text: some

text: symmetric

text: relation

text: on

text: F

text: (so

text: that

text: (F,

text: is

text: an

text: undirected

text: graph).

text: It

text: is

text: assumed

text: to

text: be

text: ﬁxed

text: throughout

text: the

text: paper.

text: For

text: “Flaws”

text: f

text: correspond

text: to

text: “bad

text: events”

text: E

text: in

text: The

text: distribution

text: over

text: Ω

text: was

text: denoted

text: in

text: as

text: µ,

text: the

text: states

text: of

text: i

text: Ω

text: as

text: ω,

text: and

text: the

text: resampling

text: oracle

text: for

text: the

text: bad

text: event

text: E

text: at

text: state

text: ω

text: Ω

text: as

text: r

text: (ω).

text: i

text: i

text: description

text: of

text: the

text: algorithm

text: in

text: says

text: “pick

text: an

text: arbitrary

text: violated

text: event”.

text: This

text: is

text: consistent

text: with

text: our

text: deﬁnition

text: of

text: an

text: “arbitrary

text: strategy”:

text: in

text: the

text: analysis

text: Moser

text: and

text: Tardos

text: mention

text: that

text: this

text: selection

text: must

text: come

text: from

text: some

text: ﬁxed

text: procedure

text: (either

text: deterministic

text: or

text: randomized),

text: so

text: that

text: expected

text: values

text: are

text: well-deﬁned.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##