|
Prikladnaya Diskretnaya Matematika. Supplement, 2024, Issue 17, Pages 9–11 DOI: https://doi.org/10.17223/2226308X/17/2
(Mi pdma632)
|
|
|
|
Theoretical Foundations of Applied Discrete Mathematics
Exact formula for expectation of number of pairs of coinciding $s$-chains in a random binary sequence with fixed number of zeroes and ones
V. I. Kruglov Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
DOI:
https://doi.org/10.17223/2226308X/17/2
Abstract:
We consider all possible binary sequences $X=(X_1,X_2,\ldots,X_{a+b})$ of length $a+b$ consisting of $a$ ones and $b$ zeroes. For each such a sequence, we count the number of pairs of its subsequences of a given length $s$ (so called $s$-chains) that have coinciding values of their elements. Assuming all these sequences $X$ to be equiprobable, we propose exact formula for expectation of number of pairs of coinciding $s$-chains. For any $s$, $s<a$ and $s<b$, and any $i$, $1\leq i\leq a+b-s+1$, consider $s$-chain $Y_i=(X_i,\ldots,X_{i+s-1})$ and event $E_{ij}=\{Y_i=Y_j\}$. Let $\eta_{ij}=\mathbb{I}(E_{ij})$ be the indicator of this event, then the number of pairs of coinciding $s$-chains in the sequence $X$ is equal to the random variable $\xi=\textstyle\sum\limits_{1\leq i<j\leq a+b-s+1}\eta_{ij}$. For any $r_a\leq a$ and $r_b\leq b$ denote by $p_{r_a,r_b}=\text{C}_{a+b-r_a-r_b}^{a-r_a}\big/\text{C}_{a+b}^a$ the probability that in sequence $X$ on fixed $r_a$ positions there are ones and on fixed $r_b$ positions are zeroes. For any $k$ such that $1\leq k\leq s-1$, we define the values $n=\lfloor s/k\rfloor$, $m=s-kn$, and the function $$f(k)=\textstyle\sum\limits_{t_1=0}^m\sum\limits_{t_2=0}^{k-m}\text{C}_m^{t_1}\text{C}_{k-m}^{t_2}p_{t_1(n+2)+t_2(n+1),(m-t_1)(n+2)+(k-m-t_2)(n+1)}.$$ Then for the expectation of $\xi$ we obtain the formula $$\mathsf{E}\xi=\frac{\text{C}_{a+b-2s+2}^2}{\text{C}_{a+b}^a}\textstyle\sum\limits_{r=0}^s \text{C}_s^r\text{C}_{a+b-2s}^{a-2r}+\sum\limits_{i=1}^{a+b-2s+2}\sum\limits_{k=1}^{s-1}f(k)+\sum\limits_{i=a+b-2s+3}^{a+b-s}\sum\limits_{k=1}^{a+b-s+1-i}f(k).$$
Keywords:
repetitions of $s$-chains, expectation, urn scheme, exact formula.
Citation:
V. I. Kruglov, “Exact formula for expectation of number of pairs of coinciding $s$-chains in a random binary sequence with fixed number of zeroes and ones”, Prikl. Diskr. Mat. Suppl., 2024, no. 17, 9–11
Linking options:
https://www.mathnet.ru/eng/pdma632 https://www.mathnet.ru/eng/pdma/y2024/i17/p9
|
|