# What is the probability for an N-char string to appear in an M-length random string?

Link shortening service bit.ly allows you to, as you might expect, shorten URLs. URLs get shortened using a 7-character string. The alphabet of this string consists of a-z, A-Z and 0-9.

Today, Dutch police have used bit.ly for a tweet about the finding of a body of a girl that was missing for two weeks. Unfortunately, the bit.ly string contained the word "Dead": https://twitter.com/PolitieUtrecht/status/918507900452077568.

That got me wondering: what is the probability that this exact 4-character string will appear in a 7-character string (generated with an alphabet of 62 characters)?

Or, more generally, what is the probability that a defined string $\alpha$ with length $S$ appears somewhere in a string $\beta$ with length $M$, with $M$ being a randomly generated string with an alphabet of 62 characters?

At first I thought "7 positions, 62 possibilities" means $62^7$ combinations, but I'm sure that's not right -- that's the possibility for a 7-character string (e.g. the complete string).

What is a proper method for calculating this?

• The answer by knrumsey is better than mine. Would you be so kind to un-accept my answer and accept theirs? Thank you! (I would consider deleting mine, but it may serve as useful context for knrumsey's.) Jun 24, 2022 at 14:17

This answer can be viewed as supplemental to @StephanKolassa's answer, in light of the counterexample provided in the comment by @whuber.

Although the accepted answer is not a general solution, it does work for the specific question asked by the OP. We will start with a sufficient condition for the formula to hold.

Let $$L$$ be the length of the largest string $$\gamma$$ such that $$\alpha = \gamma\delta\gamma$$, where $$\delta$$ is an arbitrary string. Let $$\alpha$$ and $$\beta$$ be strings of length $$S$$ and $$M$$ respectively.If $$\beta$$ is generated uniformly at random from an alphabet with $$N$$ distinct characters, then the probability that $$\beta$$ contains $$\alpha$$ is equal to $$\frac{M-S+1}{N^S}$$ so long as $$S < M < 2S-L$$

This extra condition $$M < 2S - L$$ is sufficient to ensure that no double counting of strings occurs. Without this condition, there is a potential for double counting, so that the formula becomes an upper bound on the actual probability. Note also that this condition rules out @whubers counterexample ($$3 \nless 2\cdot 2 - 1)$$.

### Other examples

In the original example, if we increase $$M$$ from $$7$$ to $$8$$, the string DeadDead would be counted twice: once when we count all strings of the form Dead???? and again when we count strings like ????Dead.

To see the role of $$L$$ it is hepful to consider a new string of interest, say $$\alpha =$$onion, which has $$L = 2$$ ($$\gamma =$$ on, $$\delta =$$ i). Suppose for example that $$M=8$$, and consider the string onionion. This will be double counted when we consider patterns onion??? and ???onion.

### dead not Dead

What if the OP had asked for the probability that a $$7$$ character string contained the word dead rather than Dead. Now, the previously stated formula would not apply, because $$7 \nless 2\cdot 4 - 1$$. Thankfully, the answer is straightforward here, since we are over counting by just one. The probability becomes $$\frac{4}{62^4} - \frac{1}{62^7},$$ which, of course, is practically indistinguishable from the previous answer.

As $$M$$ grows and becomes much larger than $$2S - L$$, the propensity for double counting will grow however, and the upper bound will become less tight.

#### Bonus

It is not too hard to come up with an English word having $$L = 3$$, for example ionization. Comment if you can come up with a common English word such that $$L=4$$!

##### Edit:

The bonus points go to @SextusEmpiricus who tracked down the English word sterraster! This word corresponds to $$L=4$$. Anybody want to try for $$L=5$$?

• +1. Would "arrest string" be a typo for "largest string"? For an exhaustive analysis of this problem, research the Boyer-Moore algorithm
– whuber
Mar 24, 2022 at 17:01
• @whuber. Yes, thank you for catching that Mar 24, 2022 at 17:13
• @SextusEmpiricus I'm a little confused at your comment. It seems that you are agreeing with the primary point of my answer. This is exactly my point in bringing up the distinction between dead and Dead. Am I missing something? Mar 24, 2022 at 18:42
• If you read "string" as more general that "word" (e.g., "string" could hold spaces), then "any quine could serve as an example of any quine could serve as an example of." Mar 24, 2022 at 20:39
• merriam-webster.com/dictionary/sterraster Jun 24, 2022 at 15:57

The answer by Stephan Kolassa works, but it is not general as noted in the answer by knrumsey.

Several questions here have had similar issues with the overlap/double counting. For methods to solve this see

Probability of a similar sub-sequence of length X in two sequences of length Y and Z

A fair die is rolled 1,000 times. What is the probability of rolling the same number 5 times in a row?

Below is an example of a Markov chain that can be used to solve it. In this case it is case insensitive (if we have x correct letters then there are two possible letters, upper case and lower case, that can be added to get x+1 correct letters)

To compute the probability you take the appropriate power of the matrix that describes the Markov chain.

library(matrixcalc)
M <- matrix(c(60/62,58/62,58/62,60/62,0/62,
2/62, 2/62, 2/62,0/62,0/62,
0/62, 2/62, 0/62,0/62,0/62,
0/62, 0/62, 2/62,0/62,0/62,
0/62, 0/62, 0/62,2/62,62/62),
nrow=5, byrow=TRUE)
row.names(M) <- stateNames; colnames(M) <- stateNames
M
#              -          d         de        dea dead
#-    0.96774194 0.93548387 0.93548387 0.96774194    0
#d    0.03225806 0.03225806 0.03225806 0.00000000    0
#de   0.00000000 0.03225806 0.00000000 0.00000000    0
#dea  0.00000000 0.00000000 0.03225806 0.00000000    0
#dead 0.00000000 0.00000000 0.00000000 0.03225806    1
# 4.331213e-06


In the above links, there are examples of how to compute estimates of the solution obtained with this Markov chain.

• This works better as a comment to the question.
– whuber
Mar 24, 2022 at 18:42
• @whuber you are right that the answer is a bit short but the question is "What is the probability for an N-char string to appear in an M-length random string?" In that case both the other two answers do not address the general problem. The first answer only gives an answer to the special case and the other explains why/when it is a special case. But how do we solve the question? That remains open. I have just given links to other questions because it is a bit like a duplicate question. I am not sure yet how to elaborate more on it with relation to those other questions. Mar 24, 2022 at 19:24
• @whuber I have added a more concrete example to build a solution rather than jus linking to the other posts. Mar 26, 2022 at 9:38

EDIT: The answer by knrumsey is better than mine. I hope the OP will un-accept my answer and accept theirs. (I would consider deleting mine, but it may serve as useful context for knrumsey's.)

Overall, there are $$62^M$$ different possible strings, because you have $$62$$ choices for each of the $$M$$ characters.

How many of these $$62^M$$ strings contain your prespecified string $$\alpha$$? Well, for each "hit", we still have $$M-S$$ characters that we can choose freely, and $$\alpha$$ can appear in $$M-S+1$$ different places in the full string. So we have $$(M-S+1)\times 62^{M-S}$$ "hits".

Dividing, we get a probability of

$$\frac{(M-S+1)\times 62^{M-S}}{62^M} = \frac{M-S+1}{62^S}.$$

When $$M = 7$$ and $$S = 4$$, the probability is 1 in 3,694,084.

(Of course, that doesn't account for the fact that the effect would have been the same if the random string had contained similar words like "killed" or "corpse", or simply a different capitalization of "Dead".)

• Let's try this in a simpler situation; say, searching for a string of length $S=2$ in a random string of length $M=3$ where the alphabet has only two characters "0" and "1" rather than $62.$ It looks like your formula would be $\frac{M-S+1}{2^S}=\frac{3-2+1}{2^2}=\frac{1}{2}.$ Apply this, for instance, to the string "00." Only the strings "000", "001", and "100" contain this substring, so the correct answer for the example must be $3/8.$ I believe something is wrong in your analysis and it derives from hidden, not always correct assumptions about the details of the target string $\alpha.$
– whuber
Mar 3, 2022 at 21:22
• Are you assuming that each character is used once? I am not understanding where the "$-S$" in $M - S$ comes from. For example, one might be interested in the length $S=10$ string "AAAAAAAAAA" in an alphabet of size $2$: A, B, right? Oh... looks like whuber has Ninja'ed me (and is asking more clearly to boot). :D Mar 24, 2022 at 20:34