Lattie walks everywhere j m b2 c1 a0 b1 jf c1 b1 if m Mireille Bousquet-Mélou, CNRS, LaBRI, U. Bordeaux 1, Frane i 1. Continued frations [1980℄ 1 1 − c0 − 1 − c1 − a1 b2 1 −··· b1 a0 2. A storage alloation sheme [1986℄ p size b2 c1 a0 b1 c1 b1 j m m p 2(p + q) = 1 q q jf !!! if m i 3. A paking problem [1998℄, with Comann, Flatto and Hofri Two papers 1. Basi analyti ombinatoris of direted lattie paths (with C. Banderier, 2002) 2. The enumeration of prudent polygons by area and its unusual asymptotis (with N. Beaton and T. Guttmann, 2011) spei problems general solutions I. Basi analyti ombinatoris of direted lattie paths (with C. Banderier, 2002) The problem Let S ⊂ Z be a nite subset of steps. Consider walks on Z, starting from 0, that take their steps in S . • The problem Let S ⊂ Z be a nite subsets of steps. Consider walks on Z, starting from 0, that take their steps in S . • What is the generating funtion of... general walks? bridges? • W (z, u) z: meanders? 11111111111 00000000000 00000000 11111111 00000000000 11111111 11111111111 00000000 B(z) the number of steps, or length; exursions? E(z) u: M (z, u) the height of the nal point Results 1. Exat expressions of the series [Gessel 80℄ + [MBM-Petkov²ek 00℄, [Banderier, MBM, Denise, Flajolet, Gardy, Gouyou-Beauhamps 02℄ 2. Uniform asymptoti results 2. Uniform limit laws general walks W (z, u) bridges B(z) exursions meanders 11111111111 00000000000 00000000 11111111 00000000000 11111111 11111111111 00000000 E(z) M (z, u) Exat expressions of the series: general walks and bridges Let −m = min S and M = max S , and let P (u) = X i∈S ωiui = M X ωiui i=−m be the generating polynomial of (possibly weighted) steps. • The generating funtion of general walks is 1 . W (z, u) = 1 − zP (u) Exat expressions of the series: general walks and bridges Let −m = min S and M = max S , and let P (u) = X i∈S ωiui = M X ωiui i=−m be the generating polynomial of (possibly weighted) steps. • The generating funtion of general walks is 1 . W (z, u) = 1 − zP (u) The oeient of u0 in W (z, u) ounts bridges. It an be obtained from a partial fration expansion in u: • m U ′(z) X i , B(z) = z i=1 Ui(z) where U1(z), . . . , Um(z) are the m solutions of 1 − zP (U ) = 0 that are nite at z = 0. Exat expressions of the series: exursions and meanders • The generating funtion of exursions is m (−1)m−1 Y Ui(z) E(z) = zω−m i=1 where U1(z), . . . , Um(z) are the m solutions of 1 − zP (U ) = 0 that are nite at z = 0. • More generally, the generating funtion of meanders is Qm (u − Ui(z)) . M (z, u) = i=1 m u (1 − zP (u)) Proof: a funtional equation and the kernel method • Step-by-step onstrution of meanders: If S = {−2, 3}, then M (z, u) = 1 + 3 z(u + u −2 )M (z, u) − z M0(z)u −2 + M1(z)u add an arbitrary step... ... but if the nal level is 0 or 1 one should not add a down step −1 Proof: a funtional equation and the kernel method Equivalently, u 2 3 1 − z(u + u −2 ) M (z, u) = u2 − zM0(z) − zM1(z)u The left-hand side vanishes when u = U1(z) and u = U2(z), where U1 and U2 are the two roots of • that are nite when z = 0. 1 − z(u3 + u−2) = 0 The right-hand side is a polynomial in u of degree 2, leading oeient 1, that anels when u = U1(z) and u = U2(z). Hene • u 2 3 1 − z(u + u and the expression −2 ) M (z, u) = (u − U1(z))(u − U2(z)) M (z, u) = follows. (u − U1(z))(u − U2(z)) u2(1 − z(u3 + u−2)) Two stowaways • A bijetion shows that Hene E ′(z) B(z) = 1 + z . E(z) m U ′(z) X i B(z) = z i=1 Ui(z) ⇒ E(z) = (The onstant is the easily determined using st m Y z i=1 E(0) = 1.) Ui(z). Two stowaways • A bijetion shows that Hene E ′(z) B(z) = 1 + z . E(z) m U ′(z) X i B(z) = z i=1 Ui(z) ⇒ E(z) = (The onstant is the easily determined using st m Y z i=1 E(0) = 1.) Ui(z). An algorithm, based on symmetri funtions manipulations, omputes an algebrai equation for the exursion generating funtion • m (−1)m−1 Y E(z) = Ui(z) z i=1 In plethysti notation, it expresses the symmetri funtions ej [em] in terms of the ei's. The platypus algorithm Asymptotis for bridges and exursions Theorem. Let τ > 0 be the unique solution of P ′(τ ) = 0, where P is the generating polynomial of steps. Then the numbers of bridges and exursions of length n behave asymptotially as b1 n −1/2 + ··· Bn = P (τ ) n b0 + n e En = P (τ )n n−3/2 e0 + 1 + · · · n Proof: the saddle-point method for bridges, sine 1 du Bn = P (u)n 2iπ C u Z As a by-produt, this ditates the singular behaviour of the series Ui(z), from whih one derives the singular behaviour of E(z). Asymptotis for general walks and meanders Theorem. Let τ > 0 be the unique solution of P ′(τ ) = 0, where P is the generating polynomial of steps. • The numbers of walks is Wn = P (1)n The asymptoti behaviour of the number of meanders (= non-negative walks) depends on the drift • δ = P ′(1) ⋆ If δ > 0, a positive fration of walks are meanders: m1 n n −3/2 m0 + + ··· Mn = κP (1) + P (τ ) n n ⋆ If δ < 0, m1 n −3/2 Mn = P (τ ) n m0 + + ··· n m Mn = P (τ )n n−1/2 m0 + 1 + · · · n ⋆ If δ = 0, Limit laws for basi parameters • The number of ontats of an exursion with the x-axis (disrete limit law) • The position Yn of the endpoint of a meander ⋆ If δ > 0, Yn − µn → Gaussian √ n ⋆ If δ < 0, disrete limit law ⋆ If δ = 0, Yn √ → Rayleigh n II. The enumeration of prudent polygons by area, and its unusual asymptotis (with N. Beaton and T. Guttmann, 2011) Self-avoiding polygons Self-avoiding polygons • Awfully hard to ount • Conjetured asymptotis: for polygons of area n, pn ∼ κµnn0, where the exponent depends only on the dimension An easier family: 3-sided prudent polygons Prudent walks: a step never points towards a vertex it has already visited Prudent walk Prudent polygon [Turban-Debierre 86℄, [Préa 97℄, [Santra-Seitz-Klein 01℄, [Duhi 05℄, [Dethridge, Guttmann, Jensen 07℄, [mbm 08℄, [Beara, Friedli, Velenik 10℄... An easier family: 3-sided prudent polygons Prudent walks: a step never points towards a vertex it has already visited Prudent polygon An easier family: 3-sided prudent polygons Prudent walks: a step never points towards a vertex it has already visited Prudent polygon Three-sided prudent polygon An easier family: 3-sided prudent polygons Three-sided prudent polygons deompose into bars, bargraphs, and separating ells [...℄ and their area generating funtion is 2q(3 − 10q + 9q 2 − q 3) + P (q) = 2 (1 − 2q) (1 − q) m−1 Y 1 − q − q k + q k+1 − q k+2 2q 3(1 − q)2 X (−1)m+1q 2m (1 − 2q)2 m≥1 (1 − 2q)m(1 − q − q m+1) k=1 1 − q − q k+1 Asymptotis • The series: 2q(3 − 10q + 9q 2 − q 3) + P (q) = 2 (1 − 2q) (1 − q) m−1 Y 1 − q − q k + q k+1 − q k+2 2q 3(1 − q)2 X (−1)m+1q 2m (1 − 2q)2 m≥1 (1 − 2q)m(1 − q − q m+1) k=1 1 − q − q k+1 A beautiful singularity analysis yields a very unusual asymptoti behaviour in the study of lattie models: • Pn = (κ0 + κ(log2 n))2n nγ + O(log n 2nnγ−1) where the exponent γ is irrational γ = log2 3 and κ(x) is a (small) periodi funtion of x. Remark. Similar to (but more omplex than) the analysis of the expeted longest run in a random binary sequene, where the key series is qk (1 − q) . k+1 1 − 2q + q k≥0 X

© Copyright 2021 DropDoc