text: SIMD COMPRESSION AND THE INTERSECTION OF SORTED INTEGERS 3 SIMD instructions. They reported using fewer than 1.5 CPU cycles per 32-bit integer on a 2011- era Intel Sandy Bridge processor. In comparison, Stepanov et al. [8] also proposed compression schemes optimized for SIMD instructions on CPUs, but they reported using at least 2.2 CPU cycles per 32-bit integer on a 2010 Intel Westmere processor. Regarding the intersection of sorted integer lists, Ding and Ko¨nig [9] compared a wide range of algorithms in the context of a search engine and found that SvS with galloping was competitive: § ≈ we describe galloping in . Their own technique (RanGroup) performed better ( 10 %–30 %) but it does not operate over sorted lists but rather over a specialized data structure that divides up the data randomly into small chunks. In some instances, they found that a merge (akin to the merge step in the merge sort algorithm) was faster. They also achieved good results with Lookup [10]: a technique that relies on an auxiliary data structure for skipping values [11]. Ding and Ko¨nig found that alternatives such as Baeza-Yates’ algorithm [12] or adaptive algorithms [13] were slower. Barbay et al. [14] also carried out an extensive experimental evaluation. On synthetic data using a uniform distribution, they found that Baeza-Yates’ algorithm [12] was faster than SvS with galloping (by about 30 %). However, on real data (e.g., TREC GOV2), SvS with galloping was superior to most × alternatives by a wide margin (e.g., 2 faster). Culpepper and Moffat similarly found that SvS with galloping was the fastest [5] though their own max algorithm was fast as well. They found that in some speciﬁc instances (for queries containing 9 or more terms) a technique similar to galloping (interpolative search) was slightly better (by less than 10 %). Kane and Tompa improved Culpepper and Moffat’s HYB+M2 by adding auxiliary data structures to skip over large blocks of compressed values (256 integers) during the computation of the intersection [15]. Their good results are in contrast with Culpepper and Moffat’s ﬁnding that skipping is counterproductive when using bitmaps [5]. Our work is focused on commodity desktop processors. Compression and intersection of integer lists using a graphics processing unit (GPU) has also received attention. Ding et al. [16] improved the intersection speed using a parallel merge ﬁnd: essentially, they divide up one list into small blocks and intersect these blocks in parallel with the other array. On conjunctive queries, Ding et al. [16] found their GPU implementation to be only marginally superior to a CPU implementation ≈ ( 15 % faster) despite the data was already loaded in GPU’s global memory. They do, however, get × impressive speed gains (7 ) on disjunctive queries. Ao et al. [17] proposed a parallelized compression technique (Parallel PFor) and replaced conventional differential coding with an approach based on linear regression. In our work, we rely critically on differential coding, but alternative models merit consideration [18, 19, 20]. 3. RELEVANT SIMD INSTRUCTIONS Intel PC processors support vector instructions, but languages such as C or C++ do not directly include vectorization as part of their standard syntax. However, it is still possible to conveniently call these instructions by using intrinsics or online assembly code. Intrinsics are special functions (sometimes called built-in functions) provided as a compiler extension of C/C++ syntax. Table I presents the various SIMD instructions we require. In addition to instruction mnemonic names, we also provide names of respective C/C++ intrinsics. In this table, there is a single intrinsic function per mnemonic except for the move instruction movdqu, which has separate intrinsics to denote store and load operations. Though most of the instructions are fast, some are signiﬁcantly more expensive. Intel often expresses the computational cost of an instruction in terms of its latency and reciprocal throughput. The latency is the minimum number of cycles required to execute the instruction. The reciprocal throughput is one over the maximum number of instructions of the same kind that can be executed per cycle. For example, a reciprocal throughput of 0.5 indicates that up to two instructions of the same type can be executed in a cycle. We give the latency and reciprocal throughput for Intel processors with a Sandy Bridge microarchitecture [21]. These numbers are often constant across Intel microarchitectures.

text: SIMD

text: COMPRESSION

text: AND

text: THE

text: INTERSECTION

text: OF

text: SORTED

text: INTEGERS

text: SIMD

text: instructions.

text: They

text: reported

text: using

text: fewer

text: than

text: CPU

text: cycles

text: per

text: integer

text: on

text: a

text: era

text: Intel

text: Sandy

text: Bridge

text: processor.

text: In

text: comparison,

text: Stepanov

text: et

text: al.

text: also

text: proposed

text: compression

text: schemes

text: optimized

text: for

text: SIMD

text: instructions

text: on

text: CPUs,

text: but

text: they

text: reported

text: using

text: at

text: least

text: CPU

text: cycles

text: per

text: integer

text: on

text: a

text: Intel

text: Westmere

text: processor.

text: Regarding

text: the

text: intersection

text: of

text: sorted

text: integer

text: lists,

text: Ding

text: and

text: Ko¨nig

text: compared

text: a

text: wide

text: range

text: of

text: algorithms

text: in

text: the

text: context

text: of

text: a

text: search

text: engine

text: and

text: found

text: that

text: SvS

text: with

text: galloping

text: was

text: competitive:

text: we

text: describe

text: galloping

text: in

text: Their

text: own

text: technique

text: (RanGroup)

text: performed

text: better

text: but

text: it

text: does

text: not

text: operate

text: over

text: sorted

text: lists

text: but

text: rather

text: over

text: a

text: specialized

text: data

text: structure

text: that

text: divides

text: up

text: the

text: data

text: randomly

text: into

text: small

text: chunks.

text: In

text: some

text: instances,

text: they

text: found

text: that

text: a

text: merge

text: (akin

text: to

text: the

text: merge

text: step

text: in

text: the

text: merge

text: sort

text: algorithm)

text: was

text: faster.

text: They

text: also

text: achieved

text: good

text: results

text: with

text: Lookup

text: a

text: technique

text: that

text: relies

text: on

text: an

text: auxiliary

text: data

text: structure

text: for

text: skipping

text: values

text: Ding

text: and

text: Ko¨nig

text: found

text: that

text: alternatives

text: such

text: as

text: Baeza-Yates’

text: algorithm

text: or

text: adaptive

text: algorithms

text: were

text: slower.

text: Barbay

text: et

text: al.

text: also

text: carried

text: out

text: an

text: extensive

text: experimental

text: evaluation.

text: On

text: synthetic

text: data

text: using

text: a

text: uniform

text: distribution,

text: they

text: found

text: that

text: Baeza-Yates’

text: algorithm

text: was

text: faster

text: than

text: SvS

text: with

text: galloping

text: (by

text: about

text: However,

text: on

text: real

text: data

text: (e.g.,

text: TREC

text: SvS

text: with

text: galloping

text: was

text: superior

text: to

text: most

text: alternatives

text: by

text: a

text: wide

text: margin

text: (e.g.,

text: faster).

text: Culpepper

text: and

text: Moffat

text: similarly

text: found

text: that

text: SvS

text: with

text: galloping

text: was

text: the

text: fastest

text: though

text: their

text: own

text: max

text: algorithm

text: was

text: fast

text: as

text: well.

text: They

text: found

text: that

text: in

text: some

text: speciﬁc

text: instances

text: (for

text: queries

text: containing

text: or

text: more

text: terms)

text: a

text: technique

text: similar

text: to

text: galloping

text: (interpolative

text: search)

text: was

text: slightly

text: better

text: (by

text: less

text: than

text: Kane

text: and

text: Tompa

text: improved

text: Culpepper

text: and

text: Moffat’s

text: by

text: adding

text: auxiliary

text: data

text: structures

text: to

text: skip

text: over

text: large

text: blocks

text: of

text: compressed

text: values

text: integers)

text: during

text: the

text: computation

text: of

text: the

text: intersection

text: Their

text: good

text: results

text: are

text: in

text: contrast

text: with

text: Culpepper

text: and

text: Moffat’s

text: ﬁnding

text: that

text: skipping

text: is

text: counterproductive

text: when

text: using

text: bitmaps

text: Our

text: work

text: is

text: focused

text: on

text: commodity

text: desktop

text: processors.

text: Compression

text: and

text: intersection

text: of

text: integer

text: lists

text: using

text: a

text: graphics

text: processing

text: unit

text: (GPU)

text: has

text: also

text: received

text: attention.

text: Ding

text: et

text: al.

text: improved

text: the

text: intersection

text: speed

text: using

text: a

text: parallel

text: merge

text: ﬁnd:

text: essentially,

text: they

text: divide

text: up

text: one

text: list

text: into

text: small

text: blocks

text: and

text: intersect

text: these

text: blocks

text: in

text: parallel

text: with

text: the

text: other

text: array.

text: On

text: conjunctive

text: queries,

text: Ding

text: et

text: al.

text: found

text: their

text: GPU

text: implementation

text: to

text: be

text: only

text: marginally

text: superior

text: to

text: a

text: CPU

text: implementation

text: faster)

text: despite

text: the

text: data

text: was

text: already

text: loaded

text: in

text: GPU’s

text: global

text: memory.

text: They

text: do,

text: however,

text: get

text: impressive

text: speed

text: gains

text: on

text: disjunctive

text: queries.

text: Ao

text: et

text: al.

text: proposed

text: a

text: parallelized

text: compression

text: technique

text: (Parallel

text: PFor)

text: and

text: replaced

text: conventional

text: differential

text: coding

text: with

text: an

text: approach

text: based

text: on

text: linear

text: regression.

text: In

text: our

text: work,

text: we

text: rely

text: critically

text: on

text: differential

text: coding,

text: but

text: alternative

text: models

text: merit

text: consideration

text: RELEVANT

text: SIMD

text: INSTRUCTIONS

text: Intel

text: PC

text: processors

text: support

text: vector

text: instructions,

text: but

text: languages

text: such

text: as

text: C

text: or

text: C++

text: do

text: not

text: directly

text: include

text: vectorization

text: as

text: part

text: of

text: their

text: standard

text: syntax.

text: However,

text: it

text: is

text: still

text: possible

text: to

text: conveniently

text: call

text: these

text: instructions

text: by

text: using

text: intrinsics

text: or

text: online

text: assembly

text: code.

text: Intrinsics

text: are

text: special

text: functions

text: (sometimes

text: called

text: built-in

text: functions)

text: provided

text: as

text: a

text: compiler

text: extension

text: of

text: C/C++

text: syntax.

text: Table

text: I

text: presents

text: the

text: various

text: SIMD

text: instructions

text: we

text: require.

text: In

text: addition

text: to

text: instruction

text: mnemonic

text: names,

text: we

text: also

text: provide

text: names

text: of

text: respective

text: C/C++

text: intrinsics.

text: In

text: this

text: table,

text: there

text: is

text: a

text: single

text: intrinsic

text: function

text: per

text: mnemonic

text: except

text: for

text: the

text: move

text: instruction

text: movdqu,

text: which

text: has

text: separate

text: intrinsics

text: to

text: denote

text: store

text: and

text: load

text: operations.

text: Though

text: most

text: of

text: the

text: instructions

text: are

text: fast,

text: some

text: are

text: signiﬁcantly

text: more

text: expensive.

text: Intel

text: often

text: expresses

text: the

text: computational

text: cost

text: of

text: an

text: instruction

text: in

text: terms

text: of

text: its

text: latency

text: and

text: reciprocal

text: throughput.

text: The

text: latency

text: is

text: the

text: minimum

text: number

text: of

text: cycles

text: required

text: to

text: execute

text: the

text: instruction.

text: The

text: reciprocal

text: throughput

text: is

text: one

text: over

text: the

text: maximum

text: number

text: of

text: instructions

text: of

text: the

text: same

text: kind

text: that

text: can

text: be

text: executed

text: per

text: cycle.

text: For

text: example,

text: a

text: reciprocal

text: throughput

text: of

text: indicates

text: that

text: up

text: to

text: two

text: instructions

text: of

text: the

text: same

text: type

text: can

text: be

text: executed

text: in

text: a

text: cycle.

text: We

text: give

text: the

text: latency

text: and

text: reciprocal

text: throughput

text: for

text: Intel

text: processors

text: with

text: a

text: Sandy

text: Bridge

text: microarchitecture

text: These

text: numbers

text: are

text: often

text: constant

text: across

text: Intel

text: microarchitectures.


text: SIMD COMPRESSION AND THE INTERSECTION OF SORTED INTEGERS 27 Table VII. Time required to answer queries from TREC 1MQ in ms/query along with the storage requirement in bits/int. Entropies of the deltas are provided. We write S4-FASTPFOR as a shorthand for S4-FASTPFOR- D1. We omit S4-BP128-DM when it does not differ signiﬁcantly from S4-BP128-D4. scheme bits/int time bits/int time bits/int time GOV2 GOV2 CLUEWEB09 (sorted) (unsorted) entropy 1.9 4.6 3.1 NO BITMAP VARINT 8.2 6.3 8.5 8.2 8.2 17.5 FASTPFOR 3.8 6.3 6.2 8.0 5.0 17.3 S4-BP128-D4 6.2 2.1 7.9 2.5 7.5 5.6 S4-BP128-DM 6.2 2.1 7.7 2.6 7.4 5.7 S4-BP128-D2 5.6 2.2 7.4 2.6 7.1 6.0 S4-BP128-D1 5.0 2.4 6.9 2.8 6.6 6.5 S4-FASTPFOR 3.8 3.5 6.2 4.0 5.0 9.7 B = 8 VARINT 5.8 3.0 7.4 4.7 6.2 9.9 FASTPFOR 4.3 3.0 6.3 4.5 5.2 9.3 S4-BP128-D4 5.7 1.2 7.4 1.6 6.5 3.4 S4-BP128-DM 5.7 1.2 7.3 1.6 6.4 3.4 S4-BP128-D2 5.5 1.3 7.1 1.6 6.3 3.6 S4-BP128-D1 5.3 1.4 6.8 1.7 6.1 3.8 S4-FASTPFOR 4.3 1.9 6.3 2.3 5.2 5.4 B = 16 VARINT 6.3 2.1 8.2 3.2 6.9 6.7 FASTPFOR 5.5 2.1 7.6 2.9 6.4 5.9 S4-BP128-D4 6.5 0.9 8.4 1.2 7.2 2.5 S4-BP128-D2 6.4 1.0 8.1 1.2 7.1 2.6 S4-BP128-D1 6.2 1.1 7.9 1.3 7.0 2.7 S4-FASTPFOR 5.5 1.4 7.6 1.6 6.4 3.7 B = 32 VARINT 8.2 1.4 11.1 2.0 8.9 4.2 FASTPFOR 7.8 1.5 10.9 1.8 8.7 3.7 S4-BP128-D4 8.4 0.8 11.2 0.9 9.1 1.9 S4-BP128-D2 8.4 0.8 11.1 1.0 9.1 2.0 S4-BP128-D1 8.3 0.8 11.0 1.0 9.0 2.0 S4-FASTPFOR 7.8 1.1 10.9 1.2 8.7 2.6 Skipper [36] 10.2 2.6 10.5 4.3 10.2 7.7 15. Kane A, Tompa F. Skewed partial bitvectors for list intersection. Proceedings of the 37th annual international ACM SIGIR conference on Research and development in information retrieval, ACM, 2014; 263–272. 16. Ding S, He J, Yan H, Suel T. Using graphics processors for high performance IR query processing. Proceedings of the 18th international conference on World wide web, WWW ’09, ACM: New York, NY, USA, 2009; 421–430, doi:10.1145/1526709.1526766. 17. Ao N, Zhang F, Wu D, Stones DS, Wang G, Liu X, Liu J, Lin S. Efﬁcient parallel lists intersection and index compression algorithms using graphics processing units. Proc. VLDB Endow. May 2011; 4(8):470–481. 18. Konow R, Navarro G, Clarke CL, Lo´pez-Ort´ız A. Faster and smaller inverted indices with treaps. Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’13, ACM: New York, NY, USA, 2013; 193–202, doi:10.1145/2484028.2484088. 19. Vigna S. Quasi-succinct indices. Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, WSDM ’13, ACM: New York, NY, USA, 2013; 83–92. 20. Ottaviano G, Venturini R. Partitioned Elias-Fano indexes. SIGIR ’14, ACM Press: New York, NY, USA, 2014. ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##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: SIMD

label: paragraph

text: COMPRESSION

text: AND

text: THE

text: INTERSECTION

text: OF

text: SORTED

text: INTEGERS

text: Table

text: VII.

text: Time

label: caption

text: required

text: to

text: answer

text: queries

text: from

text: TREC

text: in

text: ms/query

text: along

text: with

text: the

text: storage

text: requirement

text: in

text: bits/int.

text: Entropies

text: of

text: the

text: deltas

text: are

text: provided.

text: We

text: write

text: as

text: a

text: shorthand

text: for

text: We

text: omit

text: when

text: it

text: does

text: not

text: differ

text: signiﬁcantly

text: from

text: scheme

label: table

text: bits/int

text: time

text: bits/int

text: time

text: bits/int

text: time

text: (sorted)

text: (unsorted)

text: entropy

text: NO

text: BITMAP

text: VARINT

text: FASTPFOR

text: B

text: VARINT

text: FASTPFOR

text: B

text: VARINT

text: FASTPFOR

text: B

text: VARINT

text: FASTPFOR

text: Skipper

text: Kane

text: A,

text: Tompa

text: F.

text: Skewed

text: partial

text: bitvectors

text: for

text: list

text: intersection.

text: Proceedings

text: of

text: the

text: annual

text: international

text: ACM

text: SIGIR

text: conference

text: on

text: Research

text: and

text: development

text: in

text: information

text: retrieval,

text: ACM,

text: Ding

text: S,

text: He

text: J,

text: Yan

text: H,

text: Suel

text: T.

text: Using

text: graphics

text: processors

text: for

text: high

text: performance

text: IR

text: query

text: processing.

text: Proceedings

text: of

text: the

text: international

text: conference

text: on

text: World

text: wide

text: web,

text: WWW

text: ACM:

text: New

text: York,

text: NY,

text: USA,

text: Ao

text: N,

text: Zhang

text: F,

text: Wu

text: D,

text: Stones

text: DS,

text: Wang

text: G,

text: Liu

text: X,

text: Liu

text: J,

text: Lin

text: S.

text: Efﬁcient

text: parallel

text: lists

text: intersection

text: and

text: index

text: compression

text: algorithms

text: using

text: graphics

text: processing

text: units.

text: Proc.

text: VLDB

text: Endow.

text: May

text: Konow

text: R,

text: Navarro

text: G,

text: Clarke

text: CL,

text: Lo´pez-Ort´ız

text: A.

text: Faster

text: and

text: smaller

text: inverted

text: indices

text: with

text: treaps.

text: Proceedings

text: of

text: the

text: International

text: ACM

text: SIGIR

text: Conference

text: on

text: Research

text: and

text: Development

text: in

text: Information

text: Retrieval,

text: SIGIR

text: ACM:

text: New

text: York,

text: NY,

text: USA,

text: Vigna

text: S.

text: Quasi-succinct

text: indices.

text: Proceedings

text: of

text: the

text: Sixth

text: ACM

text: International

text: Conference

text: on

text: Web

text: Search

text: and

text: Data

text: Mining,

text: WSDM

text: ACM:

text: New

text: York,

text: NY,

text: USA,

text: Ottaviano

text: G,

text: Venturini

text: R.

text: Partitioned

text: Elias-Fano

text: indexes.

text: SIGIR

text: ACM

text: Press:

text: New

text: York,

text: NY,

text: USA,

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: The stationary distribution of a Markov jump process glued ∗ together from two state spaces at two vertices †‡ † Bence Mélykúti §, Peter Pfaﬀelhuber 26th May 2020 Abstract We compute the stationary distribution of a continuous-time Markov chain which is constructed by gluing together two ﬁnite, irreducible Markov chains by identifying a pair of states of one chain with a pair of states of the other and keeping all transition rates from either chain (the rates between the two shared states are summed). The result expresses the stationary distribution of the glued chain in terms of quantities of the two original chains. Some of the required terms are nonstandard but can be computed by solving systems of linear equations using the transition rate matrices of the two original chains. Special emphasis is given to the cases when the stationary distribution of the glued chain is a multiple of the equilibria of the original chains, and when not, for which bounds are derived. 1 Introduction Computing the stationary distribution of an irreducible continuous-time Markov chain on a ﬁnite state space is easy in principle. If Q is the transition rate matrix, it only requires ﬁnding a probability vector π that solves πTQ = 0. (This is a standard result in the classical literature on Markov chains, see e.g. Liggett[5]; Norris[7].) Elementary examples include birth–death chains[3] or a circular state space[1]. However, if the transition graph of the Markov chain is more complicated, hardly any general result is known about the shape of the equilibrium. (A ∗ This is a revision of our Author’s Original Manuscript submitted for publication to Stochastic Models, Taylor & Francis LLC. † Department of Mathematical Stochastics, University of Freiburg, Eckerstr. 1, 79104 Freiburg, Germany ‡ Center for Biological Systems Analysis (ZBSA), University of Freiburg, Habsburgerstr. 49, 79104 Freiburg, Germany §Corresponding author. Email: melykuti@stochastik.uni-freiburg.de. 1 ##LTLine##

text: The

label: title

text: stationary

text: distribution

text: of

text: a

text: Markov

text: jump

text: process

text: glued

text: together

text: from

text: two

text: state

text: spaces

text: at

text: two

text: vertices

label: author

text: Bence

text: Mélykúti

text: Peter

text: Pfaﬀelhuber

text: May

text: Abstract

text: We

label: abstract

text: compute

text: the

text: stationary

text: distribution

text: of

text: a

text: continuous-time

text: Markov

text: chain

text: which

text: is

text: constructed

text: by

text: gluing

text: together

text: two

text: ﬁnite,

text: irreducible

text: Markov

text: chains

text: by

text: identifying

text: a

text: pair

text: of

text: states

text: of

text: one

text: chain

text: with

text: a

text: pair

text: of

text: states

text: of

text: the

text: other

text: and

text: keeping

text: all

text: transition

text: rates

text: from

text: either

text: chain

text: (the

text: rates

text: between

text: the

text: two

text: shared

text: states

text: are

text: summed).

text: The

text: result

text: expresses

text: the

text: stationary

text: distribution

text: of

text: the

text: glued

text: chain

text: in

text: terms

text: of

text: quantities

text: of

text: the

text: two

text: original

text: chains.

text: Some

text: of

text: the

text: required

text: terms

text: are

text: nonstandard

text: but

text: can

text: be

text: computed

text: by

text: solving

text: systems

text: of

text: linear

text: equations

text: using

text: the

text: transition

text: rate

text: matrices

text: of

text: the

text: two

text: original

text: chains.

text: Special

text: emphasis

text: is

text: given

text: to

text: the

text: cases

text: when

text: the

text: stationary

text: distribution

text: of

text: the

text: glued

text: chain

text: is

text: a

text: multiple

text: of

text: the

text: equilibria

text: of

text: the

text: original

text: chains,

text: and

text: when

text: not,

text: for

text: which

text: bounds

text: are

text: derived.

text: Introduction

text: Computing

text: the

text: stationary

text: distribution

text: of

text: an

text: irreducible

text: continuous-time

text: Markov

text: chain

text: on

text: a

text: ﬁnite

text: state

text: space

text: is

text: easy

text: in

text: principle.

text: If

text: Q

text: is

text: the

text: transition

text: rate

text: matrix,

text: it

text: only

text: requires

text: ﬁnding

text: a

text: probability

text: vector

text: π

text: that

text: solves

text: πTQ

text: (This

text: is

text: a

text: standard

text: result

text: in

text: the

text: classical

text: literature

text: on

text: Markov

text: chains,

text: see

text: e.g.

text: Elementary

text: examples

text: include

text: birth–death

text: or

text: a

text: circular

text: state

text: However,

text: if

text: the

text: transition

text: graph

text: of

text: the

text: Markov

text: chain

text: is

text: more

text: complicated,

text: hardly

text: any

text: general

text: result

text: is

text: known

text: about

text: the

text: shape

text: of

text: the

text: equilibrium.

text: (A

text: This

text: is

text: a

text: revision

text: of

text: our

text: Author’s

text: Original

text: Manuscript

text: submitted

text: for

text: publication

text: to

text: Stochastic

text: Models,

text: Taylor

text: Francis

text: LLC.

text: Department

text: of

text: Mathematical

text: Stochastics,

text: University

text: of

text: Freiburg,

text: Eckerstr.

text: Freiburg,

text: Germany

text: Center

text: for

text: Biological

text: Systems

text: Analysis

text: (ZBSA),

text: University

text: of

text: Freiburg,

text: Habsburgerstr.

text: Freiburg,

text: Germany

text: §Corresponding

text: author.

text: Email:

text: melykuti@stochastik.uni-freiburg.de.

text: ##LTLine##


text: A B B In particular, the explicit solution shows that Condition ( ) implies Conditions ( A) and ( B). Proof Three statements need to be veriﬁed: the entries of π are nonnegative, they sum to one and πTQ = 0. To the ﬁrst, because of irreducibility all entries of πA and πB are positive. All is needed is that C > 0. Since πB sums to one, − − πA + πB πA(πB + πB) > πA + πB πA > 0. 1 1 1 1 2 1 1 1 As to the second statement,(cid:88) (cid:88) (cid:88) s 2 s 1 C − πi = − πiAπ(cid:88)1B + π1AπiB i= r+3 i= r+3 i=3 s = 1πB + πA πB 1 1 i i=3 − − = πB + πA(1 πB πB) 1 1 1 2 − = πB + πA πA(πB + πB) 1 1 1 1 2 is exactly 1/C, proving that the entries of π sum to one. The validity of the last statement can be most easily seen by considering how the transition × rate matrix Q arises from QA and QB almost as a block diagonal matrix if not for a 2 2 overlap where the entries are summed. In the following, we rely on (πA)TQA = 0 and (πB)TQB = 0. ∈ {− − } The result of the multiplication (πTQ) for i r + 3, r + 4, . . . , 0 can be seen to be zero i from − (C 1πTQ) = πB((πA)TQA) = πB0 = 0. i 1 i 1 ∈ { } A The case of i 3, 4, . . . , s is entirely similar. For i = 1, using Condition ( ) in the form (cid:88) πBπA = πAπB in the second step, 1 2 1 2 − (C 1πTQ) = πBπAQA + πBπA((cid:88)QA + QB ) 1 1 k k1 1 1 11 11 ∈S k A + πB(cid:88)πA(QA + QB ) +(cid:88) πAπBQB 1 2 21 21 1 k k1 ∈S k B = πB πAQA + πA πBQB 1 k k1 1 k k1 ∈V ∈V k A k B = πB0 + πA0 = 0. 1 1 20 ##LTLine##

text: A

text: B

text: B

text: In

text: particular,

text: the

text: explicit

text: solution

text: shows

text: that

text: Condition

text: implies

text: Conditions

text: A)

text: and

text: B).

text: Proof

text: Three

text: statements

text: need

text: to

text: be

text: veriﬁed:

text: the

text: entries

text: of

text: π

text: are

text: nonnegative,

text: they

text: sum

text: to

text: one

text: and

text: πTQ

text: To

text: the

text: ﬁrst,

text: because

text: of

text: irreducibility

text: all

text: entries

text: of

text: πA

text: and

text: πB

text: are

text: positive.

text: All

text: is

text: needed

text: is

text: that

text: C

text: Since

text: πB

text: sums

text: to

text: one,

text: πA

text: πB

text: πA(πB

text: πB)

text: πA

text: πB

text: πA

text: As

text: to

text: the

text: second

text: s

text: s

text: C

text: πi

text: i=

text: i=

text: s

text: πA

text: πB

text: i

text: πB

text: πB

text: πB)

text: πB

text: πA

text: πA(πB

text: πB)

text: is

text: exactly

text: proving

text: that

text: the

text: entries

text: of

text: π

text: sum

text: to

text: one.

text: The

text: validity

text: of

text: the

text: last

text: statement

text: can

text: be

text: most

text: easily

text: seen

text: by

text: considering

text: how

text: the

text: transition

text: rate

text: matrix

text: Q

text: arises

text: from

text: QA

text: and

text: QB

text: almost

text: as

text: a

text: block

text: diagonal

text: matrix

text: if

text: not

text: for

text: a

text: overlap

text: where

text: the

text: entries

text: are

text: summed.

text: In

text: the

text: following,

text: we

text: rely

text: on

text: (πA)TQA

text: and

text: (πB)TQB

text: The

text: result

text: of

text: the

text: multiplication

text: (πTQ)

text: for

text: i

text: r

text: r

text: can

text: be

text: seen

text: to

text: be

text: zero

text: i

text: from

text: (C

text: πB((πA)TQA)

text: i

text: i

text: A

text: The

text: case

text: of

text: i

text: s

text: is

text: entirely

text: similar.

text: For

text: i

text: using

text: Condition

text: in

text: the

text: form

text: πBπA

text: πAπB

text: in

text: the

text: second

text: step,

text: (C

text: πBπAQA

text: QB

text: k

text: ∈S

text: k

text: A

text: QB

text: πAπBQB

text: k

text: ∈S

text: k

text: B

text: πB

text: πAQA

text: πA

text: πBQB

text: k

text: k

text: ∈V

text: ∈V

text: k

text: A

text: k

text: B

text: ##LTLine##


text: deﬁned analogously. X X We create a new Markov chain = ( ) ≥ by gluing together the two state spaces at t t 0 ∈ V ∈ V two states: we identify state 1 A with 1 B (and call it state 1 in the glued chain) and ∈ V ∈ V X 2 A with 2 B (to be denoted by 2), and keep all transitions that were present in A X X X or in B. Between states 1 and 2, transitions of both A and B are retained: the transition rates add up. If originally both chains had a transition, say, from 1 to 2, then we can think X of the dynamics as there being a choice between two parallel edges. The glued chain has transition rate matrix Q ∈ R(r+s−2)×(r+s−2): for i, j ∈ {−r + 3, −r + 4, . . . , s}, ≤ ≥ Q = QA 1(i, j 2) + QB 1(i, j 1). ij ij ij X X { } The set of states of that belonged to A with the exception of 1, 2 is denoted by S V \ { } {− − } A = A 1, 2 = r + 3, r + 4, . . . , 0 . S V \ { } { } B = B 1, 2 = 3, 4, . . . , s X X is deﬁned similarly for B. Hence, the state space of can be written as the disjoint union S ∪{ }∪S A ˙ 1, 2 ˙ B. X Our goal is to compute the stationary distribution π of , i.e. πTQ = 0, from the stationary X X distributions πA and πB of A and, respectively, B. (Note that irreducibility implies that πA, πB and π all exist uniquely and are all strictly positive.) However, it will turn out (see Theorem 1 below) that more information than πA and πB is needed to compute π. In theory, ﬁnding a left nullvector π to matrix Q is a basic task. Still, we hope to learn more about X X X π and by expressing π through A and B. This approach would also give a method to recursively compute the stationary distribution of a Markov chain on a large state space from properties of two smaller parts, parts thereof and so on. Gluing at one state only In Mélykúti et al.[6], the stationary distribution was expressed when the gluing of two state spaces happened at one state only. Here, with the obvious adjustment of notation, the rate matrices QA ∈ Rr×r and QB ∈ Rs×s translate into the rate matrix of the glued chain Q ∈ R(r+s−1)×(r+s−1) by ≤ ≥ Q = QA 1(i, j 1) + QB 1(i, j 1) ij ij ij ∈ {− − } for i, j r + 2, r + 3, . . . , s . The resulting stationary distribution is a constant multiple S S of πA on A, and of πB on B as follows: 3

text: deﬁned

text: analogously.

text: X

text: X

text: We

text: create

text: a

text: new

text: Markov

text: chain

text: by

text: gluing

text: together

text: the

text: two

text: state

text: spaces

text: at

text: t

text: t

text: V

text: V

text: two

text: states:

text: we

text: identify

text: state

text: A

text: with

text: B

text: (and

text: call

text: it

text: state

text: in

text: the

text: glued

text: chain)

text: and

text: V

text: V

text: X

text: A

text: with

text: B

text: (to

text: be

text: denoted

text: by

text: and

text: keep

text: all

text: transitions

text: that

text: were

text: present

text: in

text: A

text: X

text: X

text: X

text: or

text: in

text: B.

text: Between

text: states

text: and

text: transitions

text: of

text: both

text: A

text: and

text: B

text: are

text: retained:

text: the

text: transition

text: rates

text: add

text: up.

text: If

text: originally

text: both

text: chains

text: had

text: a

text: transition,

text: say,

text: from

text: to

text: then

text: we

text: can

text: think

text: X

text: of

text: the

text: dynamics

text: as

text: there

text: being

text: a

text: choice

text: between

text: two

text: parallel

text: edges.

text: The

text: glued

text: chain

text: has

text: transition

text: rate

text: matrix

text: Q

text: for

text: i,

text: j

text: {−r

text: −r

text: s},

text: Q

text: QA

text: j

text: QB

text: j

text: ij

text: ij

text: ij

text: X

text: X

text: The

text: set

text: of

text: states

text: of

text: that

text: belonged

text: to

text: A

text: with

text: the

text: exception

text: of

text: is

text: denoted

text: by

text: S

text: V

text: A

text: A

text: r

text: r

text: S

text: V

text: B

text: B

text: s

text: X

text: X

text: is

text: deﬁned

text: similarly

text: for

text: B.

text: Hence,

text: the

text: state

text: space

text: of

text: can

text: be

text: written

text: as

text: the

text: disjoint

text: union

text: S

text: }∪S

text: A

text: B.

text: X

text: Our

text: goal

text: is

text: to

text: compute

text: the

text: stationary

text: distribution

text: π

text: of

text: i.e.

text: πTQ

text: from

text: the

text: stationary

text: X

text: X

text: distributions

text: πA

text: and

text: πB

text: of

text: A

text: and,

text: respectively,

text: B.

text: (Note

text: that

text: irreducibility

text: implies

text: that

text: πA,

text: πB

text: and

text: π

text: all

text: exist

text: uniquely

text: and

text: are

text: all

text: strictly

text: positive.)

text: However,

text: it

text: will

text: turn

text: out

text: (see

text: Theorem

text: below)

text: that

text: more

text: information

text: than

text: πA

text: and

text: πB

text: is

text: needed

text: to

text: compute

text: π.

text: In

text: theory,

text: ﬁnding

text: a

text: left

text: nullvector

text: π

text: to

text: matrix

text: Q

text: is

text: a

text: basic

text: task.

text: Still,

text: we

text: hope

text: to

text: learn

text: more

text: about

text: X

text: X

text: X

text: π

text: and

text: by

text: expressing

text: π

text: through

text: A

text: and

text: B.

text: This

text: approach

text: would

text: also

text: give

text: a

text: method

text: to

text: recursively

text: compute

text: the

text: stationary

text: distribution

text: of

text: a

text: Markov

text: chain

text: on

text: a

text: large

text: state

text: space

text: from

text: properties

text: of

text: two

text: smaller

text: parts,

text: parts

text: thereof

text: and

text: so

text: on.

text: Gluing

text: at

text: one

text: state

text: only

text: In

text: Mélykúti

text: et

text: the

text: stationary

text: distribution

text: was

text: expressed

text: when

text: the

text: gluing

text: of

text: two

text: state

text: spaces

text: happened

text: at

text: one

text: state

text: only.

text: Here,

text: with

text: the

text: obvious

text: adjustment

text: of

text: notation,

text: the

text: rate

text: matrices

text: QA

text: Rr×r

text: and

text: QB

text: Rs×s

text: translate

text: into

text: the

text: rate

text: matrix

text: of

text: the

text: glued

text: chain

text: Q

text: by

text: Q

text: QA

text: j

text: QB

text: j

text: ij

text: ij

text: ij

text: for

text: i,

text: j

text: r

text: r

text: s

text: The

text: resulting

text: stationary

text: distribution

text: is

text: a

text: constant

text: multiple

text: S

text: S

text: of

text: πA

text: on

text: A,

text: and

text: of

text: πB

text: on

text: B

text: as

text: follows:


text: X X If gluing is applied to grow a large A by an B with a linear state diagram, although X the required excursion probabilities etc. might well be computable by hand for B, the same X quantities for A are still only available by solving linear equations, as summarised in Section . There is no escaping the lengthy calculations for the complicated chain, even when this chain is perturbed by a simple chain. X The regeneration argument exposed in this paper should be applicable when, say, B is not irreducible only because there is no opportunity for tB -excursions (meaning that there 2B1 ∈ V are two separate communicating classes in the state space, one containing 1 B and the ∈ V other 2 B, and the communicating class of 2 is an absorbing set), but the gluing introduces V such a state-2-to-state-1 transition via A. The gluing studied here is a binary operation on the set of Markov chains. A possible line of future research might consider other operations with Markov chains: gluing at multiple states, removing parts of the state space, taking a product of state spaces, or combining product and merging, as was alluded to in Section . If we stay with gluing at two states, it would be interesting to know how other properties of a Markov chain, such as the mixing time, are aﬀected if another chain is glued to it. Acknowledgments B.M. gratefully acknowledges funding by a postdoctoral fellowship of the Alexander von Humboldt Foundation. We are grateful to András György (Massachusetts Institute of Tech- nology), who suggested to write down the linear systems solved in Propositions 3 and 4. We acknowledge Alison Etheridge (University of Oxford) to have noticed that the main points of Theorem 5 must hold. References [1] Ivo Adan and Jacques Resing. Circular Markov chains. Technical Report Memorandum COSOR 96-16, Eindhoven University of Technology, Eindhoven, The Netherlands, 1996. URL http://alexandria.tue.nl/repository/books/461817.pdf. [2] Andras Gyorgy and Domitilla Del Vecchio. Modular composition of gene tran- scription networks. PLoS Computational Biology, 10(3):e1003486, Mar 2014. doi: 10.1371/journal.pcbi.1003486. [3] S. Karlin and H. M. Taylor. A ﬁrst course in stochastic processes. Academic Press London, 1975. [4] F. Leighton and Ronald L. Rivest. Estimating a probability using ﬁnite memory. IEEE Transactions on Information Theory, 32(6):733–742, Nov 1986. ISSN 0018-9448. doi: 10.1109/TIT.1986.1057250. 28

text: X

text: X

text: If

text: gluing

text: is

text: applied

text: to

text: grow

text: a

text: large

text: A

text: by

text: an

text: B

text: with

text: a

text: linear

text: state

text: diagram,

text: although

text: X

text: the

text: required

text: excursion

text: probabilities

text: etc.

text: might

text: well

text: be

text: computable

text: by

text: hand

text: for

text: B,

text: the

text: same

text: X

text: quantities

text: for

text: A

text: are

text: still

text: only

text: available

text: by

text: solving

text: linear

text: equations,

text: as

text: summarised

text: in

text: Section

text: There

text: is

text: no

text: escaping

text: the

text: lengthy

text: calculations

text: for

text: the

text: complicated

text: chain,

text: even

text: when

text: this

text: chain

text: is

text: perturbed

text: by

text: a

text: simple

text: chain.

text: X

text: The

text: regeneration

text: argument

text: exposed

text: in

text: this

text: paper

text: should

text: be

text: applicable

text: when,

text: say,

text: B

text: is

text: not

text: irreducible

text: only

text: because

text: there

text: is

text: no

text: opportunity

text: for

text: tB

text: -excursions

text: (meaning

text: that

text: there

text: V

text: are

text: two

text: separate

text: communicating

text: classes

text: in

text: the

text: state

text: space,

text: one

text: containing

text: B

text: and

text: the

text: V

text: other

text: B,

text: and

text: the

text: communicating

text: class

text: of

text: is

text: an

text: absorbing

text: set),

text: but

text: the

text: gluing

text: introduces

text: V

text: such

text: a

text: transition

text: via

text: A.

text: The

text: gluing

text: studied

text: here

text: is

text: a

text: binary

text: operation

text: on

text: the

text: set

text: of

text: Markov

text: chains.

text: A

text: possible

text: line

text: of

text: future

text: research

text: might

text: consider

text: other

text: operations

text: with

text: Markov

text: chains:

text: gluing

text: at

text: multiple

text: states,

text: removing

text: parts

text: of

text: the

text: state

text: space,

text: taking

text: a

text: product

text: of

text: state

text: spaces,

text: or

text: combining

text: product

text: and

text: merging,

text: as

text: was

text: alluded

text: to

text: in

text: Section

text: If

text: we

text: stay

text: with

text: gluing

text: at

text: two

text: states,

text: it

text: would

text: be

text: interesting

text: to

text: know

text: how

text: other

text: properties

text: of

text: a

text: Markov

text: chain,

text: such

text: as

text: the

text: mixing

text: time,

text: are

text: aﬀected

text: if

text: another

text: chain

text: is

text: glued

text: to

text: it.

text: Acknowledgments

text: B.M.

text: gratefully

text: acknowledges

text: funding

text: by

text: a

text: postdoctoral

text: fellowship

text: of

text: the

text: Alexander

text: von

text: Humboldt

text: Foundation.

text: We

text: are

text: grateful

text: to

text: András

text: György

text: (Massachusetts

text: Institute

text: of

text: Tech-

text: nology),

text: who

text: suggested

text: to

text: write

text: down

text: the

text: linear

text: systems

text: solved

text: in

text: Propositions

text: and

text: We

text: acknowledge

text: Alison

text: Etheridge

text: (University

text: of

text: Oxford)

text: to

text: have

text: noticed

text: that

text: the

text: main

text: points

text: of

text: Theorem

text: must

text: hold.

text: References

text: Ivo

text: Adan

text: and

text: Jacques

text: Resing.

text: Circular

text: Markov

text: chains.

text: Technical

text: Report

text: Memorandum

text: COSOR

text: Eindhoven

text: University

text: of

text: Technology,

text: Eindhoven,

text: The

text: Netherlands,

text: URL

text: Andras

text: Gyorgy

text: and

text: Domitilla

text: Del

text: Vecchio.

text: Modular

text: composition

text: of

text: gene

text: tran-

text: scription

text: networks.

text: PLoS

text: Computational

text: Biology,

text: Mar

text: doi:

text: S.

text: Karlin

text: and

text: H.

text: M.

text: Taylor.

text: A

text: ﬁrst

text: course

text: in

text: stochastic

text: processes.

text: Academic

text: Press

text: London,

text: F.

text: Leighton

text: and

text: Ronald

text: L.

text: Rivest.

text: Estimating

text: a

text: probability

text: using

text: ﬁnite

text: memory.

text: IEEE

text: Transactions

text: on

text: Information

text: Theory,

text: Nov

text: ISSN

text: doi:


text: [5] T. Liggett. Continuous time Markov processes: An introduction. American Mathematical Society, 2010. [6] Bence Mélykúti, João P. Hespanha, and Mustafa Khammash. Equilibrium distribu- tions of simple biochemical reaction systems for time-scale separation in stochastic re- action networks. Journal of the Royal Society Interface, 11(97):20140054, Aug 2014. doi: 10.1098/rsif.2014.0054. [7] J. R. Norris. Markov chains. Cambridge University Press, 1998. [8] Allen L. Roginsky. A central limit theorem for cumulative processes. Advances in Applied Probability, 26(1):104–121, Mar 1994. URL http://www.jstor.org/stable/1427582. [9] Richard Serfozo. Basics of applied stochastic processes. Springer, 2009. [10] W. L. Smith. Regenerative stochastic processes. Proc. Roy. Soc. Lond. Ser. A., 232:6–31, 1955. 29

label: reference

text: T.

text: Liggett.

text: Continuous

text: time

text: Markov

text: processes:

text: An

text: introduction.

text: American

text: Mathematical

text: Society,

text: Bence

text: Mélykúti,

text: João

text: P.

text: Hespanha,

text: and

text: Mustafa

text: Khammash.

text: Equilibrium

text: distribu-

text: tions

text: of

text: simple

text: biochemical

text: reaction

text: systems

text: for

text: time-scale

text: separation

text: in

text: stochastic

text: re-

text: action

text: networks.

text: Journal

text: of

text: the

text: Royal

text: Society

text: Interface,

text: Aug

text: doi:

text: J.

text: R.

text: Norris.

text: Markov

text: chains.

text: Cambridge

text: University

text: Press,

text: Allen

text: L.

text: Roginsky.

text: A

text: central

text: limit

text: theorem

text: for

text: cumulative

text: processes.

text: Advances

text: in

text: Applied

text: Probability,

text: Mar

text: URL

text: Richard

text: Serfozo.

text: Basics

text: of

text: applied

text: stochastic

text: processes.

text: Springer,

text: W.

text: L.

text: Smith.

text: Regenerative

text: stochastic

text: processes.

text: Proc.

text: Roy.

text: Soc.

text: Lond.

text: Ser.

text: A.,


text: ∈ { } δ A, B denote the event that the ﬁrst transition of the glued chain is a transition within X chain δ. Then we let | X p := P(σ < σ , A = 1), 1A1 1 2 0 | X p := P(σ < σ , A = 1), 1A2 2 1 0 X S that is, starting from state 1, p is the probability that leaves 1 for A and returns to 1 1A1 X before it enters 2, while p is the probability that leaves 1 with a transition from QA and 1A2 enters 2 before it returns to 1. It is straightforward to deﬁne the respective quantities with B in place of A. All notations X so far introduced for can be recast with 1 and 2 interchanged. In addition to probabilities, we also need the intensities of leaving on diﬀerent excursions, so we let ∈ { } (cid:48) ∈ { } qδ (cid:48) := q pδ (cid:48) (δ A, B , ε, ε 1, 2 ). (4) εδε εδ εδε (cid:90) ∈ S V \ { } We deﬁne random variables χδ(cid:48)(k) for a state k δ = δ 1, 2 by ε σδ(cid:48) X χδ(cid:48)(k) := ε 1( δ = k) dt. ε t 0 X ∈ S That is, χδ(cid:48)(k) is the time spent by δ in a state k δ on a transition path from the initial εX (cid:48) ∈ { } state until δ reaches state ε 1, 2 . We need a notion of conditional expectation of χδ(cid:48)(k) (cid:104) (cid:12) ∈ { (cid:105) } ε with initial s(cid:12)tate ε 1, 2 , which we deﬁne the following way: (cid:12)  (cid:46) E χδ(cid:48)(k) σδ(cid:48) < σδ−(cid:48) := ε ε ε 3 ε  (cid:54) E [χδ(cid:48)(k)1(σδ(cid:48) < σδ− (cid:48))] P (σδ(cid:48) < σδ− (cid:48)), if P (σδ(cid:48) < σδ− (cid:48)) = 0, ε ε ε 3 ε ε ε 3 ε ε ε 3 ε 0, otherwise. · · (P ( ), E [ ] are the usual probability, respectively, expectation when the process is started ε ε from ε. The expectations in this paper are all ﬁnite because the state spaces are ﬁnite and (cid:104) (cid:12) (cid:105) irreducible.) For compactness, we use the shorthand(cid:12) (cid:12) E (cid:48)[χδ(cid:48)(k)] := E χδ(cid:48)(k) σδ(cid:48) < σδ− (cid:48) . εε ε ε ε ε 3 ε ∈ ∞ − ∈ ∞ − We introduce the vectors v, w [0, [r 2, x, y [0, [s 2 by 6

text: δ

text: A,

text: B

text: denote

text: the

text: event

text: that

text: the

text: ﬁrst

text: transition

text: of

text: the

text: glued

text: chain

text: is

text: a

text: transition

text: within

text: X

text: chain

text: δ.

text: Then

text: we

text: let

text: X

text: p

text: P(σ

text: σ

text: A

text: X

text: p

text: P(σ

text: σ

text: A

text: X

text: S

text: that

text: is,

text: starting

text: from

text: state

text: p

text: is

text: the

text: probability

text: that

text: leaves

text: for

text: A

text: and

text: returns

text: to

text: X

text: before

text: it

text: enters

text: while

text: p

text: is

text: the

text: probability

text: that

text: leaves

text: with

text: a

text: transition

text: from

text: QA

text: and

text: enters

text: before

text: it

text: returns

text: to

text: It

text: is

text: straightforward

text: to

text: deﬁne

text: the

text: respective

text: quantities

text: with

text: B

text: in

text: place

text: of

text: A.

text: All

text: notations

text: X

text: so

text: far

text: introduced

text: for

text: can

text: be

text: recast

text: with

text: and

text: interchanged.

text: In

text: addition

text: to

text: probabilities,

text: we

text: also

text: need

text: the

text: intensities

text: of

text: leaving

text: on

text: diﬀerent

text: excursions,

text: so

text: we

text: let

text: qδ

text: q

text: pδ

text: (δ

text: A,

text: B

text: ε,

text: ε

text: εδε

text: εδ

text: εδε

text: S

text: V

text: We

text: deﬁne

text: random

text: variables

text: for

text: a

text: state

text: k

text: δ

text: δ

text: by

text: ε

text: X

text: ε

text: δ

text: k)

text: dt.

text: ε

text: t

text: X

text: S

text: That

text: is,

text: is

text: the

text: time

text: spent

text: by

text: δ

text: in

text: a

text: state

text: k

text: δ

text: on

text: a

text: transition

text: path

text: from

text: the

text: initial

text: εX

text: state

text: until

text: δ

text: reaches

text: state

text: ε

text: We

text: need

text: a

text: notion

text: of

text: conditional

text: expectation

text: of

text: ε

text: with

text: initial

text: ε

text: which

text: we

text: deﬁne

text: the

text: following

text: way:

text: E

text: ε

text: ε

text: ε

text: ε

text: E

text: σδ−

text: P

text: σδ−

text: if

text: P

text: σδ−

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: ε

text: otherwise.

text: (P

text: E

text: are

text: the

text: usual

text: probability,

text: respectively,

text: expectation

text: when

text: the

text: process

text: is

text: started

text: ε

text: ε

text: from

text: ε.

text: The

text: expectations

text: in

text: this

text: paper

text: are

text: all

text: ﬁnite

text: because

text: the

text: state

text: spaces

text: are

text: ﬁnite

text: and

text: irreducible.)

text: For

text: compactness,

text: we

text: use

text: the

text: E

text: E

text: σδ−

text: εε

text: ε

text: ε

text: ε

text: ε

text: ε

text: We

text: introduce

text: the

text: vectors

text: v,

text: w

text: [r

text: x,

text: y

text: [s

text: by


text: X X 3.1 Calculation for the chains A and B X Let the random variable τ be the length of one segment of as a regenerative process (the X ∈ { } inter-renewal time), and deﬁne τδ analogously for δ (δ A, B ). Further, let Xδ(i) denote X ∈ V the total time spent by δ in a state i δ in a complete segment. Using the ergodic theorem for regenerative processes for the ﬁrst equality in each line, and using the second numbered ∈ S list for the second equality in each line, for i (cid:18)A, − − (cid:19) πA = E[τA] 1E[XA(i)] = E[τA] 1 E[ξA ]E [χA(i)] + E [χA(i)] i 1A1 11 1 12 2 (cid:18) (cid:19) + E[ξA ]E [χA(i)] + E [χA(i)] , 2A2 22 2 21 1 − − (cid:18) 1 1 (cid:19) πA = E[τA] 1E[XA(1)] = E[τA] 1 E[ξA ] + + 0 + 0 , 1 1A1 q q 1A 1A − − 1 1 πA = E[τA] 1E[XA(2)] = E[τA] 1 0 + 0 + E[ξA ] + . (12) 2 2A2 q q 2A 2A The parameter of the nonnegative geometric random variable ξA is 1A1 ∈ pA = qA /q ]0, 1] 1A2 1A2 1A (cf. Eq. (4)). By Eqs. (3) and (4), its mean is − 1 pA pA qA E[ξA ] = 1A2 = 1A1 = 1A1 , 1A1 pA pA qA 1A2 1A2 1A2 and similarly, pA qA E[ξA ] = 2A2 = 2A2 . 2A2 pA qA 2A1 2A1 Note that E[ξA ] = pA = 0 is possible, e.g. if the state 1 is not connected to any other 1A1 1A1 state than 2. All the other analogous mean numbers of returning excursions might be zero for certain state space diagrams. It is also true that qδ might be zero, but qδ − will always be εδε ε,δ,3 ε positive because of irreducibility. Let us substitute the expressions for E[ξA ] and E[ξA ] into the formulae for πA, Eqs. (12), 1A1 2A2 i and for πA and πA use 1 2 qA + qA = q , 1A1 1A2 1A qA + qA = q . 2A1 2A2 2A 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: X

label: section

text: X

text: Calculation

text: for

text: the

text: chains

text: A

text: and

text: B

text: X

text: Let

text: the

text: random

text: variable

text: τ

text: be

text: the

text: length

text: of

text: one

text: segment

text: of

text: as

text: a

text: regenerative

text: process

text: (the

text: X

text: inter-renewal

text: time),

text: and

text: deﬁne

text: τδ

text: analogously

text: for

text: δ

text: (δ

text: A,

text: B

text: Further,

text: let

text: Xδ(i)

text: denote

text: X

text: V

text: the

text: total

text: time

text: spent

text: by

text: δ

text: in

text: a

text: state

text: i

text: δ

text: in

text: a

text: complete

text: segment.

text: Using

text: the

text: ergodic

text: theorem

text: for

text: regenerative

text: processes

text: for

text: the

text: ﬁrst

text: equality

text: in

text: each

text: line,

text: and

text: using

text: the

text: second

text: numbered

text: S

text: list

text: for

text: the

text: second

text: equality

text: in

text: each

text: line,

text: for

text: i

label: equation

text: πA

text: E[τA]

text: E[τA]

text: E[ξA

text: ]E

text: [χA(i)]

text: E

text: [χA(i)]

text: i

text: E[ξA

text: ]E

text: [χA(i)]

text: E

text: [χA(i)]

text: πA

text: E[τA]

text: E[τA]

text: E[ξA

text: q

text: q

text: πA

text: E[τA]

text: E[τA]

text: E[ξA

text: q

text: q

text: The

text: parameter

text: of

text: the

text: nonnegative

text: geometric

text: random

text: variable

text: ξA

text: is

text: pA

text: qA

text: /q

text: (cf.

text: Eq.

text: By

text: Eqs.

text: and

text: its

text: mean

text: is

text: pA

text: pA

text: qA

text: E[ξA

text: pA

text: pA

text: qA

text: and

text: similarly,

text: pA

text: qA

text: E[ξA

text: pA

text: qA

text: Note

text: that

text: E[ξA

text: pA

text: is

text: possible,

text: e.g.

text: if

text: the

text: state

text: is

text: not

text: connected

text: to

text: any

text: other

text: state

text: than

text: All

text: the

text: other

text: analogous

text: mean

text: numbers

text: of

text: returning

text: excursions

text: might

text: be

text: zero

text: for

text: certain

text: state

text: space

text: diagrams.

text: It

text: is

text: also

text: true

text: that

text: qδ

text: might

text: be

text: zero,

text: but

text: qδ

text: will

text: always

text: be

text: εδε

text: ε

text: positive

text: because

text: of

text: irreducibility.

text: Let

text: us

text: substitute

text: the

text: expressions

text: for

text: E[ξA

text: and

text: E[ξA

text: into

text: the

text: formulae

text: for

text: πA,

text: Eqs.

text: i

text: and

text: for

text: πA

text: and

text: πA

text: use

text: qA

text: qA

text: q

text: qA

text: qA

text: q

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 3.3 The Hamiltonian and the free energy The second key component of the KKLS model is the Hamiltonian, a real- valued function of W that in physical terms measures the thermodynamic internal energy of the system. The simplest plausible form for H is H(W ) = − · 1u W W where u is a constant; this corresponds to long-range particle 2 interactions with no inter-particle correlations (see [27]). A slightly more general expression [31],[32] is a quadratic function of the form −1 · H(W ) = BW W (14) 2 → where B is a symmetric linear map L(E) L(E). We assume that B is equivariant with respect to the left action λ of G on L(E) (intrinsic frame-independence when G = SO(3)), so that H is λ-invariant. F → Finally, the (Helmholtz) free energy function : L(E) R is deﬁned by F − := H(W ) T S (15) where here T denotes absolute temperature. Since W, S are functions of F η as in (6),(11) we could regard as a function of η. However, the physical motivation for this construction [32] is that equilibrium states of the liquid crystal correspond to values of the order parameter W that are critical points of the free energy viewed as a function of W . To ﬁnd equilibrium states we thus need ﬁrst to convert S(η) into a function of W , that is to invert the map (cid:55)→ η W (η). By the Inverse Function Theorem (IFT) this can always be done ∈ locally in a neighbourhood of any given η L(E) in view of the following result. First some terminology: we say that the action α spans L(E) if the set { ∈ } α(G) := α(g) : g G does not lie in any proper aﬃne subspace (hyper- plane) of L(E). We prove in Appendix D that this holds for the conjugacy action of G = SO(3) on V , and leave as an easy exercise that it holds for the natural action of D on R2. For a ﬁnite group G an obvious necessary | | ≥ 3 condition is that G dim L(E). Proposition 5 If the action α spans L(E) then the derivative DW (η) : → ∈ L(E) L(E) is invertible for every η L(E). (cid:90) Proof. We generalise the argument given in [27]. Diﬀerentiating · Z(η)W (η) = α(g)eη α(g) G 14 ##LTLine## ##LTLine##

text: The

text: Hamiltonian

text: and

text: the

text: free

text: energy

text: The

text: second

text: key

text: component

text: of

text: the

text: KKLS

text: model

text: is

text: the

text: Hamiltonian,

text: a

text: real-

text: valued

text: function

text: of

text: W

text: that

text: in

text: physical

text: terms

text: measures

text: the

text: thermodynamic

text: internal

text: energy

text: of

text: the

text: system.

text: The

text: simplest

text: plausible

text: form

text: for

text: H

text: is

text: H(W

text: W

text: W

text: where

text: u

text: is

text: a

text: constant;

text: this

text: corresponds

text: to

text: long-range

text: particle

text: interactions

text: with

text: no

text: inter-particle

text: correlations

text: (see

text: A

text: slightly

text: more

text: general

text: expression

text: is

text: a

text: quadratic

text: function

text: of

text: the

text: form

text: −1

text: H(W

text: BW

text: W

text: where

text: B

text: is

text: a

text: symmetric

text: linear

text: map

text: L(E)

text: L(E).

text: We

text: assume

text: that

text: B

text: is

text: equivariant

text: with

text: respect

text: to

text: the

text: left

text: action

text: λ

text: of

text: G

text: on

text: L(E)

text: (intrinsic

text: frame-independence

text: when

text: G

text: so

text: that

text: H

text: is

text: λ-invariant.

text: F

text: Finally,

text: the

text: (Helmholtz)

text: free

text: energy

text: function

text: L(E)

text: R

text: is

text: deﬁned

text: by

text: F

text: H(W

text: T

text: S

text: where

text: here

text: T

text: denotes

text: absolute

text: temperature.

text: Since

text: W,

text: S

text: are

text: functions

text: of

text: F

text: η

text: as

text: in

text: we

text: could

text: regard

text: as

text: a

text: function

text: of

text: η.

text: However,

text: the

text: physical

text: motivation

text: for

text: this

text: construction

text: is

text: that

text: equilibrium

text: states

text: of

text: the

text: liquid

text: crystal

text: correspond

text: to

text: values

text: of

text: the

text: order

text: parameter

text: W

text: that

text: are

text: critical

text: points

text: of

text: the

text: free

text: energy

text: viewed

text: as

text: a

text: function

text: of

text: W

text: To

text: ﬁnd

text: equilibrium

text: states

text: we

text: thus

text: need

text: ﬁrst

text: to

text: convert

text: S(η)

text: into

text: a

text: function

text: of

text: W

text: that

text: is

text: to

text: invert

text: the

text: map

text: η

text: W

text: (η).

text: By

text: the

text: Inverse

text: Function

text: Theorem

text: (IFT)

text: this

text: can

text: always

text: be

text: done

text: locally

text: in

text: a

text: neighbourhood

text: of

text: any

text: given

text: η

text: L(E)

text: in

text: view

text: of

text: the

text: following

text: result.

text: First

text: some

text: terminology:

text: we

text: say

text: that

text: the

text: action

text: α

text: spans

text: L(E)

text: if

text: the

text: set

text: α(G)

text: α(g)

text: g

text: G

text: does

text: not

text: lie

text: in

text: any

text: proper

text: aﬃne

text: subspace

text: (hyper-

text: plane)

text: of

text: L(E).

text: We

text: prove

text: in

text: Appendix

text: D

text: that

text: this

text: holds

text: for

text: the

text: conjugacy

text: action

text: of

text: G

text: on

text: V

text: and

text: leave

text: as

text: an

text: easy

text: exercise

text: that

text: it

text: holds

text: for

text: the

text: natural

text: action

text: of

text: D

text: on

text: For

text: a

text: ﬁnite

text: group

text: G

text: an

text: obvious

text: necessary

text: condition

text: is

text: that

text: G

text: dim

text: L(E).

text: Proposition

text: If

text: the

text: action

text: α

text: spans

text: L(E)

text: then

text: the

text: derivative

text: DW

text: (η)

text: L(E)

text: L(E)

text: is

text: invertible

text: for

text: every

text: η

text: L(E).

text: Proof.

text: We

text: generalise

text: the

text: argument

text: given

text: in

text: Diﬀerentiating

text: Z(η)W

text: (η)

text: α(g)eη

text: α(g)

text: G

text: ##LTLine##

text: ##LTLine##