Pascals formulas and vector fields Philippe Chassaing Jules Flin Alexis Zevio September 18 2023

2025-05-02 0 0 1.63MB 28 页 10玖币

侵权投诉

Pascal’s formulas and vector ﬁelds

Philippe Chassaing ∗

, Jules Flin †

, Alexis Zevio ‡

September 18, 2023

Abstract

We consider four examples of combinatorial triangles (T(n, k))0≤k≤n(Pascal,

Stirling of both types, Euler) : through saddle-point asymptotics, their Pas-

cal’s formulas deﬁne four vector ﬁelds, together with their ﬁeld lines that turn

out to be the conjectured limit of sample paths of four well known Markov

chains. We prove this asymptotic behaviour in three of the four cases.

Keywords. Markov chain, combinatorial triangle, Pascal formula, hydrody-

namic limit, vector ﬁeld.

Contents

1 Introduction 2

1.1 Pascal’sformulas ............................. 2

1.2 Transition probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Random walk, coupon collector, chinese restaurant, and internal DLA 3

1.3.1 Simple random walk . . . . . . . . . . . . . . . . . . . . . . . 3

1.3.2 Coupon collector’s problem . . . . . . . . . . . . . . . . . . . 3

1.3.3 Chinese restaurant process . . . . . . . . . . . . . . . . . . . . 3

1.3.4 One-dimensional Internal Diﬀusion Limited Aggregation . . . 4

1.4 Simulations ................................ 4

1.5 Asymptotics of sample paths, and ﬁeld lines of vector ﬁelds . . . . . . 6

1.5.1 Description of φ.......................... 7

2 Time reversal and Markov property for W8

2.1 Timereversal ............................... 8

2.2 Simplerandomwalk ........................... 10

2.3 Coupon collector’s problem . . . . . . . . . . . . . . . . . . . . . . . 11

2.4 Chinese restaurant process . . . . . . . . . . . . . . . . . . . . . . . . 12

2.5 One-dimensional Internal Diﬀusion Limited Aggregation process . . . 13

3 The limit vector ﬁeld : proof of Theorem 1 15

∗Institut ´

Elie Cartan, Universit´e de Lorraine Email: chassaingph@gmail.com

†Institut ´

Elie Cartan, Universit´e de Lorraine Email: jules.ﬂin8@etu.univ-lorraine.fr

‡Institut ´

Elie Cartan, Universit´e de Lorraine Email: alexis.zevio1@etu.univ-lorraine.fr

arXiv:2210.11814v2 [math.CO] 15 Sep 2023

4 Sample path convergence 20

4.1 Proof of Theorem 2 : Pascal’s triangle. . . . . . . . . . . . . . . . . . 20

4.2 Proof of Theorem 2 : Stirling numbers of the ﬁrst kind. . . . . . . . . 22

4.3 Proof of Theorem 2 : Stirling numbers of the second kind. . . . . . . 23

4.4 Application to the enumeration of accessible complete deterministic

automata with kletters and nvertices ................. 25

1 Introduction

1.1 Pascal’s formulas

Set S={(n, k)∈N2,0≤k≤n},˚

S={(n, k)∈N2,0< k < n}, and let S⋆=

S\{(0,0)}. Besides Pascal’s triangle, other triangular arrays (T(n, k))(n,k)∈Sof in-

terest satisfy a recursion formula similar to Pascal’s formula, i.e. of the following

form, for (n, k)∈S⋆:

T(n, k) = a(n, k)T(n−1, k −1) + b(n, k)T(n−1, k),(1)

with the convention that either (n, k)∈Sor T(n, k) = 0. For instance, relation (1)

holds true for the following triangular arrays :

•for Pascal’s triangle, if (a, b)(n, k) = (1,1) ;

•for Stirling numbers of the second kind, if (a, b)(n, k) = (1, k) ;

•for Stirling numbers of the ﬁrst kind, if (a, b)(n, k) = (1, n −1) ;

•for Euler’s triangle, if (a, b)(n, k) = (n−k, k + 1).

1.2 Transition probabilities

In view of (1), for (n, k)∈S⋆, consider

(p0(n, k), p1(n, k)) = b(n, k)T(n−1, k)

T(n, k),a(n, k)T(n−1, k −1)

T(n, k)(2)

as some transition probabilities from (n, k) to (n−1, k), resp. to (n−1, k −1). For

each of these four triangular arrays, the transition probabilities

(pε(n, k))(ε,(n,k))∈{0,1}×S⋆,

together with the initial state (m, ℓ), deﬁne a Markov chain W= (Wk)0≤k≤nwith

terminal state (0,0). These four Markov chains are closely related to the simple

random walk, the coupon collector problem, the chinese restaurant process and the

one-dimensional internal DLA, respectively : they are the time-reversed versions of

these processes, once these processes are conditioned to be at level ℓat time m, as

explained in the next section.

1.3 Random walk, coupon collector, chinese restaurant, and

internal DLA

Consider a random process deﬁned by X0= 0, and, for n⩾0, Xn+1 =Xn+Yn+1,

in which the Yi’s are Bernoulli random variables. Set

Wn= (m−n, Xm−n)∈S, 0≤n≤m,

wm(t) = m−1X⌊mt⌋∈S, 0≤t≤1,

and note that, by deﬁnition, Wn= (0,0) if and only if n=m.

1.3.1 Simple random walk

Assume that (Yi)i≥1is a Bernoulli process, i.e. a sequence of i.i.d. Bernoulli random

variables with parameter p∈(0,1). Then

Proposition 1. The stochastic process W= (Wn)0≤n≤m, conditioned to W0=

(m, ℓ), or equivalently to Xm=ℓ, is the Markov chain with transition probabilities

(pε(n, k))(ε,n,k)∈{0,1}×S⋆related to Pascal’s triangle. Its distribution does not depend

on p.

This result goes back at least to Kennedy [Ken75], or even to the introduction

of the concept of suﬃciency by Fisher around 1920 [Sti73]. We recall its proof at

Subsection 2. In the next cases, the Bernoulli random variables Yiare not i.i.d. .

1.3.2 Coupon collector’s problem

Consider the coupon collector’s problem with Ndiﬀerent items. Let Xndenote the

number of diﬀerent items in the collection after the nth step. Again :

Proposition 2. The stochastic process W= (Wn)0≤n≤m, conditioned on W0=

(m, ℓ), or equivalently on the number of diﬀerent items in the collection after the

mth step, Xm, to be equal to ℓ, is the Markov chain with transition probabilities

(pε(n, k))ε,n,k related to Stirling numbers of the second kind. Its distribution does

not depend on N.

1.3.3 Chinese restaurant process

In the Chinese restaurant process with (0, θ) seating plan, deﬁned at Section 2 (see

also, e.g., [Pit06, Ch. 3]), let Xndenote the number of occupied tables after the

arrival of the nth customer.

Proposition 3. The stochastic process W= (Wn)0≤n≤m, conditioned to W0=

(m, ℓ), or equivalently to Xm=ℓ, is the Markov chain with transition probabilities

(pε(n, k))ε,n,k related to Stirling numbers of the ﬁrst kind. Its distribution does not

depend on θ.

Remark 1. As a consequence, in the three previous cases, given the data (Xn)0≤n≤m,

Xm(or W0) are suﬃcient statistics for the parameters p,Nor θ, respectively.

1.3.4 One-dimensional Internal Diﬀusion Limited Aggregation

Finally, in the one-dimensional Internal Diﬀusion Limited Aggregation process (iDLA),

let Xndenote the number of particles settled to the right of the origin after the re-

lease of the nth particle. Then

Proposition 4. The stochastic process W= (Wn)0≤n≤m, conditioned to W0=

(m, ℓ), is the Markov chain with transition probabilities (pε(n, k))ε,n,k related to Eu-

ler’s triangle.

More precise deﬁnitions, and proofs, are to be found at Section 2.

1.4 Simulations

In the case of Pascal’s triangle, the behaviour of this time-reversed Markov chain is

well understood since forever. Quite recently, [AC19] gave a rather precise analysis

of the analog time-reversed Markov chain related to Stirling numbers of the second

kind, with combinatorial analysis of ﬁnite automata as a motivation. We hope to

improve some of their results and proofs.

In this section, in order to surmise the behaviour of these time-reversed Markov

chains, we present the result of some simulations. For each case, the ﬁgures below

show sample paths starting at (m, mt) with t∈ {0.05, ..., 0.95}and m= 500 :

Figure 1: Pascal’s triangle. Figure 2: Stirling numbers of the

second kind.

Figure 3: Stirling numbers of the

ﬁrst kind. Figure 4: Eulerian numbers.

Now, in order to compare the four combinatorial triangles, we show the average

of 100 sample paths for each triangle, for m= 1000 and t∈ {0.05, ..., 0.95}:

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Pascal’sformulasandvectorfieldsPhilippeChassaing∗,JulesFlin†,AlexisZevio‡September18,2023AbstractWeconsiderfourexamplesofcombinatorialtriangles(T(n,k))0≤k≤n(Pascal,Stirlingofbothtypes,Euler):throughsaddle-pointasymptotics,theirPas-cal’sformulasdefinefourvectorfields,togetherwiththeirfieldlinesthattu...

展开>> 收起<<

Pascals formulas and vector fields Philippe Chassaing Jules Flin Alexis Zevio September 18 2023.pdf

共28页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Pascals formulas and vector fields Philippe Chassaing Jules Flin Alexis Zevio September 18 2023

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: