Expected number of overlapping substrings I want to know what the expected number of overlapping substrings there are when sampling with replacement from a large string.  Suppose there is a string of length $N$, and we want to sample $m$ substrings with replacement of length $k$ from it.  What is the expected number of the $m$ substrings that overlap in the length $N$ string?
For example if there is a string of length one billion, and I want to sample with replacement one million substrings of length 100 from it, what is the expected number of overlapping substrings?  Overlapping substrings are determined by their start and end locations in the original one billion length string.
 A: I've added an estimate on the end of this post.

We can select $N-k+1$ substrings of length $k$ from the string of length $N$.
If the substring of length $k$ is not near the edges of the string of length $N$, we will have $2k-1$ possible overlapping strings: from the one that starts $k-1$ characters to the left of the chosen substring, thereby having a superposition with the first character of the chosen string, to the one that starts on the last character (the $k^\textrm{th}$ character) of the chosen substring.
Therefore, the probability $p$ of selecting a substring that overlaps the chosen substring is
$$
p = \frac{2k - 1}{N-k+1}
$$
If the substring is near one of the edges, i.e., if there are $0 \leq j < k - 1$ characters either to the left or to the right of the string of lenght $N$, the probability becomes 
$$
p = \frac{k + j}{N-k+1}
$$
And if the substring of length $k$ if is a large portion of the string of length $N$ and we have on both sides less than $k - 1$ characters, all the other substrings will be superimposed to that one.

When we remove $m$ substrings, the number of removed characters is at most $k m$.
If we assume that $k m$ is much smaller than $N$, then we may use as an approximation of the probability that two strings of length $k$ overlap the formula
$$
p = \frac{2k - 1}{N}
$$

Edit:
So, on average, we expect that each string of lenght $k$ will be overlapped by $(m-1) p$ strings. If we sum the expected number of overlaps over the $m$ strings we have 
$$\frac{m (m-1) p}{2}$$
The division by two is because we do not want to count twice the overlap between string $a$ and string $b$ and the overlap between string $b$ and string $a$.
This estimate is probably below the true value because as we increase the number of strings of length $k$, the unoccupied space in the string of size $N$ gets smaller, thereby increasing the probability of an overlap.
A better estimate of $p$ could be
$$
p = \frac{2k - 1}{N - k m/2}
$$
where we can consider that on average, the string of length $N$ is covered by $m/2$ strings of length $k$, where the average is considered over the process of sampling $m$ strings of length $k$.

I've also run some code in octave (similar to matlab) to see how accurate this last estimate would be for your example.
k = 1e6;
N = 1000*k;
m = 100;
sum_overlaps = 0;

for j=1:10000
  s = 1 + floor(N .* rand(m,1));
  d = abs(s' .- s) < k;
  sum_overlaps = sum_overlaps + (sum(sum(d)) - m)/2;
endfor

% average number of overlaps
sum_overlaps/10000

p = (2 * k - 1)/(N - k * m / 2);
%estimate
m*(m-1)*p/2

The average number of overlaps after 10 000 simulations was $9.8604$ and the estimate was a bit higher $10.421$, but close.
