Mean length of the longest substring (not sequence) of a random string

Question

Introduction

I am analyzing the average complexity of an algorithm and it boils down to this question:

Question

What is the expected substring length which two randomly generated strings will most likely have?

I found a lot of papers covering this topic on subsequences but couldn't find any for substrings. The difference is that in a subsequence the characters can appear with any space in between as long as they're in the same order but substrings have to be consecutive (i.e. "ABC" has to appear together, "ABxC" doesn't count).

Example: In "ABCED" and "ABCXED" the longest substring is "ABC" (length = 3)

Another way to look at it:

Example: In "ABCDE" and "ABCED" the longest common substring (LCS) is "ABC" (length = 3)

Another (non random) example: "EXXAMPPLEEE" and "XXXAMPPLXXX" would have the longest common substring would be "XAMP" of length = 4.

Assuming that we generate two strings randomly of length $N$ and of alphabet size $q$, measure the length of the longest common substring and repeat this infinitely many times. What is the mean average substring length in function of N, q ?

What would be the expected common substring length to be found in a random string of length $N$ and alphabet $q$

What I Researched

My intuition and approximation suggested AVG_LCS_LENGTH = $log_q(N)$ I've read in an unofficial source that it is $2log_q(N)$ but I couldn't find anything to reference.

What I'd accept as an answer

Since I assume that this proof isn't trivial, any reference to a paper proving this and which I could use and reference for my research would be acceptable as an answer or if somebody could write a proof of course.

Answer 1

I don't know if the answer still interest you, anyway:

First of all, you need to define clearly what you mean by longest substring:

-you only look at the longest substring at the beginning of the sequences

-your longest substring can be anywhere but needs to be at the same position in both sequences

-your longest substring can be anywhere

Secondly, you wrote "we generate two strings randomly", I will assume you mean that we are in the iid case.

If it's 𝑙𝑜𝑔𝑞(𝑁) or 2𝑙𝑜𝑔𝑞(𝑁) will depend on the definition you choose.

You can see the paper of Arratia and Waterman and the references in the paper: https://www.sciencedirect.com/science/article/pii/0001870885900039

If you want results for more general processes (not only iid), the answers will be different and will involve the Renyi entropy. You can see this paper and the references therein: https://www.sciencedirect.com/science/article/pii/S000187081930026X

Answer 2

Let $X_k$ denote the number of substrings (count pairs of starting indices) of length $k$ that the two things share. Finding expected value of $X_k$ is easy by linearity of expectation. Then your answer is going to be very close to the $k$ for which this value is close to $1$. This is exactly like finding the longest string of "H" in a series of coin flips or like finding the independence number of a random graph. To make this more rigorous, you show concentration of $X_k$ about their mean.