El número esperado es $\Theta(n\, 2^n)$. El OP se observa que este es un límite superior, por lo que debemos mostrar es un límite inferior.
En una frase, la prueba es: $x$ probablemente no se superponen, por lo que sólo puede caber $O(1)$ copias de $x$ en una $2n$-cadena larga, por lo que las apariciones de $x$ como subcadenas debe ser distribuido a través de un montón de $2n$-cadenas largas.
Aquí hay más detalles; voy a ignorar algunos techos y pisos de la simplicidad.
Fijar un $n$-largo de la cadena de $x$; deje $s(x)$ denotar la más pequeña "cantidad de cambio" $s$ tal que $x$ "solapamientos" con sí mismo en un cambio de $s$; es decir, el $(n-s)$-prefijo de $x$ está de acuerdo con el $(n-s)$-sufijo de $x$. (Set $s(x)=n$ si no tal cantidad de cambio que existe.) A continuación, una $2n$-cadena larga sólo puede contener $1+n/s(x)$ copias de $x$.
El número total de $n$largo de las cadenas de $x$ $s(x)\le k$ es en la mayoría de las $2^1+2^2+\cdots+2^{k}<2^{k+1}$. Así que la probabilidad de que $s(x)<n/2$$O(2^{-n/2})$. Por lo tanto, con una probabilidad de al menos $1-O(2^{-n/2})$, el número máximo de ocurrencias de $x$ cualquier $2n$-cadena larga es en la mayoría de las $1+n/(n/2)=3$.
Por último, el número total de pares de $(w,i)$ tal que $w$ $2n$- cadena larga, en la que $x$ se produce como una subcadena en la posición $i$$(n+1)2^n$. El párrafo anterior muestra que estas apariciones de $x$ como subcadenas se extienden a: con una probabilidad de al menos $1-O(2^{-n/2})$, $x$ se produce en al menos
$(n+1)2^n /3$ de las palabras $w$. Por lo tanto la expectativa,$x$, de la cantidad de palabras $w$ contiene $x$, es al menos
$$(1-O(2^{-n/2}))(n+1)2^n /3= \Omega(n\, 2^n)$$
como se requiere.
