（基础数学专业论文）关于截尾几何分布的随机变量的组合数的研究.pdf

东北大学硕士学位论文摘要 关于截尾几何分布的随机变量的组合数的研究 摘要 计算机科学的日益发展，不断要求着数据结构和算法的优化与创新， s k t pl i s t s 作为一种新的数据结构，在1 9 8 9 年被p u g h 提出以后，以其简单而迅 速的运行特点，受到了普遍的欢迎。而s k i pl i s t s 的搜索花费等问题又与随机变 量序列的左至右最大值、最小值以及右至左最大值、最小值的组合数问题存在 着密切的关系。十多年来，h e l m u t p r o d i n g e r 、w i l f 等人先后致力于这方面的研 究，并取得了很多成果。本文根据p u g h 关于s k i pl i s t s 的原始思想，修正了 p r o d i n g e r 关于s k i pl i s t s 的概率模型，并在修正后的戤咖l i s t s 的概率模型中研 究了服从截尾几何分布的随机变量的一类组合问题：强、弱状态下左至右最大 值、最小值个数的均值与方差。另外，本文还研究了奇数型s t i r l i n g 数，得到了 奇数型s t i r l i n g 数的几个性质，并相应地得到组合数欧拉数的一个性质。 关键词：截尾几何分布左至右最大值、最小值均值方差发生函数 奇数型s t i r l i n g 数 一i i 东北大学硕士学位论文a b s t r a c t t h er e s e a r c ha b o u tt h ec o m b i n a t o r i c so fr a n d o mv a u f i a b l e s s u b m i t t i n g t ot r u n c a t eg e o m e t r i cd i s t r i b u t i o n a b s t r a c t t h ef u r t h e rd e v e l o p m e n to ft h e c o m p u t e rs c i e n c ec o n t i n u o u s l yr e q u i r e s t h e o p t i m i z a t i o na n dt h em o d i f i c a t i o no f t h ea l g o r i t h m sa n dt h ed a t as t r u c t u r e s 。a sa n e wk i n do fd a t as t r u c t u r e s ，s c i pl i s t sw i nt h ep o p u l a rw e l c o m ef o ri t sq u i c k n e s s a n ds i m p l e n e s si no p e r a t i o n 。f u r t h e r m o r e ，t h eq u e s t i o no ft h es e a r c hc o s t so f s k i pl i s t s h a sc l o s er e l a t i o n s h i pw i t ht h eq u e s t i o no ft h ec o m b i n a t o r i c so ft h e l e f t - t o r i g h tm a x i m a 、t h el e f t - t o r i g h tm i n i m a o ft h er a n d o mv a r i a b l e st h a ts u b m i t s t ot r u n c a t eg e o m e t r i cd i s t r i b u t i o n 。i nr e c e n tt e ny e a r s ，h e l m u tp r o d i n g e ra n dw i l f h a v ed e d i c a t e dt ot h er e s e a r c hi nt h i sf i e l da n dg o tm a n yr e s u l t s 。a c c o r d i n g t op u g h si d e a so nt h e s h pl i s t s ，t h i s a r t i c l em o d i f i e s s l a pl i s t s s o r i g i n a l p r o b a b i l i s t i c m o d e la n ds t u d i e st h ec o m b i n a t o r i c so ft h er a n d o mv a r i a b l e st h a t s u b m i t st ot r u n c a t e g e o m e t r i c d i s t r i b u t i o nu n d e rt h em o d i f i e d s l a p l i s t s s p r o b a b i l i s t i c m o d e l ：t h e e x p e c t a t i o n a n dt h ev a r i a n c eo ft h en u m b e r so f l e f t t o r i g h tm a x i m a 、l e f t t o r i g h t m i n i m a r e s p e c t i v e l yi ns t r o n ga n d w e a ks e n s e s 。 a d d i t i o n a l l y ，t h i sa r t i c l es t u d i e s t h e o d d t y p es t i r l i n gn u m b e r s ，o b t a i n i n gs e v e r a l q u a l i t i e so ft h eo d d t y p es t i r l i n gn u m b e r sa n da c c o r d i n g l yo b t a i n i n go n eq u a l i t y o fe 1 l l e rn u m b e r 。 k e y w o r d s ；t r u n c a t eg e o m e t r i c d i s t r i b u t i o n l e f t t o r i g h t m a x i m a 、m i n i m a e x p e c t a t i o n v a r i a n c e g e n e r a t i n g f u n c t i o n o d d t y p es t i r l i n g n u m b e r i i i 声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的研究 成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的研究成果， 也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究 所作的任何贡献均己在论文中作了明确的说明并表示谢意。 本人签名 日期 驯娜 跏僻f 月 东北大学硕士学位论文第一章绪论 第一章绪论 l - 1 s k i p l i s t s 与其他几种数据结构 近几十年来，计算机科学日益蓬勃发展，计算机的信息加工已经从简单的 数值计算发展到大量地解决非数值问题。而计算机所能够带给人类的一切都是 通过程序来实现的，n i k l a u s w i r t h 曾说过：程序= 算法+ 数据结构，这至少说明 计算机完成任务离不开算法和数据结构，并且数据结构直接影响着算法的选择 和效率。到目前为止，数据结构已有多种类型，如表、树、图等。 二叉树是我们常能碰到的一种树结构。它是结点的有穷集合，它或者是空 集，或者是由一个根和两株互不相交的左子树和右子树组成。它的特点是每个 结点至多只能有两个分支。在以随机的顺序插入元素的时候，二叉树会处理得 很好，但是大量的序列操作，如按顺序插入元素，却使二叉树退化，进而导致 数据结构运行糟糕；其次一些插入或删除会导致树的极度不平衡( 某一枝过 长) ，这样就会延长在树中的搜索时间，若在每次插入、删除之后平衡一下树， 就会避免这类问题，为此人们又引进了平衡树。平衡树是指可以在任一层至多 有一个结点不对称的树。对于一个二叉树来说，如果它的每个结点的左子树和 右子树的高度差不大于1 ，就称为平衡二叉树。平衡树在程序实施操作来维持 一定的平衡环境时将树进行了重新编排，确保了良好运行。还有一种经常被运 用的数据结构是自我调节树，它是指因一次访问会改变c o n f i g u r a t i o n 的 树，像s p l a y 树等。1 9 8 9 年，p u g h 提出一种新的数据结构- s k i pl i s t s 1 ，这种 数据结构本质上是带有附加指针的已分类的链接列表，并且这些指针跨越了中 间的结点，因此p u g h 将其命名为s k i pl i s t s ，它通过访问随机数产生器来使自 己达到平衡。 平衡树算法一般采用递归地插入和删除程序来描述，而这在某种程度上却 降低了程序处理访问的速度，这时如果在平衡树中采用非递归式的插入和删 除，此刻的算法又是惊人的，以致于使大多数人宁愿不取消递归程序。虽然平 衡树也能够处理s k i pl i s t s 所能做的一切操作，但是运行平衡树的难度大大限制 了它们的应用。自我调节树算法在进行单个操作时要占用比给定的期望时间更 长的时间，而且它们在执行操作时不断地重新编排，这给自我调节树的任何操 作带来了相当大的c o n s t a n t f a c t o r ，从而降低了算法的实际应用能力。相比较而 1 东北大学硕士学位论文第一章绪论 言，s k i pl i s t s 是很简单的数据结构，它的算法是非递归的、简单的，容易运行、 操作和修改，它们使程序员对算法的优化变得方便多了。s k i pl i s l v 的平衡特性 与平衡树通过随机插入而建立的平衡特性很相似，但是s k i pl i s t s 却不要求插入 是随机的。尽管s k i pl i s t s 也有糟糕的最坏情况下的操作，但是输入序列不会持 续产生这种情况，而且它们也很少会极度不平衡。s k i pl i s t s 和高度优化的平衡 树算法一样快，比随意地运行的平衡树算法要快得多。s h pl i s t s 能用来取代平 衡树进行的大部分工作，它们是比树更自然的表示，它们产生了更简单的算法， 这种算法的简单性使s k i pl i s t s 更容易运行及提供对平衡树算法和自我调节树 算法的c o n s t a n tf a c t o r 的改进。 1 2 s i pl i s t s 对元素的存放方式 存放在船咖l i s t s 中的每个元素都由一个结点代表，并且用一个键来唯一地 识别各个结点。每个s k i pl i s t s 都有一个元素n i l ，它被赋予大于任何的结点键 的键。s k i pl i s t s 中的元素是以递增的顺序先被存放在处于第一层的链接列表 中，然后通过访问随机数产生器，每个处于层数i ，( i = l ，2 ，) 的元素都 独立的以概率印( 0 q 1 ) 被包括在处于第i + 1 层的链接列表中因此当存放 完毕时，每个元素都属于一定的链接列表，这些链接列表的数量也称为此元素 的层数。所有元素的层数并未存放在各个结点中，而是被覆盖在适当的常量 m a x l e v e l 中。( 根据多方面的分析，人们一般令m a x l e v e l = l o g 。，n 为这个 s k i pl i s t s 的元素的个数的上界) 。层数为k 的元素有k 个从l 到k 的向前的指针， 其中第i ( 1 i k ) 个向前的指针指向下一个层数为f 或更大的元素。同时 s k i pl i s t s 的所有层数都终止于n i l 。另外，每个s k i pl i s t s 都有一个表头，它含 有从第一层到第m a x l e v e l 层的m a x l e v e l 个指针，并且它们指向每个链接列表 的第一个元素，至于高于s k i pl i s t s 的最大层数的那些层的指针则直接指向 n i l 。这里也为每一个s k i pl i s t s 定义了一个高度即所有元素的层数中最大的那 个层数，高度被存放在s k i pl i s t s 的表头中。f i g u r e l 1 是一个存放了六个元素的 s k i pl i s t s 。 一2 东北大学硕士学位论文第一章绪论 f 0 - |n i l _斗斗| 0 -斗-+t -0 - 一b 斗 -斗q -斗0 -0 -一4 +斗 h e a d e rl l h2 1 h3 1 h4 t h5 1 16 m 图1 1 带有指针的s k i p l i s t s f i g 1 1as k i pl i s t sw i t h p o i n t e r s 这个s k i pl i s t s 的高度是6 ，被存放的元素是2 ， 8 ，1 2 ，1 6 ，2 0 ，2 6 。 它们的层数分别为4 ，3 ，4 ，2 ，6 ，4 。 1 3 s k i pl i s t s 的搜索方法 在指定要搜索的对象后，s 1 pl i s t s 按如下方式搜索：每一个搜索都从表 头的最高层开始，如果指针指向的下一个元素的值比要搜索的值小，那么指针 就由下一个元素继续向前判断，否则，指针就由当前位置下降一个层数，然后 重复刚才的判断过程，直至找到要找的元素( 此元素存在于船f pl i s t s 中) 为止。 很显然，任何搜索过程都终止于第一个层数。下面是航枷l i s t s 的搜索算法： s e a r c h ( 1 i s t ，s e a r c h k e y ) x ：= l i s t h e a d e r l o o pi n v a r i a m ：x k e y s e a r c h k e y f o ri ：= l i s t l e v e ld o w n t o1d o w h i l e x f o r w a r d i 卜，k e y s e a r c h k e y d o x ：= x f o r w a r d 【i 】 3 东北大学硕士学位论文第一章绪论 x k e y 旬，那么考。就称为这个 一d 一 东北大学硕士学位论文第一章绪论 随机变量序列的强状态下左至右最大值。 定义2 ：弱状态下左至右最大值：在一n 元随机变量序列( 卣，岛，己) 中， 若善，满足下列条件：对所有的j = 1 , 2 ，i 一1 ，都有点亭，那么亭，就称为这个 随机变量序列的弱状态下左至右最大值。 定义3 ：强状态下左至右最小值：在一h 元随机变量序列( 卣，最，) 中， 若参满足下列条件：对所有的j = 1 , 2 ，f 1 ，都有 乒，那么鲁就称为这个 随机变量序列的强状态下左至右最小值。 定义4 ：弱状态下左至右最小值：在一n 元随机变量序列( 与，邑，) 中， 若亭。满足下列条件：对所有的，= 1 , 2 ，i 一1 ，都有鼻蔓孝，那么f ，就称为这个 随机变量序列的弱状态下左至右最小值。 一个矾加l i s t s ，在它对某一元素进行搜索时，它必须经历一定的路径，也 就是说它为了找到这个元素，必须付出一定的花费，我们称这个花费为搜索花 费。由1 3 知，搜索的过程就是进行元素比较的过程，那么个黜功l i s t s 为搜 索所有元素而进行的k e y t o k e y 比较的总次数，就称为总的搜索花费。当 s k i pl i s t s 中存放的元素比较少时，k e y t o k e y 比较的数量一目了然，但是如 果存放的元素比较多，k e y t o 一妇y 比较的数量就不易观察，为此，人们就寻 求了一个简单的求解k e y t o k e y 比较的数量的方法，以f i 9 1 1 为例，作如下 处理：以各自的层数代替每个元素，那么这个，咖l i s t s 就被表示成层数序列 ( 4 ，3 ，4 ，2 ，6 ，4 ) ，相应地，2 就成为这个层数序列中的被搜索的对象。 如果以2 为分界点，将序列分成两个子序列( 4 ，3 ，4 ) 和( 2 ，6 ，4 ) ，则 前一个子序列在弱状态下的右至左最大值对应着f i g1 2 中 的0 - 一一+ ，后一个子序列在强状态下的左至右最大值对应着f i g 1 2 中的_ _ ，这样一来，对搜索花费的研究就变得十分方便。对 其加以推广便会得出如下结果：对于一个存有厅个元素的s k i pl i s t s 来说，如果 以a ，记第i 个元素的层数，那么这个繇徊l i s t s 就被表示成层数序列 ( 珥，a 。，口。) 。当第z 个元素是被搜索的对象时，对应地层数序列中的a ，就是 被搜索的对象，并且搜索过程中的每一个第1 类k e y t o k e y 比较都与序列 ( a ，a ：，a 。) 在弱状态下的一个右至左最大值一一对应着，每一个第2 类 k e y t o k e y 比较都与序列( a ，a + i ，a 。) 在强状态下的一个左至右最大值 一一对应着。至此，对舭枷l i s t s 的搜索花费的研究就转变为对一个随机层数 序列的左至右最大值、最小值或右至左最大值、最小值的研究。 东北大学硕士学位论文第一章绪论 1 5 左至右最大值、最小值的实际背景及研究意义 对个n 元随机变量序列的左至右最大值、最小值问题的研究最早始于 r e n y i ，其主要结果可查于 6 】。不过，当时他的研究对象是一个n 元置换，实 质上就是一个无重复元素的序列。后来由于计算机科学的发展，二十世纪九十 年代，h e l m u tp r o d i n g e r 应实际操作需要，将研究范围进一步放宽到可重复数字 串。他致力于对左至右最大值个数的均值与方差的研究，并获得了有关均值与 方差的渐近表达式 5 。w i l f 则证明了随机变量序列中第，( 一个固定值) 个左 至右最大值的平均值与平均位置的渐近表达式 8 】。九十年代末，a r n o l d k n o p f m a c h e r 和h e l m u t p r o d i n g e r 又得到随机变量序列中第，( 一个固定值) 个 左至右最大值的值与位置的渐近表达式 9 。反过来，这些研究结果极大地推动 了s k i pl i s t s 算法的优化。有关舭枷l i s t s 的详细的算法可以在 1 7 1 查到，一些算 法分析可以在 4 【1 8 1 9 中查到。 1 6 s t i r l i n g 数的研究背景和意义 s t i f l i n g 数是组合数学中的一类重要的数，它表示将n 个不同元素分配到k 个等价类中，并使每个等价类为非空的方案数。s t i r l i n g 数在统计计算、渐近分 析、有限差分学等方面有广泛的应用，已被作为大量的研究对象，并得到定 的推广 1 5 】。将n 个不同元素分配到k 个等价类中，使每个等价类中元素个数 是奇数的方案数显然是s t i r l i n g 数的一个特殊情况，作为一类特殊的数，它被称 为奇数型s t i r l i n g 数，记作s 。( 片，k ) ，它与另两类组合数：欧拉数、贝努利数有 着密切的关系。虽然奇数型s t i r l i n g 数在 1 0 中曾被简短提到过，在 1 1 中也曾 作为一个特殊的结果出现过，但是到目前为止，我们在文献中还没有发现它 们被专门地讨论过。 1 7 本文的主要工作 本文首先修正了s k i pl i s t s 原来的概率研究模型，指出与s k i pl i s t s 相对应的 随机变量序列中的随机变量的分布类型是截尾几何分布。然后本文在修正后的 概率模型中分别对强、弱两种状态下左至右最大值、左至右最小值个数的均值 与方差进行了详细的讨论。而右至左最大值、最小值个数的均值与方差，也可 以运用类似的方法对其进行研究。另外，本文在论文的后一部分讨论了奇数型 s t i f l i n g 数，利用发生函数的思想得出奇数型s t i f l i n g 数的显式表达式、递推关 一6 一 东北大学硕士学位论文 第一章绪论 系式，证明了它同另两类组合数一欧拉数与贝努利数的关系表达式，以及利用费 马定理得到奇数型s t i r l i n g 数的同余关系式，并利用奇数型s t i r l i n g 数的同余性 质，得到e u l e r 数的一个性质。 7 一 东北大学硕士学位论文第二章一些有关左至碹垦垄垡：垦：! ：垡生鱼查竺墨 第二章一些有关左至右最大值、最小值的 已有结果 随机变量序列的左至右最大值、最小值问题一直吸引着许多学者，如a r n o l d k n o p f m a c h e r 、h e l m u tp r o d i n g e r 、w i l f 、p e t e rk i r s c h e n h o f e r ，并且他们在这一 方面己经取得了巨大的研究成果：获得了左至右最大值、最小值个数的平均值 与平均方差的渐近表达式，第r 个左至右最大值的平均值与平均位置的渐近表 达式等。下面简要地介绍一下h e l m u tp r o d i n g e r 在这方面的部分研究成果。 ( 卣，彘，) 是一个由一元随机变量组成的序列，；g e e 鼻n 是相互独立 且同服从于几何分布的随机变量，如果p ( 六= ) = p q “1( p = 1 一q ) ，那么h e l n m t p r o d i n g e r 得出： 引理2 1月个相互独立且服从于几何分布的随机变量产生的序列中，强状 态t a l 5 1 a s c i i 大值的平均个数是： e 。= p 艺 1 - ( 1 - q ) ”j ( 2 1 ) 利用s p a n k o w s k i 与r e g o 得到的一个结果： 宝i 一( 1 - q f = l o g on + 量+ i 1 坝l o g o n)+00k= 0 - 。 o ：g 一，上：1 。g q ，y 是欧拉常数，占( x ) ：r ( 一弦：一，坼= 至芋， 得到表达式( 2 1 ) 的渐近形式： 驴p 1 0 9 0 n + 兰+ 吉叫l o g o n ，i + 。专 引理2 2 个相互独立且服从于几何分布的随机变量产生的序列中，弱状 态下左至右最大值的平均个数是： e ：导妻l - ( 1 一日。) ”1 ( 2 2 ) 同样地( 2 2 ) 的渐近形式表示为： 8 一 东北大学硕士学位论文第二章一些有关左至右最大值、最小值的已有结果 驴旦l l o g o n+ql 至l；一占( 1 0 9 0n ， + 。c 吉， 引理2 3n 个相互独立且服从于几何分布的随利l 变量产生的序列中，强状 态下左至右最大值个数的方差是： v o = 2 p 2 。z 叽i 筹+ 筹卜坷。2 汜s ， 其渐近形式为： _ 钢1 0 妒+ p 2 ( + 蔷+ 兰巾2 】0 ) + p 唾+ 争吒( 1 0 9 0n ) + d ( 【占2 】。是占2 ( x ) 的平方均值，以( x ) 是均值为0 的周期函数。 引理2 4n 个相互独立且服从于几何分布的随机变量产生的序列中，弱状 态下左至右最大值个数的方差是： 圪= 丁2 p z 。对+ 龇q - ，- 1 + 糌 + 丁2 p 2 小( 寿妒a 川 + e 。一e 。2 ( 2 4 ) 其渐近形式为： 圪= 乒山g 等c 岳+ 争三们卅詈c 暑m s c l o g on m c + e 。一e 。2 其中文( 。) 是均值为0 的周期函数。 一9 东北大学硕士学位论文 g s _ 章修正s j l i s t s 的概率模型 第三章修正s k i pl i s t s 的概率模型 由第一章的1 2 节知，中的层数是通过访问随机数产生器而产生的，因此 存放了元素的的层数序列中的每个元素都是一个随机变量，且它们是相互独立 并服从同一分布的。至于它们的分布类型，有关的文献都指出是几何分布，所 有有关方面的研究也都是以此为基础来进行的。但是p u 曲在1 9 8 9 年提出 s k i pl i s t s 时指出：每个层数都是由下面的算法产生的： r a n d o m l e v e l ( ) n e w l e v e l ：= 1 r a n d o m ( ) r e t u r n sar a n d o mv a l u e i n 0 1 w h i l er a n d o m ( ) pd o n e w l e v e l ：= n e w l e v e l + l r e t u r nm i n ( n e w l e v e l ，m a x l e v e l ) 虽然m a x l e v e l 不是一个统一的标准常量，但是在工作任务明确后，实际操 作中的m a x l e v e l 的值一般都是取定的，根据有关方面的研究分析，都取定为 m a x l e v e l = l o g n ，其中真数n 是这一s k i pl i s t s 的元素个数的上界，而底数中 的p 值是由这个s k i pl i s t s 的随机数产生器决定的。所以上面的有关层数的算法 表明任何一个层数都不能超出m a x l e v e l ，因此，s k i pl i s t s 的层数序列中的随机 变量准确地讲是服从截尾几何分布的，而不是服从几何分布的。 因此我们将s k i pl i s t s 的概率模型修正为： 每个存有以个元素的s k i pl i s t s 都相应地对应着一个珂元随机层数序列 ( 卣，善：，己) ，其中f ，n 是相互独立的且服从截尾几何分布的随机变量， 即 p ( 氧= 后) = p q “1 k m a x l e v e l ( p = 1 q ) p ( 茧= k ) = q “1 k = m a x l e v e l 本章以下的一切有关s k i pl i s t s 的左至右最大值、最小值问题的工作都是 在修正后的概率模型中进行的，并且在以下的讨论中，由于肌印l i s t s 所赋予的 一1 0 一 东北大学硕士学位论文第三章修正烈初l i s t s 的概率模型 被存放的元素的层数实质上是一个变量，因此我们都统一地称随机层数序列为 随机变量序列。 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 第四章服从截尾几何分布的随机变量的 组合数：左至右最大值、最小值 4 1修正的概率模型下左至右最大值个数的均值与方差 4 1 1强状态下左至右最大值个数的均值与方差 4 1 1 1 强状态下左至右最大值个数的均值s e n ( 叩) t 对任意的一个随机变量序列( f 。，亭：，亭，) ，我们采取类似于 9 的思想，将其分解成如下的分解形式： ( 点，善2 ，厶，) = ( a 1u 彳2u 坞u u 勘) ，其中a ：= 七讧2 ，k j 。f 面 对这一分解形式给以解释：4 中的k 是随机变量序列的一个左至右最大值a 。表 k 的后面可以是小于或等于k 的任何正摧数，至于个数却没有限制。这时，我 们把随机变量序列中的每一个随机变量赋予一个追踪记号z ，而每一个左至右 最大值赋予一个追踪记号y ，然后我们便可以建立如下的一个映射： 斗j 堡j | ：1 厶，m 一，i 一 o l 。w 一 1 一( 1 一q k ) z q m - t y z 1 一z 那么相应地我们会得到如下的对应： 陀“o 卜一z ：件f 1 + j 缉 f 1 + q m - l y z l ( 4 1 1 1 1 ) ( “：一知) 一州马力2 玎【1 + 蔫代+ 百j 1 。1 1 t = 】 1 l 1q ，4 1。 由概率论的知识知，f ( z ，y ) 的展开式中z y 项的系数就是一个以元随机变 量序列含有m 个强状态下左至右最大值的概率，z ”项的系数就是一个n 元随机 变量序列含有强状态下左至右最大值个数的概率发生函数，它是y 的函数，记 为o ( y ) 。 这时记r 。= 毒是左至右最大值 ，叩= 矾 ( 其中 】表示当括号内所 叙述为真时，取值i ；为假时，取值0 ) ，那么随机变量叩就表示一个n 元随机 一1 2 东北大学硕士学位论文第四章 服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 变量序列中强状态下左至右最大值的数量，因此其期望值 趿= 掣k 。七” 掣k t 下面来求它的具体表达式： 首先，对( 4 1 1 1 1 ) 式两边同时取对数，并对y 求一阶导数得出 l 1t z ，j o y 吡y ，陷 矗热嚣杀 + 三纛鲁 吡疹瞎而蒜+ 名蔫 又因为 i n f ( z ：y l n ! 二! ! 二丝! 二堡二! 竺! , 1 ) m - 1 + i n 。否kh 篇半= 11 一l 1 一q ， 1 即 所以有 所以 f ( z ，1 ) o f ( z ，y ) i 面一。问 邛”，击陲 p q zq m - 1 z 1 一( 1 一q k ) z 。1 一( 1 一q m - i ) z = 私壤嚣杀心，毒斋 = i m 2 t kc 1 - q k r - i m - | c 1 - q m - 1 p q qm-1r=lk = or 1 = ()十g() 卜11 j p 篁l _ ( 1 _ q k)”+1-(imqm-iq k ) 1 p u 一( 1 ) ”j + b 一( 1) ”j k = o 一1 3 一 上h警糯 斋纛 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 至此我们得到如f 结论： 定理4 1 1 1 1由h 个相互独立且同分布于截尾几何分布的随机变量产生 的随机变量序列中，强状态下左至右最大值个数的平均值s e ( r 1 ) 是： s e 。( 野) = p l 一( 1 一g ) “j + 1 一( 1 - q ”。) ” 这时若令g o ，则瓯( 叩) 斗p + p 笠l 一( 1 - q k ) n 】+ l 一( 1 一g ”一1 ) “= 1 ， 即趿( 可) 斗1 ，若令q 一1 ，则s e ( 叩) 斗1 。事实上，当q 斗0 时，有p 斗1 ， 因此序列的输出结果趋向( 1 ，1 。，1 ) ，这个序列只有一个强状态下左至右最 大值：1 ，即s e 。( 叩) = 1 ：当q 斗1 时，随机变量序列的输t t i 结果趋向于 r mm ，m ) ，这个序列也只有一个强状态下左至右最大值：m ，即 s e ( 叩) = 1 ； 特别地，当m 一。时，这里的s e 。( 叩) 的极限值就与【5 】的结论一( 2 1 ) 式一致。 4 1 1 2 强状态下左至右最大值个数的方差s k ( 柙) t 由概率论知识，我们知道： s 圪( 呷) ：旦：；掣i 州+ e ( 叩) 一 瓦( 7 7 ) 2 o r 。 。 现在我们来讨论一t o z 加g ( 2 y ) i ，。的值： 由上一节知， 掣毗小瞎可惫+ 名鞔 所以 a 2 f ( z ，y ) 矿 ：翌掣| 窆 砂i 钉而1 蒜q kp qy z + 1l q u - 1 y z 一( 1 一) z + - 1 。 一z + j i 薹巫盘：盎l o y 一1 4 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 因此 ：墨掣l 艺 砂i 石 丝：2 1 一( 1 一q k 弦+ p q “ q m - t 2 z + q u q y z 堋训，偿一 下豢而 2 _ g 纛 2 丝! ：1 1 一( 1 一q k ) z + p q 4一yz+熹1 q m - t y z z + 州训，臀 而黯而 2 + g 蔫 2 a 2 f ( z ，y ) 却2 剐薯 p q k 一1 z 1 一( 1 一q “) 1f 。五。b 乞 我们令 则 2 p q z 21 一( 1 一q k q m - 1 z ( 1 一q m - t 旦! ：!；、f! 旦! ：1 1 一( 1 一q j ) z 。o ；乏寿一2 1 一( 1 一q k ) z 一( z ) ：，2 p _ l l z 0 sr ( j s m 霸( z ) = i 2 p 1 一z o e 盯一 g z 一2 1 一( 1 一q ) z q k z 2 1 一( 1 一q k k q 。z 1 一( 1 一q 。) z q m - 1 z 1 一( 1 一q m - i 弦 2 - 舞斋n q m - i z 1 一r 1 一q ” 掣i 州：一( z ) + g 。( z ) 却2 2 。1 ”7 。6 1 利用l e i b n i z 公式则有： 舴冲p 。，毛一：b + 再1 - 志+ 赤，志 q ”一1 一。一11 一f 1 一q ” 1 5 一 朝 1 l 1 一( 1 一g ) z j ，。l )y z ( f 蔫 。，l m 一 中i i j + 上h t姑 p 2 i i 自 以所 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 f ，f l ( z ) = 2 p 2 。 等等+ 筹1 l 0 9 ( j s m 一2 lq 1 可 1 【z ”】g ，( z ) = z p 。；三一： + 笔盂詈! ；车1 + ! t t ；磐 0 s i s m 一2 i呵 1 l 所以我们又有下面的式子成立： f 学i 归 = 扛”】一( z ) + z n g l ( z ) 却2 。“+ 筹+ 筹 + 2 p 五 - + 筹+ 等 因此我们有如f 结论成立： 定理4 1 1 2 1由h 个相互独立且同分布于截尾几何分布的随机变量产 生的随机变量序列中，强状态下左至右最大值个数的方差s k ( 口) 是： s k c 护甄c 加瓯2 。”一2 。毛一2 h 等等+ 譬t t 等 0 丑，s m iq 1 j 伽点 挈等+ 筹鹞 这里如果令m 斗o 。，则s k ( 可) 的极限值也正是 5 】的相应结论一( 2 3 ) 式。 4 1 2 弱状态下左至右最大值个数的均值与方差 4 , 1 2 1 弱状态下左至右最大值个数的均值w e 。( ，) ： 这时对于任一给定的随机变量序列( 鲁，厶，己，) ，我们也可以 将其归纳到统一的分解形式，具体形式如下： ( 卣，善2 ，厶，) = ( b l + n b 2 + n n b m + ) ，其中b 女= k 1 ，2 ，k 一1 。 而b 。表示b 。在分解形式中，可以不出现，也可以出现，且出现的次数不限。 我们仍然把随机变量序列中的每一个随机变量赋予一个追踪记号z ， 而每一 个左至右最大值赋予一个追踪记号y ，然后建立如下的一个映射： b ： 一1 6 东北大学硕士学位论支 第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 b m 那么相应地有 ( 石，炙， 1 卜毒1 一( 1 一g ”1 ) z ，知) 一( z ，y ) ：1 。7 ，p 再1f 1 一( 1 一g “1 弦 。7 丐- 卜斋1一( 1 一g m _ 1 ) z 同理，r ( z ，y ) 的展开式中z y “项的系数就是一个l l 元随机变量序列含有 m 个弱状态下左至右最大值的概率，矿项的系数就是一个n 元随机变量序列含 有弱状态下左至右最大值个数的概率发生函数，它是y 的函数，记为g 。( y ) 。 记h = f 。是左至右最大值】，y = e ，那么随机变量，就表示一个”元 随机变量序列的弱状态下左至右最大值的数量，因此其期望值是； w e 。( y ) ：! ! ! ；：j ! ! ! ! i ，： ：” 掣i ，：， 卯泖 下面去求它的具体值： 对( 4 1 2 1 1 ) 式两边同时取对数，再对y 求一阶导数得出： 垦墨! ! ：塑 却 所以 而 r m 一1 = l ( 训) l z 1 p q 。一1 zq m - 1 z 1 一z + q 一1 ( 1 一p y ) z 。1 一z + g “一1 ( 1 一y ) z 吲训，医m - 2 函筹而+ 百篱而 掣k 。划列，匡m - 2 斋+ 鲁1i 。 l 函l l l 盯) z z i 咒( z ，1 ) = e x p 1 n 凡( z ，1 ) 一1 7 一 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最犬值、最小值 所以 所以 e x p l 薯h 嚣糍地掣 e x p - l n ( 1 一z ) 】 1 1 一z o y a - z , y ) i 心 洲 圭瞧孝杀+ 害 掣o y h - 斗”，击誓蒜m ”，爵 邛”，詈善击嚣唯”，尚 = l ”】詈m 善- 1 圭一矗而卜矿一l ：尝窆m g t ) n h 。一 q = l 至此有如下结论成立： 定理4 1 2 1 1由，z 个相互独立且同分布于截尾几何分布的随机变量产生 的随机变量序列中，弱状态下左至右最大值个数的平均值阿。( y ) 是： 呱( 加詈薯。一( 1 _ q k ) 协矿1 这时令g 斗。，则将阮( = 翱詈篙l 一( 1 - q * ) n l 删i m p 蕃”( 1 一g 。) ”= ” 一1 8 卺斋刊 驰 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 这是因为此时随机变量序列的输出结果趋向于( 1 ，l ，1 ) ，。e 只 有h 个弱状态下左至右最3 v 值，即w e 。( y ) = 1 1 。若令q 斗1 则 曾臃。( ，) = 曾”矿一= n ，这是因为此时的随机变量序列的输出结果趋向于 ( 尬m 。，m ) ，这个随机变量序列含有n 个弱状态下左至右最大值，即 w e 。( ，) = n 。 特别地，若令m 斗。，则这里的结果就同 5 懈- - ( 2 2 ) 式一致。 4 1 2 2 弱状态下左至右最大值个数的方差阡( y ) ： 由前面的分析知 嘿= 学k ，+ w e 渺) _ 呱 2 下面去求 z ? 鱼号笋盟i 州的值： 由4 1 1 2 知 掣划训，慝函籍而+ 万舞丽 所以 里：墨! ! ! 塑 o y 2 = 型o y 陵瓦i 等1 五p y ) z + 函1 学赢y ) z j li 盘一z + g ( 一一z + 口( 1 一 力 缸忐 2 + 彘 2 所以 曼：墨竺! 塑l 加2 a 凡( z ，y ) 却 m 。f 暂岽舞 2 + 鲁 2 一1 9 一 鲁焘 偿 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最1 、值 = 击鹰蒜 1 n z ) q 2 匡羔+ 甜+ 南偿 羔钏 a 2 e ( z ，y ) 。 五f 一4 = 等，告。毛一，瓜巧嚣可砑+ 等。鲁，磊一，南 + 乒烈三一两醋碉+ 高j 脾，= 等。各。毛一，而尚 以加等，芒五商斋 “加手- 各怪一巧丽p q k * m + 而q 2 m 觯，= 等。副击+ 击。而杀+ 击，而杀 所以 2 p 2 q 2 1 i q 7 l 1 一( 1 一q ) 2 以z ，= 磊一。e1 j 一可q k 而斋+ 寄矗杀j 1 2 ( z ) = i 南一鲁i + 纛q 卜攀q ，南( 1 -l ( 1 一= ) 2 一z 1 一( 1 一。) z j 2 z ) 3 2 0 升 卺h彘 雀 上h r r 鲁 上h 旦州 一 吖一 丝矿 2 一 东北大学硕士学位论文第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值 整理得 f 】竽k - = z ”】 ( z ) + z ”】9 2 ( z ) + z ” ，2z ) 等。甜+ 辫+ 锷愕剐，一等 守2 p2 点 t + 掣笋一 ，+ 专p 川 + 丁2 p q m q 点”七) + 学 2 q “n ( n 一1 1 + q j 一_ 2 f 等 了2 p 2 羞 1 + 锷+ 错愕2 p 2 五 1 + ( 寺十州 j - 2 p q ”一3 岳一i 一( 1 _ q k y b t + n ( n 一- ) g ：”一z 1 “ 因此我们有如下结论成立： 定理4 1 2 2 1由珂个相互独立且同分布于截尾几何分布的随机变量产生 的随机变量序列中，弱状态下左至右最大值个数的方差眠( y ) 是： 暇c 炉脱府卜畹船汗+ 等q 。暑一i ，+ 嬖q 譬+