A FROG ’ S RANDOM JUMP AND THE P ÓLYA IDENTITY
A FROG ’ S RANDOM JUMP AND THE P ÓLYA IDENTITY
复制标题
青蛙的随机跳跃和波利亚恒等式
DOI：
10.1016/j.ejc.2005.07.012
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
N. Tokushige
中科院分区：
文献类型：
--
作者：
N. Tokushige
青蛙沿着x轴上的晶格点跳跃。从x = x0开始，他每次以概率p向左跳`步，或者以概率1 − p向右跳r步。他到达原点的概率是多少？我们用一个关于∑k≥0（ck+ sdk +t）zk的封闭公式来回答这个问题，这个公式是P ólya恒等式的推广。我们还包括一个组合的证明的alanolya身份。1.青蛙问题和Psycholya恒等式在本文中，我们考虑以下问题（参见。第10.6节[3]）。问题1.一只青蛙生活在直线上。从x = x0开始，他以概率p向左跳n步（从x到x− `），或者他以概率q = 1− p向右跳r步（从x到x+ r），在每个时间= 1，2，. . ..我们在原点设陷阱抓住他的概率有多大？更正式地，我们考虑随机变量X1，X2，. . .其中对于所有i ≥ 1，Prob（Xi =−`）= p和Prob（Xi = r）= q。设fk为青蛙在第k次跳跃后落在原点上的概率，即，fk = Prob（∑i=1Xi =−x0且∑i=1Xi 6=−x0，对于所有` < k）。什么是∑i=1 fk？这个概率的定义对所有的起始位置x0 ∈ Z都是有效的，但是我们例外地将x0 = 0（从原点开始的情况）的概率定义为1，只是出于技术原因。另一种表述问题的方式如下。问题2.一只青蛙住在Z2。从原点开始，他以概率p向上跳一个单位，或者每次以概率q = 1− p向右跳一个单位。那么，青蛙落在直线− `y+x0 = 0上的概率是多少？一步一步向左跳（分别为。r步向右跳）对应于向上跳一个单位（相应地，一个单位跳到右边）在问题2中。问题2是在极值集理论中处理多重相交族时自然出现的，这也是本文的动机之一。事实上，问题的答案（及其变化）在[1]和[8]中起着重要的作用。这个问题也与枚举组合学中出现的一些有趣的恒等式有关。其中，我们给出了∑k≥0（ck+ sdk +t）的一个封闭公式，它是Escholya恒等式的推广.作者得到了文部科学省科学研究补助金（B）16340027的资助。
A frog jumps along the lattice points on the x-axis. Starting from x = x0, he jumps` steps to the left with probabilityp, or he jumpsr steps to the right with probability1− p at each time. What is the probability that he ever lands on the origin? We answer this question by using a closed formula for ∑k≥0 (ck+s dk+t ) zk, which is an extension of the P ólya identity. We also include a combinatorial proof of the Ṕ olya identity. 1. A FROG PROBLEM AND THEPÓLYA IDENTITY In this paper we consider the following problem (cf. section 10.6 of [3]). Problem 1. A frog lives on the lineZ. Starting fromx= x0, he jumps̀ steps to the left (from x to x− `) with probability p, or he jumpsr steps to the right (fromx to x+ r) with probabilityq = 1− p at each timet = 1,2, . . .. What is the probability that we can catch him by setting a trap at the origin? More formally we consider random variables X1,X2, . . . with Prob(Xi =−`) = p andProb(Xi = r) = q for all i ≥ 1. Let fk be the probability that the frog lands on the origin afterk jumps for the first time, i.e., fk = Prob(∑i=1Xi =−x0 and∑i=1Xi 6=−x0 for all ` < k). Then what is∑i=1 fk? This definition of the probability is valid for all starting positionx0 ∈ Z, but we exceptionally define the probability for the case x0 = 0 (the case starting from the origin) to be 1 just for a technical reason. Another way to state the problem is as follows. Problem 2. A frog lives inZ2. Starting from the origin, he jumps one unit up with probability p, or he jumps one unit right with probability q = 1− p at each time. Then what is the probability that the frog ever lands on the line rx− `y+x0 = 0? An l steps jump to the left (resp. r steps jump to the right) in Problem 1 is corresponding to one unit jump upwards (resp. one unit jump to the right) in Problem 2. Problem 2 is naturally arisen when one deals with multiply intersecting families in extremal set theory, which was one of the motivations of this paper. In fact, the answer to the problem (and its variations) plays an important role in [1] and [8]. Also the problem is related to some interesting identities appeared in enumerative combinatorics. Among others, we give a closed formula for ∑k≥0 (ck+s dk+t ) , which is an extension of the Ṕ olya identity. The author was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027.
- 4-wise 2-相交和 4-wise 2-union 族的最大尺寸
DOI：
--
发表时间：
2006
期刊：
European Journal of Combinatorics 27
影响因子：
--
作者：
P. Frankl;N. Tokushige;N. Tokushige
通讯作者：
N. Tokushige
DOI：
--
发表时间：
2005
期刊：
Journal of Combinatorial Theory (A) 109
影响因子：
--
作者：
P. Frankl;N. Tokushige
通讯作者：
N. Tokushige