The Expected Number of Distinct Substrings in an Alphabet String

Abstract

Consider a sequence of i.i.d.~trials $X=\{X_1,X_2,\dots ,X_n\}$ where $p(X_i=j)=1/d;j=1,2,\dots ,d$, or more generally $p(X_i=j)=p_j;{\sum }_{1\le j\le d}{p}_j=1$. We consider the variable $D$ that counts the number of distinct substrings of all lengths,$1\le k\le n$ in $X$ and prove results concerning $E(D)$.

13 pages