Expected number of substring in random string Consider random string of length $n$ over alphabet of size $|\mathcal{A}|=a$ ($a^n$ strings in total).  What's expected number of distinct substrings of this string? What's expected number of distinct substrings of length $k$?
In other words, find size of the set $$\left\{(s, t)| s \in \mathcal{A}^n, t \in \mathcal{A} ^ k, t\  \text{is substring of}\  s \right\}.$$
Does it possible to calculate this number in polynomial time (i.e. $poly(n,k,a)$)?
I am looking for exact formula or alogirthm to calculate this number, but asymptotics results are also welcome. 
 A: The authors of this paper exactly answer that question (in corollary 2.2 of that paper).
A: It seems like if $\tau$ is a uniformly random word in $\mathcal{A}^n$, then $\tau$ has roughly as many distinct length $k$ substrings as possible (in expectation).  That is, this number is within a constant factor of the upper bound $\min(a^k, n-k+1)$.
Case 1 ($k$ is big): As noted in the comments, if $k \geq (1+ \varepsilon) \log(n)/\log(a)$ , then with high probability no substring of length $k$ appears more than once.  So in fact, when $k$ is this large, it is very likely that $\tau$ has exactly $n-k+1$ distinct substrings (no expectation needed).
Case 2 ($k$ is small):  Suppose that $k < (1 + \varepsilon) \log(n)/\log(a)$.  Then split the length $n$ word into $n/k$ disjoint blocks of length $k$.  Let $B_1, B_2, \ldots , B_{n/k}$ denote the substrings of $\tau$ corresponding to these blocks.  Then these $B_i$ are i.i.d. and each is uniformly drawn from $\mathcal{A}^k$.  Thus, the expected number of distinct values for the $B_i$ is $a^k \left[ 1 - (1-a^{-k})^{n/k} \right] \geq a^k (1 - \exp[-\frac{n}{ka^k}])$, which is at least $a^k \delta$ for some fixed $\delta >0$ depending only on $\varepsilon$.
Does this answer the question to your satisfaction?
