论文标题
完整根树的属性与随机生成字符串长度分布的属性之间的关系
Relations between the properties of a complete rooted tree and the properties of a distribution of lengths of randomly generated strings
论文作者
论文摘要
让我们表示一个完整的$ m $ yar-ary rooted树的高度$ n $ as $ g $。 In scope of this paper we prove the certain relations between the properties of $G$ and the expectation and variance of the distribution of lengths of strings, generated as follows: starting from an empty string we pick a random symbol from the alphabet $\{ α_1, α_2, \dots α_m \}$ and append it to the string, the process continues until we see $n$ instances of a specific symbol in a row. 考虑一个随机变量$ξ_{m，n} $，该$表示根据所述过程生成的字符串的长度。期望$ \ mathbb {e} [ξ_{m，n}] $和方差$ \ mathrm {var} [ξ_{m，n}] $依赖于$ m $（字母的大小）和$ n $（定义了弦乐生成过程停止标准的参数）。另外，让我们用$ g $的所有2个节点上的公共路径长度的总和为$ s_ {m，n} $，然后表示$ g $中的边缘总数为$ t_ {m，n} $。在本文的范围内，我们证明了所有$ m，n \ geq 1 $：$ \ mathbb {e} [ξ_{m，n}] = t_ {m，n} $和$ \ mathrm {var} [蒜 众所周知，众所周知，从整数序列（OEIS）的在线百科全书中，序列A000918描述了$ \ mathbb {e} [ξ_{2，n}] $和$ t_ {2，n} $，均在$ s_ {2，n} $中描述了$ s_ {2，n} $ oeis sequeence a 2，wey osies A 2，weys sequeence a 2， A286778：此序列描述了$ \ mathrm {var} [ξ_{2，n}] $ - 折腾数量的差异，直到我们连续看到$ n $ heads。
Let's denote a complete $m$-ary rooted tree graph of height $n$ as $G$. In scope of this paper we prove the certain relations between the properties of $G$ and the expectation and variance of the distribution of lengths of strings, generated as follows: starting from an empty string we pick a random symbol from the alphabet $\{ α_1, α_2, \dots α_m \}$ and append it to the string, the process continues until we see $n$ instances of a specific symbol in a row. Consider a random variable $ξ_{m,n}$ that represents a length of a string generated according to the described process. The expectation $\mathbb{E}[ξ_{m,n}]$ and variance $\mathrm{Var}[ξ_{m,n}]$ depend on $m$ (the size of the alphabet) and $n$ (a parameter that defines a stopping criteria of the string generation process). Also, let's denote the sum of the common path length over all 2-tuples of nodes of $G$ as $S_{m,n}$, and let's denote the total number of edges in $G$ as $T_{m,n}$. In scope of this paper we prove that the following relations are true for all $m,n \geq 1$: $\mathbb{E}[ξ_{m,n}] = T_{m,n}$ and $\mathrm{Var}[ξ_{m,n}] = (m-1) \cdot S_{m,n}$. While it is known that both $\mathbb{E}[ξ_{2,n}]$ and $T_{2,n}$ are described by the sequence A000918 from the On-Line Encyclopedia of Integer Sequences (OEIS), and it is known that $S_{2,n}$ is described by the OEIS sequence A286778, we demonstrate a new interpretation for A286778: this sequence describes $\mathrm{Var}[ξ_{2,n}]$ - a variance of the number of tosses of a fair coin until we see $n$ heads in a row.
