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

Question

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?

Answer 1

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$?

Edit (12/23):

@PhilipSwannell tracked down the English word undergrounder, a great example for $L=5$. He also came up with benzeneazobenzene, a cool $L=7$ word. But since benzeneazobenzene isn't a word on merriam-webster.com, I think I (personally) will consider undergrounder the current record.

Answer 2

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)
stateNames <- c("-","d","de","dea","dead")
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
matrix.power(M,7)["dead","-"]
# 4.331213e-06

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

Answer 3

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".)