text: there are as many as eight independent positive results (e.g., 100Mo). In some experiments, the statistical error does not always play the primary role in overall half-life uncertainties. For example, the NEMO-3 experiment with 100Mo has currently detected more than 219,000 2νββ events [1], which ∼ results in a value for the statistical error of 0.2% . At the same time, the systematic error for many experiments on 2νββ decay remains quite ∼ − high ( 10 30%) and very often cannot be determined reliably. As a consequence, it is frequently diﬃcult for the “user” to select the “best” half- life value among the results. Using an averaging procedure, one can produce the most reliable and accurate half-life values for each isotope. Why are accurate half-life periods necessary? The most important moti- vations are the following: 1) Nuclear spectroscopy. Now we know that some isotopes which were earlier considered to be stable are not, and decay via the double beta decay pro- ∼ − cesses with a half-life period of 1018 1024 yr are observed. The values which are presented here should be introduced into the isotope tables. 2) Nuclear matrix elements (NME). First, it gives the possibility to im- prove the quality of NME calculations for two neutrino double beta decay, so one can directly compare experimental and calculated values. For example, so-called ”g (axial-vector coupling constant) quenching” problem could be A solved by comparison of exact experimental values of NMEs and results of theoretical calculations (see discussions in Ref. [2, 3, 4, 5]. Second, it gives the possibility to improve the quality of NME calculations for neutrinoless double beta decay. The accurate half-life values for 2νββ decay are used to adjust the most relevant parameter of the quasiparticle random-phase ap- proximation (QRPA) model, the strength of the particle-particle interaction g [6, 7, 8, 9]. pp 3) Research on the single state dominance (SSD) mechanism [10, 11] and a check of the ”bosonic” component of the neutrino hypothesis [12, 13] is possible. In the present work, an analysis of all “positive” experimental results has been performed, and averaged or recommended values for isotopes are presented. The ﬁrst time that this work was done was in 2001, and the results were presented at the International Workshop on the calculation of double beta decay nuclear matrix elements, MEDEX’01 [14]. Then revised half-life values were presented at MEDEX’05 and MEDEX’09 and published in Ref. [15] and [16, 17], respectively. In the present paper, new positive results obtained 2

text: there

text: are

text: as

text: many

text: as

text: eight

text: independent

text: positive

text: results

text: (e.g.,

text: In

text: some

text: experiments,

text: the

text: statistical

text: error

text: does

text: not

text: always

text: play

text: the

text: primary

text: role

text: in

text: overall

text: half-life

text: uncertainties.

text: For

text: example,

text: the

text: experiment

text: with

text: has

text: currently

text: detected

text: more

text: than

text: 2νββ

text: events

text: which

text: results

text: in

text: a

text: value

text: for

text: the

text: statistical

text: error

text: of

text: At

text: the

text: same

text: time,

text: the

text: systematic

text: error

text: for

text: many

text: experiments

text: on

text: 2νββ

text: decay

text: remains

text: quite

text: high

text: and

text: very

text: often

text: cannot

text: be

text: determined

text: reliably.

text: As

text: a

text: consequence,

text: it

text: is

text: frequently

text: diﬃcult

text: for

text: the

text: “user”

text: to

text: select

text: the

text: “best”

text: half-

text: life

text: value

text: among

text: the

text: results.

text: Using

text: an

text: averaging

text: procedure,

text: one

text: can

text: produce

text: the

text: most

text: reliable

text: and

text: accurate

text: half-life

text: values

text: for

text: each

text: isotope.

text: Why

text: are

text: accurate

text: half-life

text: periods

text: necessary?

text: The

text: most

text: important

text: moti-

text: vations

text: are

text: the

text: following:

text: Nuclear

text: spectroscopy.

text: Now

text: we

text: know

text: that

text: some

text: isotopes

text: which

text: were

text: earlier

text: considered

text: to

text: be

text: stable

text: are

text: not,

text: and

text: decay

text: via

text: the

text: double

text: beta

text: decay

text: pro-

text: cesses

text: with

text: a

text: half-life

text: period

text: of

text: yr

text: are

text: observed.

text: The

text: values

text: which

text: are

text: presented

text: here

text: should

text: be

text: introduced

text: into

text: the

text: isotope

text: tables.

text: Nuclear

text: matrix

text: elements

text: (NME).

text: First,

text: it

text: gives

text: the

text: possibility

text: to

text: im-

text: prove

text: the

text: quality

text: of

text: NME

text: calculations

text: for

text: two

text: neutrino

text: double

text: beta

text: decay,

text: so

text: one

text: can

text: directly

text: compare

text: experimental

text: and

text: calculated

text: values.

text: For

text: example,

text: so-called

text: ”g

text: (axial-vector

text: coupling

text: constant)

text: quenching”

text: problem

text: could

text: be

text: A

text: solved

text: by

text: comparison

text: of

text: exact

text: experimental

text: values

text: of

text: NMEs

text: and

text: results

text: of

text: theoretical

text: calculations

text: (see

text: discussions

text: in

text: Ref.

text: Second,

text: it

text: gives

text: the

text: possibility

text: to

text: improve

text: the

text: quality

text: of

text: NME

text: calculations

text: for

text: neutrinoless

text: double

text: beta

text: decay.

text: The

text: accurate

text: half-life

text: values

text: for

text: 2νββ

text: decay

text: are

text: used

text: to

text: adjust

text: the

text: most

text: relevant

text: parameter

text: of

text: the

text: quasiparticle

text: random-phase

text: ap-

text: proximation

text: (QRPA)

text: model,

text: the

text: strength

text: of

text: the

text: particle-particle

text: interaction

text: g

text: pp

text: Research

text: on

text: the

text: single

text: state

text: dominance

text: (SSD)

text: mechanism

text: and

text: a

text: check

text: of

text: the

text: ”bosonic”

text: component

text: of

text: the

text: neutrino

text: hypothesis

text: is

text: possible.

text: In

text: the

text: present

text: work,

text: an

text: analysis

text: of

text: all

text: “positive”

text: experimental

text: results

text: has

text: been

text: performed,

text: and

text: averaged

text: or

text: recommended

text: values

text: for

text: isotopes

text: are

text: presented.

text: The

text: ﬁrst

text: time

text: that

text: this

text: work

text: was

text: done

text: was

text: in

text: and

text: the

text: results

text: were

text: presented

text: at

text: the

text: International

text: Workshop

text: on

text: the

text: calculation

text: of

text: double

text: beta

text: decay

text: nuclear

text: matrix

text: elements,

text: Then

text: revised

text: half-life

text: values

text: were

text: presented

text: at

text: and

text: and

text: published

text: in

text: Ref.

text: and

text: respectively.

text: In

text: the

text: present

text: paper,

text: new

text: positive

text: results

text: obtained


text: Table 1: continued. ∼ · 100Mo 500 11.5+−3.0 1018 1/7 [49], 1991 2.0 · 67 11.6+−3.4 1018 7 [50], 1991 ± 0±.8 · 1433 [7.3 0.35(stat) 0.8(syst)] 1018b) 3 [51], 1995 · 175 7.6+−2.2 1018 1/2 [52], 1997 1±.4 · 377 [6.75+−0.37(stat) 0.68(syst)] 1018 10 [53], 1997 ±0.42 ± · 800 [7.2 1.1(stat) 1.8(syst)] 1018 1/9 [54], 2001 ± ± · 219000 [7.11 0.02(stat) 0.54(syst)] 1018c) 40 [1], 2005 ∼ ± ± · ∼ 350 [7.15 0.37(stat) 0.66(syst)] 1018 5d) [19], 2014 ± · (2.1 0.3) 1018 (geochem.) [55], 2004 ± · Average value: (7.1 0.4) 1018 · 100Mo - 133e) 6.1+−1.8 1020 1/7 [56], 1995 ±1.1 · 100Ru (0+) 153e) [9.3+−2.8(stat) 1.4(syst)] 1020 1/4 [57], 1999 1 1.7 ± · ∼ 19.5 [5.9+−1.7(stat) 0.6(syst)] 1020 8 [58], 2001 1.1 ± · ∼ 35.5 [5.5+−1.2(stat) 0.3(syst)] 1020 8 [59], 2009 0.8 ± · ∼ 37.5 [5.7+−1.3(stat) 0.8(syst)] 1020 3 [60], 2007 0.9 ± · ∼ 597e) [6.9+−1.0(stat) 0.7(syst)] 1020 1/10 [20], 2010 ±0.8 ± · 239e) [7.5 0.6(stat) 0.6(syst)] 1020 2 [21], 2014 · Average value: 6.7+−0.5 1020 0.4 ∼ · ∼ 116Cd 180 2.6+−0.9 1019 1/4 [61], 1995 ± 0±.5 · 174.6 [2.9 0.3(stat) 0.2(syst)] 1019b) 3 [62], 1996 ± · ∼ 9850 [2.9 0.06(stat)+−0.4(syst)] 1019 3 [63], 2003 ± ± 0.3 · 7000 [2.88 0.04(stat) 0.16(syst)] 1019c) 10 [64], 2011 ± ± · 34927 [2.80 0.05(stat) 0.4(syst)] 1019 2 [22], 2014 ± · Average value: (2.87 0.13) 1019 ∼ · 128Te 2.2 1024 (geochem.) [65], 1991 ± · (7.7 0.4) 1024 (geochem.) [66], 1993 ± · (2.41 0.39) 1024 (geochem.) [67], 2008 ± · (2.3 0.3) 1024 (geochem.) [68], 2008 ± · Recommended value: (2.0 0.3) 1024 5 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Table

label: paragraph

text: continued.

label: caption

label: table

text: (geochem.)

text: Average

text: value:

text: Average

text: value:

text: Average

text: value:

text: (geochem.)

text: (geochem.)

text: (geochem.)

text: (geochem.)

text: Recommended

text: value:

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: larger than 1, but not greatly so, it is still best to use the average data, but to increase the quoted error, δx¯ in Equation 1, by a factor of S deﬁned by − S = [χ2/(N 1)]1/2. (2) For averages, the statistical and systematic errors are treated in quadra- ture and used as a combined error δx . In some cases, only the results i obtained with high enough signal-to-background ratio were used. 3.1. 48Ca There are three independent experiments in which 2νββ decay of 48Ca was observed [33, 34, 35]. The results are in good agreement. The weighted average value is: · T = 4.4+−0.6 1019yr. 1/2 0.5 3.2. 76Ge Considering the results of six experiments, a few additional comments are necessary, as follows: 1) We use here ﬁnal result of the Heidelberg-Moscow Collaboration, T = ± · 1/2 [1.74 0.01(stat)+−0.18(syst)] 1021 yr [41]. 0.16 · 2) In Ref. [38], the value T = 0.92+−0.07 1021 yr was presented. However, 1/2 0.04 after a more careful analysis, this result has been changed [39]. In Ref. [39] a few values for half-life using diﬀerent analysis methods were obtained. I use here the value obtained by ﬁt the data using χ2 model, which take into account shape of the spectrum (see Table 1). Unfortunately systematic error was not discussed and taken into account in this paper. This is why during my analysis I added typical systematic error for such sort of experiments ± ± · ( 10%). So, ﬁnally, I use T = [1.27+−021 (stat) 0.13(syst)] 1021 yr as a 1/2 0.16 result of Ref. [39]. 3) The results presented in Ref. [36] do not agree with the more recent experiments [40, 41, 18]. Furthermore, the error presented in [36] appears to be too small, especially taking into account that the signal-to-background ∼ ratio in this experiment is equal to 1/8. It has been mentioned before [77] ∼ − that the half-life value in this work can be 1.5 2 times higher because the thickness of the dead layer in the Ge(Li) detectors used can be diﬀerent for crystals made from enriched Ge, rather than natural Ge. With no uniformity of the external background (and this is the case!), this eﬀect can have an appreciable inﬂuence on the ﬁnal result. 7

text: larger

text: than

text: but

text: not

text: greatly

text: so,

text: it

text: is

text: still

text: best

text: to

text: use

text: the

text: average

text: data,

text: but

text: to

text: increase

text: the

text: quoted

text: error,

text: δx¯

text: in

text: Equation

text: by

text: a

text: factor

text: of

text: S

text: deﬁned

text: by

label: equation

text: S

text: For

text: averages,

text: the

text: statistical

text: and

text: systematic

text: errors

text: are

text: treated

text: in

text: quadra-

text: ture

text: and

text: used

text: as

text: a

text: combined

text: error

text: δx

text: In

text: some

text: cases,

text: only

text: the

text: results

text: i

text: obtained

text: with

text: high

text: enough

text: signal-to-background

text: ratio

text: were

text: used.

label: section

text: There

text: are

text: three

text: independent

text: experiments

text: in

text: which

text: 2νββ

text: decay

text: of

text: was

text: observed

text: The

text: results

text: are

text: in

text: good

text: agreement.

text: The

text: weighted

text: average

text: value

text: is:

text: T

text: Considering

text: the

text: results

text: of

text: six

text: experiments,

text: a

text: few

text: additional

text: comments

text: are

text: necessary,

text: as

text: follows:

text: We

text: use

text: here

text: ﬁnal

text: result

text: of

text: the

text: Heidelberg-Moscow

text: Collaboration,

text: T

text: yr

text: In

text: Ref.

text: the

text: value

text: T

text: yr

text: was

text: presented.

text: However,

text: after

text: a

text: more

text: careful

text: analysis,

text: this

text: result

text: has

text: been

text: changed

text: In

text: Ref.

text: a

text: few

text: values

text: for

text: half-life

text: using

text: diﬀerent

text: analysis

text: methods

text: were

text: obtained.

text: I

text: use

text: here

text: the

text: value

text: obtained

text: by

text: ﬁt

text: the

text: data

text: using

text: χ2

text: model,

text: which

text: take

text: into

text: account

text: shape

text: of

text: the

text: spectrum

text: (see

text: Table

text: Unfortunately

text: systematic

text: error

text: was

text: not

text: discussed

text: and

text: taken

text: into

text: account

text: in

text: this

text: paper.

text: This

text: is

text: why

text: during

text: my

text: analysis

text: I

text: added

text: typical

text: systematic

text: error

text: for

text: such

text: sort

text: of

text: experiments

text: So,

text: ﬁnally,

text: I

text: use

text: T

text: (stat)

text: yr

text: as

text: a

text: result

text: of

text: Ref.

text: The

text: results

text: presented

text: in

text: Ref.

text: do

text: not

text: agree

text: with

text: the

text: more

text: recent

text: experiments

text: Furthermore,

text: the

text: error

text: presented

text: in

text: appears

text: to

text: be

text: too

text: small,

text: especially

text: taking

text: into

text: account

text: that

text: the

text: signal-to-background

text: ratio

text: in

text: this

text: experiment

text: is

text: equal

text: to

text: It

text: has

text: been

text: mentioned

text: before

text: that

text: the

text: half-life

text: value

text: in

text: this

text: work

text: can

text: be

text: times

text: higher

text: because

text: the

text: thickness

text: of

text: the

text: dead

text: layer

text: in

text: the

text: Ge(Li)

text: detectors

text: used

text: can

text: be

text: diﬀerent

text: for

text: crystals

text: made

text: from

text: enriched

text: Ge,

text: rather

text: than

text: natural

text: Ge.

text: With

text: no

text: uniformity

text: of

text: the

text: external

text: background

text: (and

text: this

text: is

text: the

text: case!),

text: this

text: eﬀect

text: can

text: have

text: an

text: appreciable

text: inﬂuence

text: on

text: the

text: ﬁnal

text: result.


text: The ﬁrst indication of a positive result for 130Te in a direct experiment was obtained in [69]. More accurate and reliable value was obtained recently in NEMO-3 experiment [23]. The results are in good agreement, and the weighted average value for half-life is ± · T = (6.9 1.3) 1020yr. 1/2 ± · − Now, using very well-known ratio T (130Te)/T (128Te) = (3.52 0.11) 10 4 1/2 1/2 [66], one can obtain half-life value for 128Te, ± · T = (2.0 0.3) 1024yr. 1/2 I recommend to use these last two results as the best present half-life values for 130Te and 128Te, respectively. 3.9. 136Xe The half-life value was recently measured in two independent experiments, EXO [28, 27] and Kamland-Zen [83, 26]. To obtain average value I use most precise results from these experiments, obtained in [26, 27] (see Table 1). The weighted average value is ± · T = (2.19 0.06) 1021yr. 1/2 3.10. 150Nd This half-life value was measured in three independent experiments [70, 53, 71]. The most accurate value was obtained in Ref. [71]. This value ∼ ∼ is higher than in Ref. [53] and lower than in Ref. [70] ( 3σ and 2σ diﬀerences, respectively). Using Eq. (1), and three existing values, one ± · obtains T = (8.2 0.5) 1018 yr. Taking into account the fact that χ2 > 1 1/2 and S = 1.89 (see Eq. (2)) we then obtain: ± · T = (8.2 0.9) 1018yr. 1/2 3.11. 150Nd - 150Sm (0+; 740.4 keV) 1 There are two independent experiments in which 2νββ decay of 150Nd to the 0+ excited state of 150Sm was observed [72, 24] (the preliminary result 1 of Ref. [72] was published in Ref. [84]). The results are in good agreement. The weighted average value is: · T = 1.2+−0.3 1020yr. 1/2 0.2 10

text: The

text: ﬁrst

text: indication

text: of

text: a

text: positive

text: result

text: for

text: in

text: a

text: direct

text: experiment

text: was

text: obtained

text: in

text: More

text: accurate

text: and

text: reliable

text: value

text: was

text: obtained

text: recently

text: in

text: experiment

text: The

text: results

text: are

text: in

text: good

text: agreement,

text: and

text: the

text: weighted

text: average

text: value

text: for

text: half-life

text: is

text: T

text: Now,

text: using

text: very

text: well-known

text: ratio

text: T

text: one

text: can

text: obtain

text: half-life

text: value

text: for

text: T

text: I

text: recommend

text: to

text: use

text: these

text: last

text: two

text: results

text: as

text: the

text: best

text: present

text: half-life

text: values

text: for

text: and

text: respectively.

text: The

text: half-life

text: value

text: was

text: recently

text: measured

text: in

text: two

text: independent

text: experiments,

text: EXO

text: and

text: Kamland-Zen

text: To

text: obtain

text: average

text: value

text: I

text: use

text: most

text: precise

text: results

text: from

text: these

text: experiments,

text: obtained

text: in

text: (see

text: Table

text: The

text: weighted

text: average

text: value

text: is

text: T

text: This

text: half-life

text: value

text: was

text: measured

text: in

text: three

text: independent

text: experiments

text: The

text: most

text: accurate

text: value

text: was

text: obtained

text: in

text: Ref.

text: This

text: value

text: is

text: higher

text: than

text: in

text: Ref.

text: and

text: lower

text: than

text: in

text: Ref.

text: 3σ

text: and

text: 2σ

text: diﬀerences,

text: respectively).

text: Using

text: Eq.

text: and

text: three

text: existing

text: values,

text: one

text: obtains

text: T

text: yr.

text: Taking

text: into

text: account

text: the

text: fact

text: that

text: χ2

text: and

text: S

text: (see

text: Eq.

text: we

text: then

text: obtain:

text: T

text: keV)

text: There

text: are

text: two

text: independent

text: experiments

text: in

text: which

text: 2νββ

text: decay

text: of

text: to

text: the

text: excited

text: state

text: of

text: was

text: observed

text: (the

text: preliminary

text: result

text: of

text: Ref.

text: was

text: published

text: in

text: Ref.

text: The

text: results

text: are

text: in

text: good

text: agreement.

text: The

text: weighted

text: average

text: value

text: is:

text: T


text: 1 Introduction The m-ary search trees are a class of data structures introduced by Muntz and Uzgalis [35] in 1971 in computer algorithms to support efﬁcient searching and sorting of data; see the next section for more details. When constructed from a random permutation of n elements, the space requirement (total number of nodes to store the input) S of such random m-ary search trees (cid:62) n (m 3) is known to exhibit a phase change phenomenon: its distribution is asymptotically (cid:54) (cid:54) Gaussian for large n when the branching factor m satisﬁes 3 m 26 but does not approach (cid:62) a limit law when m 27; see [8, 22, 30, 31] and the references therein. On the other hand, it is also known that the total key path length K (the sum over all distances from the root to n any key) does not change its limiting behavior when m varies, and tends asymptotically, after (cid:62) properly centered and normalized, to a limit law for each m 3. Another closely related shape measure, the total node path length N (summing over all distances from the root to any node) n also follows asymptotically a very similar behavior. Our motivating question was “how does K or N depend on S ?” Surprisingly, despite n n n the strong dependence of the deﬁnition of N on S (see (2)), we show that the correlation n n coefﬁcient ρ(S , N ) satisﬁes (cid:40) n n (cid:54) (cid:54) ∼ 0, if 3 m 26; ρ(S , N ) (cid:62) (1) n n F (β log n), if m 27, ρ where F (t) is a 2π-periodic function and β = β is a structural constant depending on ρ m m. The same type of results also holds for ρ(S , K ). In words, N and S are asymptotically (cid:54) (cid:54) n n n − n (cid:62) uncorrelated for 3 m 26 and their correlation ﬂuctuates (between 1 and 1) for m 27; see Figure 1 for an illustration. Figure 1: The periodic functions F (2πt) for m = 27, . . . , 100 (left) and F (β log n) for m = ρ ρ 27, 54, . . . , 270 (right). One reason why the above result (1) may seem less or even counter-intuitive is because of the seemingly strong dependence of N on S in the recursive equations satisﬁed by both n n random variables (cid:40) · · · S =d S(1) + + S(m) + 1, n I1 · · · Im · · · (2) N =d N(1) + + N(m) + S(1) + + S(m), n I1 Im I1 Im where the (S(r), N(r))’s are independent copies of (S , N ), respectively, also independent i i i i of (I , . . . , I ), and 1 m 2 ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Introduction

text: The

text: m-ary

text: search

text: trees

text: are

text: a

text: class

text: of

text: data

text: structures

text: introduced

text: by

text: Muntz

text: and

text: Uzgalis

text: in

text: in

text: computer

text: algorithms

text: to

text: support

text: efﬁcient

text: searching

text: and

text: sorting

text: of

text: data;

text: see

text: the

text: next

text: section

text: for

text: more

text: details.

text: When

text: constructed

text: from

text: a

text: random

text: permutation

text: of

text: n

text: elements,

text: the

text: space

text: requirement

text: (total

text: number

text: of

text: nodes

text: to

text: store

text: the

text: input)

text: S

text: of

text: such

text: random

text: m-ary

text: search

text: trees

text: n

text: (m

text: is

text: known

text: to

text: exhibit

text: a

text: phase

text: change

text: phenomenon:

text: its

text: distribution

text: is

text: asymptotically

text: Gaussian

text: for

text: large

text: n

text: when

text: the

text: branching

text: factor

text: m

text: satisﬁes

text: m

text: but

text: does

text: not

text: approach

text: a

text: limit

text: law

text: when

text: m

text: see

text: and

text: the

text: references

text: therein.

text: On

text: the

text: other

text: hand,

text: it

text: is

text: also

text: known

text: that

text: the

text: total

text: key

text: path

text: length

text: K

text: (the

text: sum

text: over

text: all

text: distances

text: from

text: the

text: root

text: to

text: n

text: any

text: key)

text: does

text: not

text: change

text: its

text: limiting

text: behavior

text: when

text: m

text: varies,

text: and

text: tends

text: asymptotically,

text: after

text: properly

text: centered

text: and

text: normalized,

text: to

text: a

text: limit

text: law

text: for

text: each

text: m

text: Another

text: closely

text: related

text: shape

text: measure,

text: the

text: total

text: node

text: path

text: length

text: N

text: (summing

text: over

text: all

text: distances

text: from

text: the

text: root

text: to

text: any

text: node)

text: n

text: also

text: follows

text: asymptotically

text: a

text: very

text: similar

text: behavior.

text: Our

text: motivating

text: question

text: was

text: “how

text: does

text: K

text: or

text: N

text: depend

text: on

text: S

text: Surprisingly,

text: despite

text: n

text: n

text: n

text: the

text: strong

text: dependence

text: of

text: the

text: deﬁnition

text: of

text: N

text: on

text: S

text: (see

text: we

text: show

text: that

text: the

text: correlation

text: n

text: n

text: coefﬁcient

text: ρ(S

text: N

text: satisﬁes

text: n

text: n

text: if

text: m

text: ρ(S

text: N

text: n

text: n

text: F

text: (β

text: log

text: n),

text: if

text: m

text: ρ

text: where

text: F

text: (t)

text: is

text: a

text: function

text: and

text: β

text: β

text: is

text: a

text: structural

text: constant

text: depending

text: on

text: ρ

text: m

text: m.

text: The

text: same

text: type

text: of

text: results

text: also

text: holds

text: for

text: ρ(S

text: K

text: In

text: words,

text: N

text: and

text: S

text: are

text: asymptotically

text: n

text: n

text: n

text: n

text: uncorrelated

text: for

text: m

text: and

text: their

text: correlation

text: ﬂuctuates

text: (between

text: and

text: for

text: m

text: see

text: Figure

text: for

text: an

text: illustration.

text: Figure

text: The

text: periodic

text: functions

text: F

text: for

text: m

text: (left)

text: and

text: F

text: (β

text: log

text: n)

text: for

text: m

text: ρ

text: ρ

text: (right).

text: One

text: reason

text: why

text: the

text: above

text: result

text: may

text: seem

text: less

text: or

text: even

text: counter-intuitive

text: is

text: because

text: of

text: the

text: seemingly

text: strong

text: dependence

text: of

text: N

text: on

text: S

text: in

text: the

text: recursive

text: equations

text: satisﬁed

text: by

text: both

text: n

text: n

text: random

text: variables

text: S

text: =d

text: S(m)

text: n

text: Im

text: N

text: =d

text: N(m)

text: S(m),

text: n

text: Im

text: Im

text: where

text: the

text: (S(r),

text: N(r))’s

text: are

text: independent

text: copies

text: of

text: (S

text: N

text: respectively,

text: also

text: independent

text: i

text: i

text: i

text: i

text: of

text: (I

text: I

text: and

text: m

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:0) (cid:1) (cid:54) (cid:54) (cid:54) (cid:54) where, as in (5)–(7), the Q(r)’s are distributed as Q for all 1 r m and 0 j − j j n m + 1, and the Q(r) (cid:54) (cid:54) − are independent for r = 1, . . . , m and independent of j 0 j n m+1 (I , . . . , I ). The recurrence satisﬁed by the pair Z(cid:18) := (K , S(cid:19)) is 1 n (cid:88) (cid:104) (cid:105) (cid:16) (cid:17) n n n − 1 0 t n m + 1 (cid:62) (Z )t =d Z(r) + , (n m), (13) n (cid:54) (cid:54) 0 1 Ir 1 1 r m with conditions on independence and identical distributions similar to (12). 3.2 Asymptotic transfer and Dirichlet integrals Starting from the distributional recurrences (5) and (6), we see that all centered and non- (cid:0) (cid:1) centered moments satisfy the sam(cid:88)e recurrence of the following type (cid:0) (cid:1) − − n 1 j − a = m π a + b , π = m 2 , (14) n n,j j n n,j n (cid:54) (cid:54) − − 0 j n m+1 m 1 (cid:62) − { } for n m 1, where b (cid:62) − is a given sequence. The asymptotics of a can be n n m 1 n systematically characterized by that of b through the use of the following transfer techniques; n see Proposition 7 in [8] and Theorem 2.4 in [14] for details. Proposition 3.1. Assume that a satisﬁes (14) with ﬁnite initial conditions a , . . . , a − . Deﬁne (cid:54) (cid:54) − n 0 m 2 b := a for 0 n m 2. n n (cid:12) (cid:12) (i) Assume bn = c(n + 1) + tn, where c ∈ C. Th(cid:12)(cid:12)e(cid:88)n the cond(cid:12)(cid:12) itions (cid:12) (cid:12) (cid:12) (cid:12) − ∞ t = o(n) and t n 2 < n n (cid:62) n 1 are both necessary and sufﬁcient for (cid:48) a = 2cφnH + c n + o(n), (cid:88) n n where (cid:48) t c − − c = 2φ j + 2cφ + 2c(H(2) 1)φ2; (j + 1)(j + 2) 2 m (cid:62) j 0 ∼ (ii) if b cnv, where v > 1, then n ∼ c a − nv. n 1 m!Γ(v+1) Γ(v+m) (cid:12) (cid:12) In particular, wh(cid:88)en c = 0 in (i), then we see that an is asympto(cid:12)(cid:12)(cid:88)tically line(cid:12)(cid:12)ar (cid:12) (cid:12) (cid:12) (cid:12) a ∼ b − ∞ n 2φ j iff b = o(n) and b n 2 < . n n n (j + 1)(j + 2) (cid:62) (cid:62) j 0 n 1 11 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where,

text: as

text: in

text: the

text: Q(r)’s

text: are

text: distributed

text: as

text: Q

text: for

text: all

text: r

text: m

text: and

text: j

text: j

text: j

text: n

text: m

text: and

text: the

text: Q(r)

text: are

text: independent

text: for

text: r

text: m

text: and

text: independent

text: of

text: j

text: j

text: n

text: (I

text: I

text: The

text: recurrence

text: satisﬁed

text: by

text: the

text: pair

text: (K

text: is

text: n

text: n

text: n

text: n

text: t

text: n

text: m

text: (Z

text: )t

text: =d

text: Z(r)

text: (n

text: m),

text: n

text: Ir

text: r

text: m

text: with

text: conditions

text: on

text: independence

text: and

text: identical

text: distributions

text: similar

text: to

text: Asymptotic

text: transfer

text: and

text: Dirichlet

text: integrals

text: Starting

text: from

text: the

text: distributional

text: recurrences

text: and

text: we

text: see

text: that

text: all

text: centered

text: and

text: non-

text: centered

text: moments

text: satisfy

text: the

text: recurrence

text: of

text: the

text: following

text: type

text: n

text: j

text: a

text: m

text: π

text: a

text: b

text: π

text: m

text: n

text: n,j

text: j

text: n

text: n,j

text: n

text: j

text: n

text: m

text: for

text: n

text: m

text: where

text: b

text: is

text: a

text: given

text: sequence.

text: The

text: asymptotics

text: of

text: a

text: can

text: be

text: n

text: n

text: m

text: n

text: systematically

text: characterized

text: by

text: that

text: of

text: b

text: through

text: the

text: use

text: of

text: the

text: following

text: transfer

text: techniques;

text: n

text: see

text: Proposition

text: in

text: and

text: Theorem

text: in

text: for

text: details.

text: Proposition

text: Assume

text: that

text: a

text: satisﬁes

text: with

text: ﬁnite

text: initial

text: conditions

text: a

text: a

text: Deﬁne

text: n

text: m

text: b

text: a

text: for

text: n

text: m

text: n

text: n

text: (i)

text: Assume

text: bn

text: c(n

text: tn,

text: where

text: c

text: C.

text: the

text: itions

text: t

text: o(n)

text: and

text: t

text: n

text: n

text: n

text: n

text: are

text: both

text: necessary

text: and

text: sufﬁcient

text: for

text: a

text: c

text: n

text: o(n),

text: n

text: n

text: where

text: t

text: c

text: c

text: 2φ

text: j

text: (j

text: m

text: j

text: (ii)

text: if

text: b

text: cnv,

text: where

text: v

text: then

text: n

text: c

text: a

text: nv.

text: n

text: Γ(v+m)

text: In

text: particular,

text: c

text: in

text: (i),

text: then

text: we

text: see

text: that

text: an

text: is

text: a

text: b

text: n

text: 2φ

text: j

text: iff

text: b

text: o(n)

text: and

text: b

text: n

text: n

text: n

text: n

text: (j

text: j

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3.3 Correlation between the space requirement and KPL We are now ready to prove Theorem 2.1. Expected values of S(cid:62)n an−d Kn. For c(cid:88)onvenience, let µn := E(Sn) and κn := E(Kn). Then, by (5) and (6), for n m 1 (cid:88) µ = m π µ + 1, n n,j j (cid:54) (cid:54) − 0 j n m+1 − κ = m π κ + n m + 1, n n,j j (cid:54) (cid:54) − 0 j n m+1 (cid:54) (cid:54) − (cid:54) (cid:54) − with the initial conditions µ = κ = 0 for 0 n m 2 and µ = 1 for 1 n m 2. 0 n n By applying Proposition 3.1(i), we obtain ∼ µ φn, and κ = 2φn log n + c n + o(n), (18) n n 1 for some constant c whose value matters less; see (21) below. The latter approximation 1 is sufﬁcient for all our purposes, but the former is not and we need the following stronger expansion (see [8, 31, 30]) (cid:88) − 1 A − − µ = φ(n + 1) − + k nλk 1 + o(nα 1), (19) n m 1 Γ(λ ) (cid:54) (cid:54) k 2 k 3 − where λ = α + iβ and λ := α iβ and 2 3 (cid:80) 1 A = − . (20) k λ (λ 1) (cid:54) (cid:54) − 1 k k 0 j m 2 j+λ k (cid:54) (cid:54) − Note that for 3 m 13 the constant term 1− (together with φ) is the second-order m 1 term on the right-hand side of (19), while for larger m, it is absorbed in the o-term. On the other hand, although the explicit expression of c is not needed in this paper, we 1 provide its expression here since the known ones (see [29, 30]) are less explicit and it can be easily obtained from Proposition 3.1: − − − c = 1 4φ + 2φ2(H(2) 1) + γ. (21) 1 2 m Variance and covariance. To compute the asymptotics of the covariance, we ﬁrst derive the corresponding recurrences and then apply Proposition 3.1 of asymptotic transfer. (cid:16) (cid:17) − − First, let S¯ = S µ and K¯ = K κ . We consider the moment-generating function n n n n n n P¯ (u, v) := E eS¯nu+K¯nv . n 13 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Correlation

text: between

text: the

text: space

text: requirement

text: and

text: KPL

text: We

text: are

text: now

text: ready

text: to

text: prove

text: Theorem

text: Expected

text: values

text: of

text: an−d

text: Kn.

text: For

text: let

text: µn

text: E(Sn)

text: and

text: κn

text: E(Kn).

text: Then,

text: by

text: and

text: for

text: n

text: m

text: µ

text: m

text: π

text: µ

text: n

text: n,j

text: j

text: j

text: n

text: κ

text: m

text: π

text: κ

text: n

text: m

text: n

text: n,j

text: j

text: j

text: n

text: with

text: the

text: initial

text: conditions

text: µ

text: κ

text: for

text: n

text: m

text: and

text: µ

text: for

text: n

text: m

text: n

text: n

text: By

text: applying

text: Proposition

text: we

text: obtain

text: µ

text: φn,

text: and

text: κ

text: log

text: n

text: c

text: n

text: o(n),

text: n

text: n

text: for

text: some

text: constant

text: c

text: whose

text: value

text: matters

text: less;

text: see

text: below.

text: The

text: latter

text: approximation

text: is

text: sufﬁcient

text: for

text: all

text: our

text: purposes,

text: but

text: the

text: former

text: is

text: not

text: and

text: we

text: need

text: the

text: following

text: stronger

text: expansion

text: (see

text: A

text: µ

text: φ(n

text: k

text: nλk

text: o(nα

text: n

text: m

text: Γ(λ

text: k

text: k

text: where

text: λ

text: α

text: iβ

text: and

text: λ

text: α

text: iβ

text: and

text: A

text: k

text: λ

text: (λ

text: k

text: k

text: j

text: m

text: j+λ

text: k

text: Note

text: that

text: for

text: m

text: the

text: constant

text: term

text: 1−

text: (together

text: with

text: φ)

text: is

text: the

text: second-order

text: m

text: term

text: on

text: the

text: right-hand

text: side

text: of

text: while

text: for

text: larger

text: m,

text: it

text: is

text: absorbed

text: in

text: the

text: o-term.

text: On

text: the

text: other

text: hand,

text: although

text: the

text: explicit

text: expression

text: of

text: c

text: is

text: not

text: needed

text: in

text: this

text: paper,

text: we

text: provide

text: its

text: expression

text: here

text: since

text: the

text: known

text: ones

text: (see

text: are

text: less

text: explicit

text: and

text: it

text: can

text: be

text: easily

text: obtained

text: from

text: Proposition

text: c

text: 4φ

text: γ.

text: m

text: Variance

text: and

text: covariance.

text: To

text: compute

text: the

text: asymptotics

text: of

text: the

text: covariance,

text: we

text: ﬁrst

text: derive

text: the

text: corresponding

text: recurrences

text: and

text: then

text: apply

text: Proposition

text: of

text: asymptotic

text: transfer.

text: First,

text: let

text: S¯

text: S

text: µ

text: and

text: K¯

text: K

text: κ

text: We

text: consider

text: the

text: moment-generating

text: function

text: n

text: n

text: n

text: n

text: n

text: n

text: P¯

text: (u,

text: v)

text: E

text: eS¯nu+K¯nv

text: n

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:13) (cid:13) (cid:18) (cid:18) (cid:18) (cid:19)(cid:19)(cid:19) Using the triangle inequ(cid:13)(cid:13)ali(cid:88)ty and w(cid:101)ritin(cid:16)g the(cid:17)components as Yn = (Yn,1,(cid:13)(cid:13)Yn,2), we obtain (cid:13) (cid:13) (cid:13) (cid:13) (cid:54) (cid:13) t − (cid:60) X(r) (cid:13) ∆(n) (cid:13) (cid:88) A(n(cid:18)) Y (r(cid:18)) (cid:19)(cid:19)C(n) (cid:18) (cid:18) (cid:19)(cid:19)(cid:13) 1(cid:54)(cid:13)(cid:13)(cid:13)r(cid:54)m r Ir(n) r Λ(r) 2 (cid:13)(cid:13)(cid:13) (cid:13)(cid:60) X(r) (cid:13) − (cid:60) X(r) + (cid:88) (cid:13)(cid:13) Cr(n) Λ(r) (cid:13)(cid:13) (cid:13)(cid:13) Br((cid:18)n) (cid:19)Λ(cid:13)(cid:13)(r) 1(cid:54)r(cid:54)m(cid:13)(cid:13) (cid:13)(cid:13) (cid:13)(cid:13) (cid:13)(cid:13) 2 − (I(n))α 1 − b + r Y (r) + b(n) . 1(cid:54)r(cid:54)m n Ir(n),2 2 0 2 → ∞ The second and the fourth summand on the right-hand side tend to zero as n by (30) and (32). For the third summand, note that the asymptotic behavior of the normalized size Y of n,2 m-ary search trees is covered by Theorem 1, eq. (2) in [8]. In particular, from that theorem we (cid:107) (cid:107) ∞ − obtain sup (cid:62) Y < . Taking into account the prefactor (I(n))α 1/n and conditioning n 1 n,2 2 r on Ir(n), we ﬁnd that the third summand(cid:16)also t(cid:17)ends to(cid:18)zero. (cid:18) (cid:19)(cid:19) (cid:62) − To bound the ﬁrst summand in t(cid:101)he latter display, we write, for r = 1, . . . , m and n m 1, t − (cid:60) X(r) W (n) := A(n) Y (r) C(n) r r Ir(n) r Λ(r) and d(cid:13)(cid:13)en(cid:88)ote the co(cid:13)(cid:13)mponen(cid:34)ts (cid:88)of W(cid:110)r(n) by Wr(n) = (Wr(,n1)(cid:111), Wr((cid:88),n2)).(cid:110)For r = 1, . . . , m, we hav(cid:111)e(cid:35) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 E E W (n) = (W (n))2 + (W (n))2 + W (n)W (n) + W (n)W (n) . r r,1 r,2 r,1 s,1 r,2 s,2 (cid:54) (cid:54) (cid:54) (cid:54) (cid:54) 1 r m 1 r m r=s (35) (cid:104) (cid:105) We bound the three types of terms individually. First, for the dominant term   (cid:32) (cid:33) (cid:32) (cid:33) E (W (n))2 + (W(cid:16)(n))2 (cid:17) (cid:16) (cid:0) (cid:1)(cid:17) r,1 r,2  − 2 2(α 1) = E Ir(n) Y (r) − X(r) 2 + Ir(n) Y (r) − (cid:60) (I(n))iβΛ(r) 2 n Ir(n),1 n Ir(n),2 r 22 ##LTLine## ##LTLine## ##LTLine##

text: Using

text: the

text: triangle

text: and

text: as

text: Yn

text: we

text: obtain

text: t

text: X(r)

text: ∆(n)

text: Y

text: r

text: Ir(n)

text: r

text: Λ(r)

text: X(r)

text: X(r)

text: Cr(n)

text: Λ(r)

text: (I(n))α

text: b

text: r

text: Y

text: (r)

text: b(n)

text: n

text: The

text: second

text: and

text: the

text: fourth

text: summand

text: on

text: the

text: right-hand

text: side

text: tend

text: to

text: zero

text: as

text: n

text: by

text: and

text: For

text: the

text: third

text: summand,

text: note

text: that

text: the

text: asymptotic

text: behavior

text: of

text: the

text: normalized

text: size

text: Y

text: of

text: m-ary

text: search

text: trees

text: is

text: covered

text: by

text: Theorem

text: eq.

text: in

text: In

text: particular,

text: from

text: that

text: theorem

text: we

text: obtain

text: sup

text: Y

text: Taking

text: into

text: account

text: the

text: prefactor

text: (I(n))α

text: and

text: conditioning

text: n

text: r

text: on

text: Ir(n),

text: we

text: ﬁnd

text: that

text: the

text: third

text: To

text: bound

text: the

text: ﬁrst

text: summand

text: in

text: latter

text: display,

text: we

text: write,

text: for

text: r

text: m

text: and

text: n

text: m

text: t

text: X(r)

text: W

text: (n)

text: A(n)

text: Y

text: (r)

text: C(n)

text: r

text: r

text: Ir(n)

text: r

text: Λ(r)

text: and

text: the

text: by

text: Wr(n)

text: r

text: m,

text: we

text: E

text: E

text: W

text: (n)

text: (W

text: (W

text: W

text: (n)W

text: (n)

text: W

text: (n)W

text: (n)

text: r

text: r

text: m

text: r

text: m

text: r=s

text: We

text: bound

text: the

text: three

text: types

text: of

text: terms

text: individually.

text: First,

text: for

text: the

text: dominant

text: term

text: E

text: (W

text: E

text: Ir(n)

text: Y

text: (r)

text: X(r)

text: Ir(n)

text: Y

text: (r)

text: (I(n))iβΛ(r)

text: n

text: n

text: r

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: (cid:32) (cid:32) and (cid:60) C eiz (cid:37) + 2t + 1 (cid:33)(cid:33) 2 2 G (z) = 2 Γ((cid:37) ) t + 1 2 − − − − ((cid:37) + 2t + 1)ψ((cid:37) + 2t + 2) ((cid:37) + t)ψ((cid:37) + t + 1) (t + 1)(H γ) 2 2 2 − 2 t+1 , (t + 1)(H H ) 2t+2 t+1 (cid:32) (cid:33) respectively. Moreover, we have 1 2t + 3 − t + 2 − π2 D = − H(2) H(2) . X (H H )2 t + 1 2t+2 t + 1 t+1 6 2t+2 t+1 The limit law for the normalized TPL of random FBBSTs was ﬁrst shown in the dissertation of S Bruhn, [5]; see also [4, 8, 34, 40]. The phase change of the limit law of the normalized was n ﬁrst discovered in [8]. S X V To describe the joint limiting behavior of and , we denote by a random variable that n n is the median of (2t + 1) independent, identically distributed uniform [0, 1] random variables, i.e., a Beta(t + 1, t + 1) distribution. We deﬁne the map T by (cid:18)(cid:20) (cid:21) (cid:18) (cid:19) (cid:20) med (cid:21) (cid:18) (cid:19) (cid:18) (cid:19)(cid:19) MR×C → MR×C T : , med V − V L (cid:55)→ L 0 Z(1) 1 0 Z(2) b (Z, W ) V + − V + M , 0 (cid:37)2 W (1) 0 (1 )(cid:37)2 W (2) 0 with conditions on independence and distributions as in (33) and 1 V V − V − V b := 1 + − ( log + (1 ) log(1 )) . M H H 2t+2 t+1 (cid:62) Then Lemma 4.1 and its proof also apply to the map T as long as t 59. The normalization med used is given by (cid:18) (cid:19) X − E X S − Y ( ) C n (cid:62) n := n n n , nnαt−11 , (n 1). (47) (cid:62) We have the following asymptotic behavior for t 59. Rewrite (46) as E S − (cid:60) − ( ) = C (n + 1) 1 + (ϑn(cid:37)2) + o(nαt 1), (48) n 1 (cid:60) where ϑ := 2 (C /Γ((cid:37) )). 2 2 (cid:62) Y Theorem 5.2. Assume t 59. Let be the normalization of TPL and the number of non-leaf n L nodes in a random FBBST deﬁned in (47). Denote by (X , Λ ) the unique ﬁxed point of MR×C med med (cid:61) the restriction of T to(cid:0) ((0, ϑ)) with ϑ deﬁ(cid:1)ned in (48). Then, denoting by β := ((cid:37) ), med 2 t 2 we have Y (cid:60) → → ∞ (cid:96) , (X , (niβtΛ )) 0, (n ). 2 n med med 32 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: and

text: C

text: eiz

text: G

text: (z)

text: t

text: t

text: (t

text: γ)

text: (t

text: H

text: respectively.

text: Moreover,

text: we

text: have

text: t

text: π2

text: D

text: X

text: (H

text: H

text: t

text: t

text: The

text: limit

text: law

text: for

text: the

text: normalized

text: TPL

text: of

text: random

text: FBBSTs

text: was

text: ﬁrst

text: shown

text: in

text: the

text: dissertation

text: of

text: S

text: Bruhn,

text: see

text: also

text: The

text: phase

text: change

text: of

text: the

text: limit

text: law

text: of

text: the

text: normalized

text: was

text: n

text: ﬁrst

text: discovered

text: in

text: S

text: X

text: V

text: To

text: describe

text: the

text: joint

text: limiting

text: behavior

text: of

text: and

text: we

text: denote

text: by

text: a

text: random

text: variable

text: that

text: n

text: n

text: is

text: the

text: median

text: of

text: independent,

text: identically

text: distributed

text: uniform

text: random

text: variables,

text: i.e.,

text: a

text: Beta(t

text: t

text: distribution.

text: We

text: deﬁne

text: the

text: map

text: T

text: by

text: med

text: MR×C

text: MR×C

text: T

text: med

text: V

text: V

text: L

text: L

text: b

text: (Z,

text: W

text: V

text: V

text: M

text: W

text: W

text: with

text: conditions

text: on

text: independence

text: and

text: distributions

text: as

text: in

text: and

text: V

text: V

text: V

text: V

text: b

text: log

text: M

text: H

text: H

text: Then

text: Lemma

text: and

text: its

text: proof

text: also

text: apply

text: to

text: the

text: map

text: T

text: as

text: long

text: as

text: t

text: The

text: normalization

text: med

text: used

text: is

text: given

text: by

text: X

text: E

text: X

text: S

text: Y

text: C

text: n

text: n

text: n

text: n

text: n

text: (n

text: We

text: have

text: the

text: following

text: asymptotic

text: behavior

text: for

text: t

text: Rewrite

text: as

text: E

text: S

text: C

text: (n

text: o(nαt

text: n

text: where

text: ϑ

text: (C

text: Y

text: Theorem

text: Assume

text: t

text: Let

text: be

text: the

text: normalization

text: of

text: TPL

text: and

text: the

text: number

text: of

text: non-leaf

text: n

text: L

text: nodes

text: in

text: a

text: random

text: FBBST

text: deﬁned

text: in

text: Denote

text: by

text: (X

text: Λ

text: the

text: unique

text: ﬁxed

text: point

text: of

text: MR×C

text: med

text: med

text: the

text: restriction

text: of

text: T

text: ϑ))

text: with

text: ϑ

text: in

text: Then,

text: denoting

text: by

text: β

text: med

text: t

text: we

text: have

text: Y

text: (X

text: (niβtΛ

text: (n

text: n

text: med

text: med

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: where χ , c , c− (which is the conjugate of c ) are given in [7], and 2e2πi/d = αˆ + 1 + iβˆ. d + + Moreover, the asymptotic transfer results in [7] also lead to the asymptotic approximation (see also [16]) E 2 (Ξ ) = n log n + cˆn + o(n), n d for some explicitly computable constant cˆ. In a similar manner, we can characterize the asymp- totics of the variances and the covariance. Theorem 5.4. For the number of lea(cid:40)ves L and the internal path length Ξ in random d- n n dimensional quadtrees, we have (cid:0) (cid:1) (cid:54) (cid:54) V ∼ (cid:40)E n, if 1 d 8; L (L ) (cid:62) n P1(cid:0)βˆ log n(cid:1)n2αˆ, if d 9, (cid:54) (cid:54) ∼ E n, if 1 d 5; R Cov(Ξ , L ) (cid:62) n n P βˆ log n nαˆ+1, if d 6, 2 V ∼ (Ξ ) E n2, n X where E , E are suitable constants, βˆ := 2 sin 2π, and all other constants and functions are L R d given below. The periodic functions above are given by (2αˆ + 1)d(cid:32) | | − (cid:33) P (z) = 2 − c 2c (αˆ + iβˆ, αˆ iβˆ) 1 (2αˆ + 1)d 2d + L (cid:60) (2αˆ + 2iβˆ + 1)d + 2 − c2 c (αˆ + iβˆ, αˆ + iβˆ)e2iz , (2αˆ + 2iβˆ + 1)d 2d + L − − (cid:18) (cid:19) where c (u, v) = 1 η(0, u) η(0, v) + 2dη(u, v) with L 1 Γ(u + 1)Γ(v + 1) d η(u, v) := + (cid:32) u + v + 1 Γ(u + v + 2) (cid:33) and (cid:60) (αˆ + iβˆ + 2)d P (z) = 2 − c c (αˆ + iβˆ)eiz , 2 (αˆ + iβˆ + 2)d 2d + K (cid:12) (cid:12) (cid:12) where 2d+1 ∂ c (u, v) = η(0, u) + η(u, v) . K d ∂v v=1 Finally, − 3d · 21 2π2 E = − . X 3d 2d 9d The limit law for the normalized internal path length of random d-dimensional quadtrees was ﬁrst obtained in [38]; see also [4, 7, 34]. The asymptotic behavior of the normalized number of leaves together with its phase change was ﬁrst discovered in [7]; see also [9, 23, 24, 25] for closely related types of phase changes. 34 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: where

text: χ

text: c

text: c−

text: (which

text: is

text: the

text: conjugate

text: of

text: c

text: are

text: given

text: in

text: and

text: αˆ

text: iβˆ.

text: d

text: Moreover,

text: the

text: asymptotic

text: transfer

text: results

text: in

text: also

text: lead

text: to

text: the

text: asymptotic

text: approximation

text: (see

text: also

text: E

text: (Ξ

text: n

text: log

text: n

text: cˆn

text: o(n),

text: n

text: d

text: for

text: some

text: explicitly

text: computable

text: constant

text: cˆ.

text: In

text: a

text: similar

text: manner,

text: we

text: can

text: characterize

text: the

text: asymp-

text: totics

text: of

text: the

text: variances

text: and

text: the

text: covariance.

text: Theorem

text: For

text: the

text: number

text: of

text: L

text: and

text: the

text: internal

text: path

text: length

text: Ξ

text: in

text: random

text: d-

text: n

text: n

text: dimensional

text: quadtrees,

text: we

text: have

text: V

text: n,

text: if

text: d

text: L

text: (L

text: n

text: log

text: if

text: d

text: E

text: n,

text: if

text: d

text: R

text: Cov(Ξ

text: L

text: n

text: n

text: P

text: βˆ

text: log

text: n

text: if

text: d

text: V

text: (Ξ

text: E

text: n

text: X

text: where

text: E

text: E

text: are

text: suitable

text: constants,

text: βˆ

text: sin

text: and

text: all

text: other

text: constants

text: and

text: functions

text: are

text: L

text: R

text: d

text: given

text: below.

text: The

text: periodic

text: functions

text: above

text: are

text: given

text: by

text: (2αˆ

text: P

text: (z)

text: c

text: (αˆ

text: iβˆ,

text: αˆ

text: iβˆ)

text: (2αˆ

text: L

text: (2αˆ

text: 2iβˆ

text: c

text: (αˆ

text: iβˆ,

text: αˆ

text: (2αˆ

text: 2iβˆ

text: L

text: where

text: c

text: (u,

text: v)

text: u)

text: v)

text: v)

text: with

text: L

text: Γ(u

text: d

text: η(u,

text: v)

text: u

text: v

text: Γ(u

text: v

text: and

text: (αˆ

text: iβˆ

text: P

text: (z)

text: c

text: c

text: (αˆ

text: iβˆ)eiz

text: (αˆ

text: iβˆ

text: K

text: where

text: c

text: (u,

text: v)

text: u)

text: η(u,

text: v)

text: K

text: d

text: ∂v

text: Finally,

text: E

text: X

text: The

text: limit

text: law

text: for

text: the

text: normalized

text: internal

text: path

text: length

text: of

text: random

text: d-dimensional

text: quadtrees

text: was

text: ﬁrst

text: obtained

text: in

text: see

text: also

text: The

text: asymptotic

text: behavior

text: of

text: the

text: normalized

text: number

text: of

text: leaves

text: together

text: with

text: its

text: phase

text: change

text: was

text: ﬁrst

text: discovered

text: in

text: see

text: also

text: for

text: closely

text: related

text: types

text: of

text: phase

text: changes.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: [35] R. Muntz and R. Uzgalis. Dynamic storage allocation for binary search trees in a two- level memory. Proceedings of the Princeton Conference on Information Sciences and Systems, 4:345–349, 1971. [36] R. Neininger. On a multivariate contraction method for random recursive structures with applications to Quicksort. Random Structures Algorithms, 19(3-4):498–524, 2001. [37] R. Neininger. Reﬁned quicksort asymptotics. Random Structures Algorithms, 46(2):346– 361, 2015. [38] R. Neininger and L. Ru¨schendorf. On the internal path length of d-dimensional quad trees. Random Structures Algorithms, 15(1):25–41, 1999. [39] R. Neininger and L. Ru¨schendorf. A general limit theorem for recursive algorithms and combinatorial structures. Ann. Appl. Probab., 14(1):378–418, 2004. [40] U. Ro¨sler. On the analysis of stochastic divide and conquer algorithms. Algorithmica, 29(1-2):238–261, 2001. [41] H. Sulzbach. On martingale tail sums for the path length in random trees. http://arXiv:1412.3508, 2014. 39

label: reference

text: R.

text: Muntz

text: and

text: R.

text: Uzgalis.

text: Dynamic

text: storage

text: allocation

text: for

text: binary

text: search

text: trees

text: in

text: a

text: two-

text: level

text: memory.

text: Proceedings

text: of

text: the

text: Princeton

text: Conference

text: on

text: Information

text: Sciences

text: and

text: Systems,

text: R.

text: Neininger.

text: On

text: a

text: multivariate

text: contraction

text: method

text: for

text: random

text: recursive

text: structures

text: with

text: applications

text: to

text: Quicksort.

text: Random

text: Structures

text: Algorithms,

text: R.

text: Neininger.

text: Reﬁned

text: quicksort

text: asymptotics.

text: Random

text: Structures

text: Algorithms,

text: R.

text: Neininger

text: and

text: L.

text: Ru¨schendorf.

text: On

text: the

text: internal

text: path

text: length

text: of

text: d-dimensional

text: quad

text: trees.

text: Random

text: Structures

text: Algorithms,

text: R.

text: Neininger

text: and

text: L.

text: Ru¨schendorf.

text: A

text: general

text: limit

text: theorem

text: for

text: recursive

text: algorithms

text: and

text: combinatorial

text: structures.

text: Ann.

text: Appl.

text: Probab.,

text: U.

text: Ro¨sler.

text: On

text: the

text: analysis

text: of

text: stochastic

text: divide

text: and

text: conquer

text: algorithms.

text: Algorithmica,

text: H.

text: Sulzbach.

text: On

text: martingale

text: tail

text: sums

text: for

text: the

text: path

text: length

text: in

text: random

text: trees.


text: where α has the same meaning as(cid:40)in Introduction; see (4). They also discovered and proved the surprising result for the variance (cid:54) (cid:54) V ∼ C n, if 3 m 26; S (Sn) F (β log n)n2α−2, if m (cid:62) 27, 1 where C is a constant depending on m, F is a π-periodic function given in (24), α + iβ S 1 is the second largest zero (in real part) with β > 0 of the equation Λ(z) = 0 (see (4)), and − (cid:62) 2α 2 > 1 for m 27. See also [9, 25, 33] for a closely related fragmentation model with the (cid:54) (cid:54) same asymptotic behavior. A central limit theorem for S was then proved for 3 m 26 in n [28, 31]; see also [30] for more details. Their approach is based on an inductive approximation argument. By the method of moments, two authors of this paper re-proved in [8] the central limit the- (cid:54) (cid:54) orem for S when 3 m 26; the same approach was also used to establish the nonexistence n of a limit law for S due to inherent oscillations. Moreover, the convergence rates to the normal n distribution were characterized in [22] by a reﬁned method of moments, which undergo further change of behaviors. Then several different approaches were developed in the literature for a deeper understand- ing of the “phase change” at m = 26; these include martingale [6], renewal theory [25], urn models [23, 32], contraction method [13, 39], method of moments [22], statistical physics [9, 33], etc. (cid:62) On the other hand, the KPL for general m 2 was ﬁrst studied by Mahmoud [29] and he proved E (cid:80) (K ) = 2φn log n + c n + o(n), n 1 § for some explicitly computable constant c ; see (21). The variance was computed in [30, 3.5] 1 − and satisﬁes (Hm(2) := 1(cid:54)j(cid:54)m j 2) (cid:16) (cid:17) V(K ) ∼ C n2, where C = 4φ2 (m+1)H−m(2)−2 − π2 . (8) n K K m 1 6 The corresponding limit law was characterized in [38] by the contraction method − E K (K ) −→ n n d K, (9) n where K is given by the recursive distributional equation (44); see also [4, 34] for a general framework. For NPL N , Broutin and Holmgren [4] proved that n E (N ) = 2φ2n log n + c n + o(n), n 2 for some constant c (for which no numerical value was provided); a series expression of c 2 2 is given in [21, p. 156]. We will give an alternative proof of this result below with tools from [8, 14]. Our approach makes the computation of c feasible (although its exact value is not 2 needed); see (27). 6 ##LTLine## ##LTLine## ##LTLine##

text: where

text: α

text: has

text: the

text: same

text: meaning

text: Introduction;

text: see

text: They

text: also

text: discovered

text: and

text: proved

text: the

text: surprising

text: result

text: for

text: the

text: variance

text: V

text: C

text: n,

text: if

text: m

text: S

text: (Sn)

text: F

text: (β

text: log

text: if

text: m

text: where

text: C

text: is

text: a

text: constant

text: depending

text: on

text: m,

text: F

text: is

text: a

text: π-periodic

text: function

text: given

text: in

text: α

text: iβ

text: S

text: is

text: the

text: second

text: largest

text: zero

text: (in

text: real

text: part)

text: with

text: β

text: of

text: the

text: equation

text: Λ(z)

text: (see

text: and

text: 2α

text: for

text: m

text: See

text: also

text: for

text: a

text: closely

text: related

text: fragmentation

text: model

text: with

text: the

text: same

text: asymptotic

text: behavior.

text: A

text: central

text: limit

text: theorem

text: for

text: S

text: was

text: then

text: proved

text: for

text: m

text: in

text: n

text: see

text: also

text: for

text: more

text: details.

text: Their

text: approach

text: is

text: based

text: on

text: an

text: inductive

text: approximation

text: argument.

text: By

text: the

text: method

text: of

text: moments,

text: two

text: authors

text: of

text: this

text: paper

text: re-proved

text: in

text: the

text: central

text: limit

text: the-

text: orem

text: for

text: S

text: when

text: m

text: the

text: same

text: approach

text: was

text: also

text: used

text: to

text: establish

text: the

text: nonexistence

text: n

text: of

text: a

text: limit

text: law

text: for

text: S

text: due

text: to

text: inherent

text: oscillations.

text: Moreover,

text: the

text: convergence

text: rates

text: to

text: the

text: normal

text: n

text: distribution

text: were

text: characterized

text: in

text: by

text: a

text: reﬁned

text: method

text: of

text: moments,

text: which

text: undergo

text: further

text: change

text: of

text: behaviors.

text: Then

text: several

text: different

text: approaches

text: were

text: developed

text: in

text: the

text: literature

text: for

text: a

text: deeper

text: understand-

text: ing

text: of

text: the

text: “phase

text: change”

text: at

text: m

text: these

text: include

text: martingale

text: renewal

text: theory

text: urn

text: models

text: contraction

text: method

text: method

text: of

text: moments

text: statistical

text: physics

text: etc.

text: On

text: the

text: other

text: hand,

text: the

text: KPL

text: for

text: general

text: m

text: was

text: ﬁrst

text: studied

text: by

text: Mahmoud

text: and

text: he

text: proved

text: E

text: (K

text: log

text: n

text: c

text: n

text: o(n),

text: n

text: for

text: some

text: explicitly

text: computable

text: constant

text: c

text: see

text: The

text: variance

text: was

text: computed

text: in

text: and

text: satisﬁes

text: j

text: V(K

text: C

text: where

text: C

text: π2

text: n

text: K

text: K

text: m

text: The

text: corresponding

text: limit

text: law

text: was

text: characterized

text: in

text: by

text: the

text: contraction

text: method

text: E

text: K

text: (K

text: n

text: n

text: d

text: K,

text: n

text: where

text: K

text: is

text: given

text: by

text: the

text: recursive

text: distributional

text: equation

text: see

text: also

text: for

text: a

text: general

text: framework.

text: For

text: NPL

text: N

text: Broutin

text: and

text: Holmgren

text: proved

text: that

text: n

text: E

text: (N

text: log

text: n

text: c

text: n

text: o(n),

text: n

text: for

text: some

text: constant

text: c

text: (for

text: which

text: no

text: numerical

text: value

text: was

text: provided);

text: a

text: series

text: expression

text: of

text: c

text: is

text: given

text: in

text: p.

text: We

text: will

text: give

text: an

text: alternative

text: proof

text: of

text: this

text: result

text: below

text: with

text: tools

text: from

text: Our

text: approach

text: makes

text: the

text: computation

text: of

text: c

text: feasible

text: (although

text: its

text: exact

text: value

text: is

text: not

text: needed);

text: see

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: formation. This evaluation function makes it with a coarse search phase that adds or removes possible to construct each community indepen- groups of links by adding or removing nodes dently from all others, which in turn enables per- with all their links, and follow it with ﬁne search vasive overlaps because inner links (links all of phase, namely link-wise memetic evolution or at whose neighbours are community members) of least a link-wise local search. one community can also be inner links of an- 3 The cost function: other community. We then design an algorithm that constructs local communities. ratio node-cut For the ﬁrst step, we followed a suggestion by Evans and Lambiotte (2009) to obtain link 3.1 Node-induced and clusters by clustering vertices in a network’s line link-induced subgraphs graph. We deﬁned a local cost function Ψ(L) Traditionally, the boundary of a community in the line-graph approach which we call ratio is drawn between nodes and therefore cuts the node-cut. It can be used to identify link commu- links between nodes inside and outside the com- nities by ﬁnding local minima in the cost land- munity. If we consider communities as clusters scape. Since Ψ(L) evaluates the boundary be- of links rather than nodes, the perspective must tween a subgraph and the rest of the network, be reversed. While the boundary of a node com- communities can be constructed independently munity cuts links, the boundary of a link com- of all other communities. munity cuts nodes. The cost landscape of Ψ(L) is often very rough A node community is a connected subgraph i.e. has many local minima that may correspond deﬁned by a node set C. It contains all links to very similar subgraphs. Therefore, the reso- existing between nodes in C. A link community lution of the algorithm must be deﬁned by set- is a connected link-induced subgraph. It con- ting a minimum distance (number of links that tains all nodes attached to links of a given set diﬀer) between subgraphs corresponding to dif- L. There can be links existing between a link ferent local minima. We deﬁne the range of a community’s nodes which are not in L. community as a distance in which no subgraph Cost functions of a subgraph can be deﬁned exists that has a lower Ψ-value. by relating a measure of external to a measure of Since the task of ﬁnding communities in large total connectivity. This ratio should be minimal networks is always very complex, heuristics must for well separated and cohesive subgraphs i.e. for be applied. This applies even more strongly to communities. link clustering because networks contain many Node communities can be deﬁned as con- more links than nodes, and particularly to the nected subgraphs corresponding to minima in rough Ψ-landscape. We chose an evolutionary cost landscapes where places correspond to algorithm but accelerate evolution by combin- node-induced subgraphs. Correspondingly, link ing it with a deterministic local search in the communities can be deﬁned as connected sub- cost landscape. This approach is called memetic graphs corresponding to minima in cost land- (Neri, Cotta, and Moscato 2012). Memetic algo- scapes where places correspond to link-induced rithms can also ﬁnd local optima of a local cost subgraphs. function (Vitela and Castan˜os 2012). In the following, we only consider connected In evolutionary algorithms, individuals oc- unweighted graphs G = (V, E). The number of | | cupy places in the cost (or ﬁtness) landscape. edges (or links) is m = E , the number of ver- | | In our local algorithm, populations are sets of tices (or nodes) is n = V . With k we denote i diﬀerent subgraphs. We start with a random the degree of node i. The internal degree of node initialisation of the population of some deﬁnite i, denoted by kin(L), is the number of links at- size. The genetic operators of crossover, mu- i tached to node i which are in link set L. The − tation, and selection are repeatedly applied to external degree of node i is kout(L) = k kin(L). move the population into optima. In memetic i i i 3.2 External connectivity algorithms each crossover and each mutation is followed by a local search. We ﬁrst consider measures of external connec- In large networks exploring the cost landscape tivity of a subgraph which are useful for con- by adding or removing individual links is very structing node or link communities. The sim- time-consuming. We therefore begin the search plest measure of external connectivity of a node- 3

text: formation.

text: This

text: evaluation

text: function

text: makes

text: it

text: with

text: a

text: coarse

text: search

text: phase

text: that

text: adds

text: or

text: removes

text: possible

text: to

text: construct

text: each

text: community

text: indepen-

text: groups

text: of

text: links

text: by

text: adding

text: or

text: removing

text: nodes

text: dently

text: from

text: all

text: others,

text: which

text: in

text: turn

text: enables

text: per-

text: with

text: all

text: their

text: links,

text: and

text: follow

text: it

text: with

text: ﬁne

text: search

text: vasive

text: overlaps

text: because

text: inner

text: links

text: (links

text: all

text: of

text: phase,

text: namely

text: link-wise

text: memetic

text: evolution

text: or

text: at

text: whose

text: neighbours

text: are

text: community

text: members)

text: of

text: least

text: a

text: link-wise

text: local

text: search.

text: one

text: community

text: can

text: also

text: be

text: inner

text: links

text: of

text: an-

text: The

text: cost

text: function:

text: other

text: community.

text: We

text: then

text: design

text: an

text: algorithm

text: that

text: constructs

text: local

text: communities.

text: ratio

text: node-cut

text: For

text: the

text: ﬁrst

text: step,

text: we

text: followed

text: a

text: suggestion

text: by

text: Evans

text: and

text: Lambiotte

text: to

text: obtain

text: link

text: Node-induced

text: and

text: clusters

text: by

text: clustering

text: vertices

text: in

text: a

text: network’s

text: line

text: link-induced

text: subgraphs

text: graph.

text: We

text: deﬁned

text: a

text: local

text: cost

text: function

text: Ψ(L)

text: Traditionally,

text: the

text: boundary

text: of

text: a

text: community

text: in

text: the

text: line-graph

text: approach

text: which

text: we

text: call

text: ratio

text: is

text: drawn

text: between

text: nodes

text: and

text: therefore

text: cuts

text: the

text: node-cut.

text: It

text: can

text: be

text: used

text: to

text: identify

text: link

text: commu-

text: links

text: between

text: nodes

text: inside

text: and

text: outside

text: the

text: com-

text: nities

text: by

text: ﬁnding

text: local

text: minima

text: in

text: the

text: cost

text: land-

text: munity.

text: If

text: we

text: consider

text: communities

text: as

text: clusters

text: scape.

text: Since

text: Ψ(L)

text: evaluates

text: the

text: boundary

text: be-

text: of

text: links

text: rather

text: than

text: nodes,

text: the

text: perspective

text: must

text: tween

text: a

text: subgraph

text: and

text: the

text: rest

text: of

text: the

text: network,

text: be

text: reversed.

text: While

text: the

text: boundary

text: of

text: a

text: node

text: com-

text: communities

text: can

text: be

text: constructed

text: independently

text: munity

text: cuts

text: links,

text: the

text: boundary

text: of

text: a

text: link

text: com-

text: of

text: all

text: other

text: communities.

text: munity

text: cuts

text: nodes.

text: The

text: cost

text: landscape

text: of

text: Ψ(L)

text: is

text: often

text: very

text: rough

text: A

text: node

text: community

text: is

text: a

text: connected

text: subgraph

text: i.e.

text: has

text: many

text: local

text: minima

text: that

text: may

text: correspond

text: deﬁned

text: by

text: a

text: node

text: set

text: C.

text: It

text: contains

text: all

text: links

text: to

text: very

text: similar

text: subgraphs.

text: Therefore,

text: the

text: reso-

text: existing

text: between

text: nodes

text: in

text: C.

text: A

text: link

text: community

text: lution

text: of

text: the

text: algorithm

text: must

text: be

text: deﬁned

text: by

text: set-

text: is

text: a

text: connected

text: link-induced

text: subgraph.

text: It

text: con-

text: ting

text: a

text: minimum

text: distance

text: (number

text: of

text: links

text: that

text: tains

text: all

text: nodes

text: attached

text: to

text: links

text: of

text: a

text: given

text: set

text: diﬀer)

text: between

text: subgraphs

text: corresponding

text: to

text: dif-

text: L.

text: There

text: can

text: be

text: links

text: existing

text: between

text: a

text: link

text: ferent

text: local

text: minima.

text: We

text: deﬁne

text: the

text: range

text: of

text: a

text: community’s

text: nodes

text: which

text: are

text: not

text: in

text: L.

text: community

text: as

text: a

text: distance

text: in

text: which

text: no

text: subgraph

text: Cost

text: functions

text: of

text: a

text: subgraph

text: can

text: be

text: deﬁned

text: exists

text: that

text: has

text: a

text: lower

text: Ψ-value.

text: by

text: relating

text: a

text: measure

text: of

text: external

text: to

text: a

text: measure

text: of

text: Since

text: the

text: task

text: of

text: ﬁnding

text: communities

text: in

text: large

text: total

text: connectivity.

text: This

text: ratio

text: should

text: be

text: minimal

text: networks

text: is

text: always

text: very

text: complex,

text: heuristics

text: must

text: for

text: well

text: separated

text: and

text: cohesive

text: subgraphs

text: i.e.

text: for

text: be

text: applied.

text: This

text: applies

text: even

text: more

text: strongly

text: to

text: communities.

text: link

text: clustering

text: because

text: networks

text: contain

text: many

text: Node

text: communities

text: can

text: be

text: deﬁned

text: as

text: con-

text: more

text: links

text: than

text: nodes,

text: and

text: particularly

text: to

text: the

text: nected

text: subgraphs

text: corresponding

text: to

text: minima

text: in

text: rough

text: Ψ-landscape.

text: We

text: chose

text: an

text: evolutionary

text: cost

text: landscapes

text: where

text: places

text: correspond

text: to

text: algorithm

text: but

text: accelerate

text: evolution

text: by

text: combin-

text: node-induced

text: subgraphs.

text: Correspondingly,

text: link

text: ing

text: it

text: with

text: a

text: deterministic

text: local

text: search

text: in

text: the

text: communities

text: can

text: be

text: deﬁned

text: as

text: connected

text: sub-

text: cost

text: landscape.

text: This

text: approach

text: is

text: called

text: memetic

text: graphs

text: corresponding

text: to

text: minima

text: in

text: cost

text: land-

text: (Neri,

text: Cotta,

text: and

text: Moscato

text: Memetic

text: algo-

text: scapes

text: where

text: places

text: correspond

text: to

text: link-induced

text: rithms

text: can

text: also

text: ﬁnd

text: local

text: optima

text: of

text: a

text: local

text: cost

text: subgraphs.

text: function

text: (Vitela

text: and

text: Castan˜os

text: In

text: the

text: following,

text: we

text: only

text: consider

text: connected

text: In

text: evolutionary

text: algorithms,

text: individuals

text: oc-

text: unweighted

text: graphs

text: G

text: (V,

text: E).

text: The

text: number

text: of

text: cupy

text: places

text: in

text: the

text: cost

text: (or

text: ﬁtness)

text: landscape.

text: edges

text: (or

text: links)

text: is

text: m

text: E

text: the

text: number

text: of

text: ver-

text: In

text: our

text: local

text: algorithm,

text: populations

text: are

text: sets

text: of

text: tices

text: (or

text: nodes)

text: is

text: n

text: V

text: With

text: k

text: we

text: denote

text: i

text: diﬀerent

text: subgraphs.

text: We

text: start

text: with

text: a

text: random

text: the

text: degree

text: of

text: node

text: i.

text: The

text: internal

text: degree

text: of

text: node

text: initialisation

text: of

text: the

text: population

text: of

text: some

text: deﬁnite

text: i,

text: denoted

text: by

text: kin(L),

text: is

text: the

text: number

text: of

text: links

text: at-

text: size.

text: The

text: genetic

text: operators

text: of

text: crossover,

text: mu-

text: i

text: tached

text: to

text: node

text: i

text: which

text: are

text: in

text: link

text: set

text: L.

text: The

text: tation,

text: and

text: selection

text: are

text: repeatedly

text: applied

text: to

text: external

text: degree

text: of

text: node

text: i

text: is

text: kout(L)

text: k

text: kin(L).

text: move

text: the

text: population

text: into

text: optima.

text: In

text: memetic

text: i

text: i

text: i

text: External

text: connectivity

text: algorithms

text: each

text: crossover

text: and

text: each

text: mutation

text: is

text: followed

text: by

text: a

text: local

text: search.

text: We

text: ﬁrst

text: consider

text: measures

text: of

text: external

text: connec-

text: In

text: large

text: networks

text: exploring

text: the

text: cost

text: landscape

text: tivity

text: of

text: a

text: subgraph

text: which

text: are

text: useful

text: for

text: con-

text: by

text: adding

text: or

text: removing

text: individual

text: links

text: is

text: very

text: structing

text: node

text: or

text: link

text: communities.

text: The

text: sim-

text: time-consuming.

text: We

text: therefore

text: begin

text: the

text: search

text: plest

text: measure

text: of

text: external

text: connectivity

text: of

text: a

text: node-


text: 4 Conclusion The paper has reviewed lazy ABC [1], a method to speed up ABC without introducing further ap- proximations to the target distribution. Unlike [1], non-uniform ABC kernels have been considered. This allows a simpler approach to tuning, which provides a comparable three-fold efﬁciency increase in a spatial extremes example. Several extensions to lazy ABC are described in [1]: multiple stopping decisions, choosing h after running the algorithm and a similar scheme for likelihood-based inference. Other potential exten- sions include using the lazy ABC approach in ABC versions of MCMC or SMC algorithms, or focusing on model choice. 5

text: Conclusion

text: The

text: paper

text: has

text: reviewed

text: lazy

text: ABC

text: a

text: method

text: to

text: speed

text: up

text: ABC

text: without

text: introducing

text: further

text: ap-

text: proximations

text: to

text: the

text: target

text: distribution.

text: Unlike

text: non-uniform

text: ABC

text: kernels

text: have

text: been

text: considered.

text: This

text: allows

text: a

text: simpler

text: approach

text: to

text: tuning,

text: which

text: provides

text: a

text: comparable

text: three-fold

text: efﬁciency

text: increase

text: in

text: a

text: spatial

text: extremes

text: example.

text: Several

text: extensions

text: to

text: lazy

text: ABC

text: are

text: described

text: in

text: multiple

text: stopping

text: decisions,

text: choosing

text: h

text: after

text: running

text: the

text: algorithm

text: and

text: a

text: similar

text: scheme

text: for

text: likelihood-based

text: inference.

text: Other

text: potential

text: exten-

text: sions

text: include

text: using

text: the

text: lazy

text: ABC

text: approach

text: in

text: ABC

text: versions

text: of

text: MCMC

text: or

text: SMC

text: algorithms,

text: or

text: focusing

text: on

text: model

text: choice.


text: Mirror, mirror on the wall, tell me, is the error small? Heng Yang Ioannis Patras Queen Mary University of London Queen Mary University of London heng.yang@qmul.ac.uk i.patras@qmul.ac.uk Abstract Do object part localization methods produce bilaterally symmetric results on mirror images? Surprisingly not, even though state of the art methods augment the training set with mirrored images. In this paper we take a closer look into this issue. We ﬁrst introduce the concept of mirrorabil- ity as the ability of a model to produce symmetric results in mirrored images and introduce a corresponding measure, (a) Mirror error 0.2. (b) Mirror error 0.02. namely the mirror error that is deﬁned as the difference be- tween the detection result on an image and the mirror of the detection result on its mirror image. We evaluate the mir- rorability of several state of the art algorithms in two of the most intensively studied problems, namely human pose es- timation and face alignment. Our experiments lead to sev- eral interesting ﬁndings: 1) Surprisingly, most of state of the art methods struggle to preserve the mirror symmetry, (c) Mirror error 0.6. (d) Mirror error 0.02. despite the fact that they do have very similar overall per- Figure 1: Example pairs of localization results on original formance on the original and mirror images; 2) the low mir- (left) and mirror (right) images. First row: Human Pose rorability is not caused by training or testing sample bias - Estimation [24], second row: Face Alignment by RCPR [4]. all algorithms are trained on both the original images and The ﬁrst column (a and c) shows large mirror error and the their mirrored versions; 3) the mirror error is strongly cor- second (b and d) small mirror error. Can we evaluate the related to the localization/alignment error (with correlation performance without knowing the ground truth? coefﬁcients around 0.7). Since the mirror error is calcu- lated without knowledge of the ground truth, we show two eral methods have reported close-to-human performance. interesting applications - in the ﬁrst it is used to guide the This includes localization of objects in images (e.g. pedes- selection of difﬁcult samples and in the second to give feed- trian or face detection) or ﬁne-grained localization of object back in a popular Cascaded Pose Regression method for parts (e.g. face parts localization, body parts localization, face alignment. bird parts localization). Most of those methods augment the training set by mirroring the positive training samples. 1. Introduction However, are these models able to give symmetric results on a mirror image during testing? The evolution of mirror (bilateral) symmetry has pro- In order to answer this question we ﬁrst introduce the foundly impacted animal evolution [7]. As a consequence, concept of mirrorability, i.e., the ability of an algorithm to the overwhelming majority of modern animals (>99%), in- give on a mirror image bilaterally symmetric results, and a cluding humans, exhibit mirror symmetry. As shown in quantitative measure called the mirror error. The latter is Fig. 1, the mirror of an image depicting such objects shows deﬁned as the difference between the detection result on an a meaningful version of the same objects. Taking face im- image and the mirror of detection result on its mirror im- ages as a concrete example, a mirrored version of a face age. We evaluate the mirrorability of several state of the image is perceived as the same face. In recent year, object art algorithms in two representative problems (face align- (parts) localization has made signiﬁcant progress and sev- ment and human pose estimation) on several datasets. One 1 ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTFigure## ##LTLine##

text: Mirror,

label: title

text: mirror

text: on

text: the

text: wall,

text: tell

text: me,

text: is

text: the

text: error

text: small?

text: Heng

label: author

text: Yang

text: Ioannis

text: Patras

text: Queen

text: Mary

text: University

text: of

text: London

text: Queen

text: Mary

text: University

text: of

text: London

text: heng.yang@qmul.ac.uk

font: MBQPWM+NimbusMonL-Regu

text: i.patras@qmul.ac.uk

text: Abstract

text: Do

label: abstract

text: object

text: part

text: localization

text: methods

text: produce

text: bilaterally

text: symmetric

text: results

text: on

text: mirror

text: images?

text: Surprisingly

text: not,

text: even

text: though

text: state

text: of

text: the

text: art

text: methods

text: augment

text: the

text: training

text: set

text: with

text: mirrored

text: images.

text: In

text: this

text: paper

text: we

text: take

text: a

text: closer

text: look

text: into

text: this

text: issue.

text: We

text: ﬁrst

text: introduce

text: the

text: concept

text: of

text: mirrorabil-

text: ity

text: as

text: the

text: ability

text: of

text: a

text: model

text: to

text: produce

text: symmetric

text: results

text: in

text: mirrored

text: images

text: and

text: introduce

text: a

text: corresponding

text: measure,

text: (a)

text: Mirror

text: error

text: (b)

text: Mirror

text: error

text: namely

text: the

text: mirror

text: error

text: that

text: is

text: deﬁned

text: as

text: the

text: difference

text: be-

text: tween

text: the

text: detection

text: result

text: on

text: an

text: image

text: and

text: the

text: mirror

text: of

text: the

text: detection

text: result

text: on

text: its

text: mirror

text: image.

text: We

text: evaluate

text: the

text: mir-

text: rorability

text: of

text: several

text: state

text: of

text: the

text: art

text: algorithms

text: in

text: two

text: of

text: the

text: most

text: intensively

text: studied

text: problems,

text: namely

text: human

text: pose

text: es-

text: timation

text: and

text: face

text: alignment.

text: Our

text: experiments

text: lead

text: to

text: sev-

text: eral

text: interesting

text: ﬁndings:

text: Surprisingly,

text: most

text: of

text: state

text: of

text: the

text: art

text: methods

text: struggle

text: to

text: preserve

text: the

text: mirror

text: symmetry,

text: (c)

text: Mirror

text: error

text: (d)

text: Mirror

text: error

text: despite

text: the

text: fact

text: that

text: they

text: do

text: have

text: very

text: similar

text: overall

text: per-

text: Figure

text: Example

text: pairs

text: of

text: localization

text: results

text: on

text: original

text: formance

text: on

text: the

text: original

text: and

text: mirror

text: images;

text: the

text: low

text: mir-

text: (left)

text: and

text: mirror

text: (right)

text: images.

text: First

text: row:

text: Human

text: Pose

text: rorability

text: is

text: not

text: caused

text: by

text: training

text: or

text: testing

text: sample

text: bias

text: Estimation

text: second

text: row:

text: Face

text: Alignment

text: by

text: RCPR

text: all

text: algorithms

text: are

text: trained

text: on

text: both

text: the

text: original

text: images

text: and

text: The

text: ﬁrst

text: column

text: (a

text: and

text: c)

text: shows

text: large

text: mirror

text: error

text: and

text: the

text: their

text: mirrored

text: versions;

text: the

text: mirror

text: error

text: is

text: strongly

text: cor-

text: second

text: (b

text: and

text: d)

text: small

text: mirror

text: error.

text: Can

text: we

text: evaluate

text: the

text: related

text: to

text: the

text: localization/alignment

text: error

text: (with

text: correlation

text: performance

text: without

text: knowing

text: the

text: ground

text: truth?

text: coefﬁcients

text: around

text: Since

text: the

text: mirror

text: error

text: is

text: calcu-

text: lated

text: without

text: knowledge

text: of

text: the

text: ground

text: truth,

text: we

text: show

text: two

text: eral

text: methods

text: have

text: reported

text: close-to-human

text: performance.

text: interesting

text: applications

text: in

text: the

text: ﬁrst

text: it

text: is

text: used

text: to

text: guide

text: the

text: This

text: includes

text: localization

text: of

text: objects

text: in

text: images

text: (e.g.

text: pedes-

text: selection

text: of

text: difﬁcult

text: samples

text: and

text: in

text: the

text: second

text: to

text: give

text: feed-

text: trian

text: or

text: face

text: detection)

text: or

text: ﬁne-grained

text: localization

text: of

text: object

text: back

text: in

text: a

text: popular

text: Cascaded

text: Pose

text: Regression

text: method

text: for

text: parts

text: (e.g.

text: face

text: parts

text: localization,

text: body

text: parts

text: localization,

text: face

text: alignment.

text: bird

text: parts

text: localization).

text: Most

text: of

text: those

text: methods

text: augment

text: the

text: training

text: set

text: by

text: mirroring

text: the

text: positive

text: training

text: samples.

text: Introduction

text: However,

text: are

text: these

text: models

text: able

text: to

text: give

text: symmetric

text: results

text: on

text: a

text: mirror

text: image

text: during

text: testing?

text: The

text: evolution

text: of

text: mirror

text: (bilateral)

text: symmetry

text: has

text: pro-

text: In

text: order

text: to

text: answer

text: this

text: question

text: we

text: ﬁrst

text: introduce

text: the

text: foundly

text: impacted

text: animal

text: evolution

text: As

text: a

text: consequence,

text: concept

text: of

text: mirrorability,

text: i.e.,

text: the

text: ability

text: of

text: an

text: algorithm

text: to

text: the

text: overwhelming

text: majority

text: of

text: modern

text: animals

text: in-

text: give

text: on

text: a

text: mirror

text: image

text: bilaterally

text: symmetric

text: results,

text: and

text: a

text: cluding

text: humans,

text: exhibit

text: mirror

text: symmetry.

text: As

text: shown

text: in

text: quantitative

text: measure

text: called

text: the

text: mirror

text: error.

text: The

text: latter

text: is

text: Fig.

text: the

text: mirror

text: of

text: an

text: image

text: depicting

text: such

text: objects

text: shows

text: deﬁned

text: as

text: the

text: difference

text: between

text: the

text: detection

text: result

text: on

text: an

text: a

text: meaningful

text: version

text: of

text: the

text: same

text: objects.

text: Taking

text: face

text: im-

text: image

text: and

text: the

text: mirror

text: of

text: detection

text: result

text: on

text: its

text: mirror

text: im-

text: ages

text: as

text: a

text: concrete

text: example,

text: a

text: mirrored

text: version

text: of

text: a

text: face

text: age.

text: We

text: evaluate

text: the

text: mirrorability

text: of

text: several

text: state

text: of

text: the

text: image

text: is

text: perceived

text: as

text: the

text: same

text: face.

text: In

text: recent

text: year,

text: object

text: art

text: algorithms

text: in

text: two

text: representative

text: problems

text: (face

text: align-

text: (parts)

text: localization

text: has

text: made

text: signiﬁcant

text: progress

text: and

text: sev-

text: ment

text: and

text: human

text: pose

text: estimation)

text: on

text: several

text: datasets.

text: One

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##