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)$?



The mean value of the reconstruction complexity of a random sequence
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:


1. $j\_\*$-s such that $X\_{i\_\*}$ and $X\_{j\_\*}$ are independent,
2. $O(l^2n^2)$ $j\_\*$-s such that $E[X\_{i\_\*}X\_{j\_\*}]\leq |A|^{-3l}$, and
3. $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).
$$


