2
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ With LCS I meant longest common substring not subsequence. What you say counts for subsequences but in a substring it wont be "ABCD" since X is in between ABC and D $\endgroup$
    – Ilhan
    Jan 12, 2017 at 12:37
  • $\begingroup$ thw longest consecutive piece in both strings is ABC $\endgroup$
    – Ilhan
    Jan 12, 2017 at 12:38
  • $\begingroup$ Sorry all the misunderstandings are due to my English.. I've edited and corrected everything. Permutation was a bad word to use. With concrete I mean any paper which I can use for referencing (best'd be published) i.e. "this is proven in ... [1]" Refferences: [1] this and this paper, pp. xyz.. @MattF. $\endgroup$
    – Ilhan
    Jan 12, 2017 at 13:06
  • $\begingroup$ Please state if anything else is left unclear and needs clarification so I can edit my post! $\endgroup$
    – Ilhan
    Jan 12, 2017 at 13:10
  • $\begingroup$ Ok, I deleted my previous comments, so those issues are fixed. But now it needs better examples, which are not permutations. $\endgroup$
    – user44143
    Jan 12, 2017 at 13:17

2 Answers 2

3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you sure it is the same as the longest expected occourance of H coin flips? It is allowed for the common substring to be HTHHTHT.. in that analogy $\endgroup$
    – Ilhan
    Jan 12, 2017 at 14:43
  • 1
    $\begingroup$ I meant that the proof is the same. $\endgroup$
    – Pat Devlin
    Jan 12, 2017 at 14:44
  • $\begingroup$ So it would be the expected wait time of that occourance $\endgroup$
    – Ilhan
    Jan 12, 2017 at 14:46
  • $\begingroup$ Sure. Depending on what you mean by "wait time." $\endgroup$
    – Pat Devlin
    Jan 12, 2017 at 15:39

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.