×

# Expected Length of Longest Repeating Substring

This is inspired by one of this week's Data Structures and Algorithms challenges. Suppose you had a string S of length L whose letters are drawn uniformly randomly from an alphabet of size N. A repeating substring is something like 'aaaaaaaa' or '7777' with the same letter appearing consecutively more than once. Let R be the longest repeating substring of S. What is E(length(R))?

Another question that feels related: Suppose we have an ordering on this alphabet. Let's think of the string S as a sequence instead. Call an increasing subsequence one in which letter is less than (or equal) to those that follow it in the subsequence. These need not be consecutive. What is the expected length of the longest increasing subsequence of S?

Note by Eric Edwards
4 years ago

Sort by:

The second question seems deeper than I expected. Here's a monograph related to the problem: https://www.math.ucdavis.edu/~romik/lisbook/versions/lis.pdf

The Fields medalist Andrei Okounkov among others did recent-ish work on the fluctuations that relates the longest subsequence of a random permutation (a little different from this problem) to the fluctuations of the largest eigenvalue of a random matrix. Neat.

For my first question, I'll try to code up something for strings of digits in a few bases and see if anything pops out. Meanwhile, if any of you brilliant folks know of an analytic approach, let us know. · 4 years ago

Quick update: I wrote some code and think I need a faster way to do this. I don't want to put my code here for review because 1) it stinks and isn't commented yet and 2) I don't want to spoil the challenge that inspired this question for anybody. However, I'm getting for random strings that the E(length(R)) is approximately $$C\log_N (L)$$ with $$C$$ close to 1.

Can anybody prove it? · 4 years ago

That's pretty interesting. Maybe you could brute force it for some small numbers and then conjecture something. · 4 years ago

For the first question. If L is fixed then there is a polynomial pL(N) for which E(length(R)) = pL(N)/N^L. The degree of the polynomial will be L. In the case of L = 3, p3(N) = 3*[N] + 2*[2*N*(N-1)] + 1*[N*(N-1)*(N-1)] = (N+2)*N^2. The bracketed terms above count the number of strings with 3, 2, and 1 repeated substrings respectively. Counting the cases becomes increasing complicated, but perhaps a patten will emerge between the polynomials. We know, p1(N) = N and p2(N) = (N+1)*N. I am working on figuring out p4. · 4 years ago

A very rough estimate for your first question is O(log(L)/log(N)), and for the second one, I believe the answer is O(sqrt(L)), however, here I assumed that the alphabet is of size close to L. If the alphabet is significantly smaller than L, the answer is closer to L/N. I warn you, it could turn out that none of this is correct. I will do some original research and post my results here. · 4 years ago

The answer for your second question is very close to $$2 \sqrt{L}$$, assuming the string to be a permutation of the alphabet of size N=L. (Computed for random strings of size up to 20000) · 4 years ago

There is a wonderful proof of this $$2\sqrt{L}$$ limit in the first chapter of the book that I linked to which uses the limiting shape of the Young Tableaux arising from applying the RSK correspondence to random permutations. · 4 years ago