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

Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 9-11

Résumé

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$ and $s$, 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$. 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).$$

Détail

Keywords: repetitions of $s$-chains, expectation, urn scheme
Mots-clés : exact formula.