3 Asymptotic results in the general case

(1)

Enumeration of walks reaching a line

Philippe Nadeau

Laboratoire de Recherche en informatique, Bˆat. 490, Universit´e Paris Sud, 91405 ORSAY Cedex, France

We enumerate walks in the planeR², with steps East and North, that stop as soon as they reach a given line; these walks are counted according to the distance of the line to the origin, and we study the asymptotic behavior when the line has a fixed slope and moves away from the origin. When the line has a rational slope, we study a more general class of walks, and give exact as well as asymptotic enumerative results ; for this, we define a nice bijection from our walks to words of a rational language. For a general slope, asymptotic results are obtained; in this case, the method employed leads us to find asymptotic results for a wider class of walks inR^m.

Keywords:walk, generating function, rational language, singularity analysis

1 Introduction

In this work we consider primarily two classes of walks in the planeR², notedW_a,δ⁺ andW_a,δ⁻ , defined in the following manner :

Definition 1 Leta∈[0,1[andδ>0be real numbers. We denote byDa,δthe line ofR²with slope−a, going through the point(δ,0). An equation ofDa,δisy =−a(x−δ). We denote byW_a,δ⁺ (resp.W_a,δ⁻ ) the set of walks in the planeR²starting at the originO= (0,0)with steps East or North, which end as soon as they reach the open (resp.closed) half plane aboveDa,δ. The cardinalities of the setsW_a,δ⁺ and W_a,δ⁻ are denoted respectively byW_a,δ⁺ andW_a,δ⁻ .

These definitions are illustrated on Figure 1.

These walks stop as soon as they cross the lineDa,δ, those inW_a,δ⁺ having to go strictly beyond the line, whereas those inW_a,δ⁻ stop on it if they happen to touch it. We are interested in the enumeration of these walks according to the parameterδ; that is, we fix the slope−aof the lineDa,δ, and study the numbersW_a,δ⁺ andW_a,δ⁻ in function ofδ. Note that, up to a constant factora,δrepresents the distance of the lineDa,δto the origin.

We can now state our first theorem which gives all asymptotic results forW_a,δ⁺ andW_a,δ⁻ whenδgoes to infinity.

Theorem 1 Leta∈]0,1], and letλbe the unique positive solution to the equationλ⁻¹+λ^−1/a= 1.

Ifa=p/q >0is a fixed rational number, wherepandqare relatively prime positive integers, then the asymptotic approximations

W_a,δ⁺ ∼

∞

a

p(1−λ^−1/p)· 1

1−(1−a)λ⁻¹λ^bpδc/p and W_a,δ⁻ ∼

∞

a

p(λ^1/p−1)· 1

1−(1−a)λ⁻¹λ^bpδc/p

1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

(2)

000000 111111 000000 111111 000000 111111

000000 111111 000000 111111

000000 111111 000000 111111 000000 111111 000000 111111

000000 111111

000000 111111 000000

111111 000000

111111

O

Fig. 1:An example of walk inW_a,δ⁺ witha=³₇ andn= 14.

hold whenδgoes to infinity. Ifais irrational, then the asymptotic approximations

W_a,δ⁺ ∼

∞

a

lnλ· 1

1−(1−a)λ⁻¹λ^δ and W_a,δ⁻ ∼

∞

a

lnλ· 1

1−(1−a)λ⁻¹λ^δ

hold whenδgoes to infinity.

As this theorem shows, the behavior ofW_a,δ⁺ andW_a,δ⁻ depends on the rationality of the numbera; if ais rational, then we will find the generating function of the numbersW_a,n⁺ andW_a,n⁻ . In this case, we will actually introduce another class of walks that includesW_a,n⁺ andW_a,n⁻ and find a bijection that sends walks to words of a rational language; various enumerative and asymptotic results derive from there. In the case of a generala, we will proceed differently, and start from an easily obtained functional equation to obtain asymptotic results. Our method is close to Erd¨os et al. (EHO⁺87), method that is also applicable to a wider class of walks defined inRⁿ.

2 Walks reaching a set of points

As announced in the introduction, we now introduce a new class of walks that will include our original walks when the slope ofD_a,δ is rational. The reader is advised to look at Figure 2 while reading the following definition.

Definition 2 (V_d,nandWd,n) Letd= (d_i)_i_>₁be an infinite sequence of positive integers, and lete = (e_i)_i∈_Nbe the corresponding sequence of partial sums, defined bye₀= 0ande_k =d₁+d₂+· · ·+d_k, fork>1. We associate toda set of pointsV_din the plane, with integer coordinates: the setV_d⊂Z×N consists in the originOtogether with, for everyk > 1, thed_k points withy-coordinate equal tokand x-coordinate in[[−ek,−e_k−1−1]].

For any integern,Vd,nis defined as the translated ofVdby the vector(n,0). That is,Vd,n=Vd+(n,0).

Thegeneralized set of walksWd,n consists of the walks that start at the originO, make steps East or North, and have their last points, and no other one, inV_d,n.

These walks are a generalization of our walksW_a,n⁺ andW_a,n⁻ . Indeed, letd⁺_a andd⁻_a be the sequences whosekth terms are given respectively byd^k_ae − d^k−1_a eandb^k_ac − b^k−1_a c. Then we have the following proposition :

(3)

0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111 0000 1111

Fig. 2:A setVd,nwith examples of walks inWd,n. Heren= 14andd= (3,1,2,3,6,1,1, . . .)

Proposition 1 For everyn∈Nanda∈]0,1], we have the equalities W_a,n⁺ =W_d+

a,n+1andW_a,n⁻ =W_d− a,n.

An interesting case happens when the sequencedis periodic. It is easy to see that d⁺_a andd⁻_a are periodic exactly when ais a rational number. Ifd = (d₁, . . . , d_p) is a finite sequence, we will note Vd,n=Vd,n¯ andWd,n=Wd,n¯ , whered¯is the periodic infinite sequence(d1, . . . , dp, d1, . . . , dp, . . .).

From now on d will stand for a finite sequence d = (d1, . . . , dp)of positive integers. We define q=d1+· · ·dp, anda=p/q. To such a sequence we attach the following language on a finite alphabet (recall that arunin a finite word is a maximal factor composed of identical letters)

Definition 3 (LanguageLd) The languageLdis the set of wordswon the alphabetΣ ={a0, a1, . . . , ap−1} that satisfy the following conditions (where we set by conventiond0=dpandap=a0):

C1. wis the empty word, or its initial letter belongs to{a0, a1}

C2. for alli, a run ofa_iinwis terminal or is followed by a run ofa_i+1;

C3. for alli, the runs ofaiinware of length at leastdi; this constraint does not apply to the last run, and, ifwbegins witha0, it does not apply to the first run either.

We can finally state the theorem announced in the introduction:

Theorem 2 Letn>0be an integer. There exists an explicit bijection between walks inWd,nand words ofLdof lengthn.

The languageLdis rational, and we give an unambiguous rational expression that represents it. Then the existence of a bijection as stated in Theorem 2 allows us to explicit the generating functionWd(x) = P∞

k=0Wd,kx^k of the sequence(Wd,n)n∈N:

Theorem 3 The generating functionW_d(x)has the following expression:

Wd(x) = N(x)

(1−x)^p−x^q, withN(x) = (1−x)^p−2+

p−2

X

i=1

x^eⁱ⁺¹(1−x)^p−2−i+

ep−1

X

k=ep−1+1

x^k.

(4)

its series expansion, and we show that the first part of Theorem 1 can thus be obtained as a consequence of Theorem 3.

In fact, thanks to the bijection of Theorem 2, we can even find the bivariate generating function of the numbers(Wd,n,k)n,kwhich enumerate walks inWd,n of lengthk. By the techniques of singularity analysis exposed in chapter 8 of (FS), we can then prove that the average length of a walk inWd,n is asymptoticallyCa·nwhenngoes to infinity, whereCais positive constant depending only ona.

3 Asymptotic results in the general case

LetW_a⁺be the function defined onRbyW_a⁺(δ) = 1ifδ <0, and byW_a⁺(δ) = W_a,δ⁺ ifδ>0. Then, by decomposing walks according to their first step, one shows thatW_a⁺satisfies the following functional equation :

∀δ>0, W_a⁺(δ) =W_a⁺(δ−1/a) +W_a⁺(δ−1). (1) This equation and related ones have appeared in various contexts, and have been studied in numerous works, including (CG01; FK74; Pip93). Here we use a method inspired by the paper (EHO⁺87). This consists in interpreting Equation 1 as a “renewal equation”, so that its asymptotic behavior is given by the celebratedRenewal Limit Theorem(RLT) of probability theory; see Feller (Fel71) for all necessary back- ground. Application of the RLT immediately leads to a proof of Theorem 1 as far asW_a,δ⁺ is concerned.

It is then extended toW_a,δ⁻ by finding simple relations between the two numbers.

Our walks have a natural generalization in any dimension. Let ¯a = (a1, . . . , am) be a vector in R^m, with all coordinates being positive, andHδ be the hyperplane of equationHδ : a1x1+· · ·+ a_m−1x_m−1+am(xm−δ) = 0.Then defineW_¯_a,δ⁺ (resp. W_¯_a,δ⁻) to be the numbers of walks inR^mfrom the origin with steps in{ei}16i6mdefined by the fact that their last points, and no other one, are “above Hδ” (resp.“above or onHδ”).

Assume1 = am 6 a1 6 a2 6 . . . 6 am−1, and letλ designate the unique positive solution to Pm

i=1λ^−aⁱ = 1. If allaiare rational numbers and we writeai =pi/qiin reduced form for eachi, we defineq= lcm(q_i). Then the proof of the following theorem is proved along the same lines as described above :

Theorem 4 Letλandqbe defined as above. Then we have the following asymptotics whenδtends to∞:

(i) if at least onea_iis irrational, then

W_¯_a,δ⁺ ∼

∞

m−1 lnλ·Pm

i=1aiλ^−aⁱ ·λ^δ and W_¯_a,δ⁻ ∼

∞

m−1 lnλ·Pm

i=1aiλ^−aⁱ ·λ^δ, (ii) and if alla_iare rational, then

W_a,δ_¯⁺ ∼

∞

m−1 q(1−λ^−1/q)·Pm

i=1a_iλ^−aⁱ·λ^bqδc/q and W_a,δ_¯⁻ ∼

∞

m−1 q(λ^1/q−1)·Pm

i=1a_iλ^−aⁱ·λ^bqδc/q. In fact, the same reasoning shows that similar approximations hold in the irrational case when the steps are allowed to be any finite number of non zero vectors with nonnegative coordinates.

(5)

Acknowledgements

I would like to thank Yves Verhoeven who is at the origin of this work and helped me on many occasions during my researches.

References

[CG01] V. Choi and M. J. Golin. Lopsided trees. I. Analyses. Algorithmica, 31(3):240–290, 2001.

Mathematical analysis of algorithms.

[EHO⁺87] P. Erd˝os, A. Hildebrand, A. Odlyzko, P. Pudaite, and B. Reznick. The asymptotic behavior of a family of sequences. Pacific J. Math., 126(2):227–241, 1987.

[Fel71] William Feller. An introduction to probability theory and its applications. Vol. II. Second edition. John Wiley & Sons Inc., New York, 1971.

[FK74] Michael L. Fredman and Donald E. Knuth. Recurrence relations based on minimization. J.

Math. Anal. Appl., 48:534–559, 1974.

[FS] P. Flajolet and R. Sedgewick. Analytic combinatorics. Book in preparation. Preliminary version available at http://algo.inria.fr/flajolet/Publications/books.html.

[Pip93] Nicholas Pippenger. An elementary approach to some analytic asymptotics. SIAM J. Math.

Anal., 24(5):1361–1377, 1993.

(6)