Waste less time on Facebook — follow Brilliant.

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

No vote yet
7 votes


Sort by:

Top Newest

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. Eric Edwards · 4 years ago

Log in to reply

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? Eric Edwards · 4 years ago

Log in to reply

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

Log in to reply

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. Adam Buck · 4 years ago

Log in to reply

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. Ivan Stošić · 4 years ago

Log in to reply

@Ivan Stošić 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) Ivan Stošić · 4 years ago

Log in to reply

@Ivan Stošić 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. Eric Edwards · 4 years ago

Log in to reply


Problem Loading...

Note Loading...

Set Loading...