The mean value of the reconstruction complexity of a random sequence This problem is motivated by the problem of reconstructing a genome from the family of its short subwords.
Given a word $w$ and a positive integer $k$, let $M_k(w)$ be the family of all subwords of length $k$ and $\mu_{k,w}:M_k(w)\to \omega$ be the function assigning to each subword $v\in M_k(w)$ the number of subwords of $w$ that are equal to $v$.
For example, for the word $w=mathover\!flow$ we have
$$M_2(w)=\{ma,at,th,ho,ov,ve,er,rf,fl,lo,ow\}$$ and
$$M_3(w)=\{mat,ath,tho,hov,ove,ver,erf,rfl,flo,low\}$$ and $\mu_{k,w}\equiv 1$ is the constant unit functions on $M_k(w)$ for $k\in\{2,3\}$.
Definition. The reconstruction complexity of a word $w$ is the smallest $k$ such that for any word $u$, the equality $\mu_{k,w}=\mu_{k,u}$ implies $w=u$.
For example, the word $mathover\!flow$ has reconstruction complexity 2.
Problem. What is the mean value of the reconstruction complexity of a random word of length $n$ in a finite alphabet $A$? We assume that each word appears with equal probability $1/|A|^n$.
I am especially interested in case $|A|=4$ (because DNA-sequences are written in such an alphabet).
Computer experiments show that a random word in 4-letter alphabet of length about 1500 (a typical length of a short gene) has reconstruction complexity about 10, and the complexity slightly grows with growth of $n$. For $n=3000$ it is near 12. So, what are lower and upper bounds for the reconstruction complexity of a random word? Maybe it is $O(\ln n)$?
 A: The expectation of the reconstruction complexity of a random word of length $n$ over the alphabet $A$ is $E[k(n)]=(2\pm o(1))\log_{|A|}(n)$.
Upper bound. We show that $E[k(n)]\leq 2\log_{|A|}(n)+2$, for any $n$ large enough. Given a word $w$, let $k'=\min\{l:\mu_{l,w}\equiv 1\}$. Then, $k(n)\leq k'+1$. To see that, take an element of $u\in M_{k'+1}(w)$. There is only one way to extend $u$ forwards and only one way to extend it backwards.
It is sufficient to show that $E[k']\leq (2+\delta)\log_{|A|}(n)$. To see that, note that a word of length $n$ has less that $n^2$ pairs of sub-words of length $l$, and the probability that two sub-words of length $l$ are equal is $|A|^{-l}$. It follows, by the union bound, that $P(k'>l)\leq \min\{1,n^2|A|^{-l}\}$. Summing over all $l\geq 0$, gives
$$
E[k(n)]-1\leq E[k']=\sum_{l=0}^\infty P(k'>l)\leq 2\log_{|A|}(n)+\sum_{i=0}^\infty |A|^{-i}\leq 2\log_{|A|}(n)+1.
$$
Lower bound. We show that $E[k(n)]\geq (1-\delta)(2-\delta)\log_{|A|}(n)$, for any $\delta>0$ and any $n$ large enough. Let $w=(w_1,\ldots,w_n)$ be a random word of length $n$ over the alphabet $A$. For, $l\in[n]$ and $i\in[n-l+1]$, let $w_i^l:=(w_i,\ldots,w_{i+l-1})$, the sub-word of length $l$ starting at $i$. For indices $i,j,i',j'$ such that
$$1\leq i<i+l< j<j+l< i'<i'+l<j'<j'+l\leq n,$$
consider the event $A_{i,j,i',j'}:=\{w_i^l=w_{i'}^l,\ w_{i+l}\neq w_{i'+l},\ w_j^l=w_{j'}^l\}$. Define a random variable
$$X(n,l)=\sum_{i,j,i',j'}\chi_{A_{i,j,i',j'}}.$$
We argue that $P(k(n)>l)\geq P(X(n,l)>0)$. Indeed, if $X(n,l)>0$ then let $A_{i,j,i',j'}$ be an event that occurs, and by swapping the sub-words $w_i^{j-i}$ and $w_{i'}^{j'-i'}$ one obtains two different words with the same $M_l$.
Since $E[k(n)]=\sum_l P(k(n)>l)$, it remains to estimate $P(X(n,l)>0)$ from below. For each such $i_*=(i,j,i',j')$ denote the indicator of the event $A_{i
_*}$ by $X_{i_*}$. We have
$P(X_{i_*}=1)=|A|^{-2l}(1-|A|^{-1})$. For any $l< (2-\delta)\log_{|A|}(n)$, the number of possible $i_*$ is $\Theta(n^4)$; therefore $E(X(n,l))=\Theta(n^4|A|^{-2l})=\omega_\delta(1)$.
For any given $i_*$ we can partition the possible $j_*$-s into three sets:

*

*$j_*$-s such that $X_{i_*}$ and $X_{j_*}$ are independent,

*$O(l^2n^2)$ $j_*$-s such that $E[X_{i_*}X_{j_*}]\leq |A|^{-3l}$, and

*$O(l^4)$ $j_*$-s such that $E[X_{i_*}X_{j_*}]\leq |A|^{-2l}$.

Therefore,
$$
E[(X(n,l))^2]\leq (E[X(n,l)])^2+ O(n^6l^2|A|^{-3l}) + O(n^4l^4|A|^{-2l})= (E[X(n,l)])^2(1+o(1)).
$$
By the second moment method,
$$
P(X(n,l)>0)\geq \frac{(E[X(n,l)])^2}{E[(X(n,l))^2]}\geq \frac 1 {1+o(1)}\geq  1-\delta,
$$
for every $n$ large enough and any $l<(2-\delta)\log_{|A|}(n)$.
It follows that
$$
E[k(n)]= \sum_{l=0}^\infty P(k(n)>l)\geq \sum_{l< (2-\delta)\log_{|A|}(n)}P(X(n,l)>0)\geq (1-\delta)(2-\delta)\log_{|A|}(n).
$$
