Probability of text in a string and probability that the text is random if I keep seeing the text. This is a simplification of my real problem that I will mention specifically at the end. First, a comment on the real problem at hand.
I looked at a specific series of supposedly random data and I saw a specific pattern of six characters (bytes). The same pattern exists in more than one piece of data. If I have 15000 sets and I see the pattern 10 times, do I call this random? What about 100 times? I did not keep my statistic book from the one stats class I had in the early 1980's, it would probably help.
For my first attempt, I just wanted to know if a series of bits are random, so look at each data set and see if it looks random. NIST has advise (see https://nvlpubs.nist.gov/nistpubs/legacy/sp/nistspecialpublication800-22r1a.pdf), which is an interesting read. If I only modify a small number of bytes of the data, it is not really likely to affect data of length 100 to 1000 in length for over-all randomness.
I am unsure if I should attempt to frame the question as "what percentage of my data sets can contain something odd before I call it a problem" (kind of like evaluating parts with failure) or should I look at over-all probabilities of a specific string showing up more times than it should.
My first attempt to look at probabilities, I considered an easier problem where I assum that I have a series of "random" lower case strings and I do not expect to see some specific string $S$ of length $n$. Allowing for duplicate letters there are $26^n$ possible strings of length $n$. Assume, for example, I see my name "andy" I think, that does not seem random. So I start searching all of my strings for "andy" and I see that many of the strings contain the pattern "andy". If I see "andy" once in a million strings I think, maybe it was random. If I see my name many times, I start thinking it is not random. How can I assign some confidence that this is random or now?
Understanding that every random string may have a different length, at what point can I say "I have seen my name 10 times in one million strings so this cannot be random"?
Initially, I started looking at the probability that given one random string, what is the probability that I would see my name exactly one time and I do not care where it is in the string. If I assume that the string is of length $m$ where $m \ge n$, I became lost just trying to think about assigning a probability that the specific string would contain my name.
While trying to wrap my head around this, I considered $m=n$, which of course means a probability of $26^{-n}$ since only one would match. But what if $m=n+1$, then things get ugly when I start considering that the match could start at location 1 or 2, and what if it could start at 1 and 2 (if say the string is all the same character)?
 A: The simplest calculation relevant to this question is the following: consider our data as a long string $N$ of length $n$ from an alphabet of size $a$ (so if we consider bits then $a = 2$, while if we consider bytes then $a = 2^8 = 256$). Suppose $S$ is some specific string of length $s$ from the same alphabet. If $D$ is chosen randomly (meaning each of its letters is chosen independently and uniformly at random from the alphabet), what is the expected number of times that $S$ appears in $D$?
Happily this calculation is straightforward using linearity of expectation. We consider any block of $s$ consecutive letters in our string $N$: the probability that this block equals $S$ is $\frac{1}{a^s}$. The number of such blocks in $N$ is $n - s + 1$, so the expected number of times that $S$ appears is exactly $\boxed{ \frac{n - s + 1}{a^s} }$, or about $\frac{n}{a^s}$. Importantly, this is true even though the blocks can overlap, meaning the events that two overlapping blocks are both equal to $S$ are not independent.
To put some specific numbers to this, if $a = 2^8, s = 6$ then this means you should expect to see a given string of six bytes about once every $a^s = 2^{48} \approx 2.8 \times 10^{14}$ random bytes you examine, or about $280$ terabytes. I don't know what you mean by "$15000$ sets" since you don't specify how many bytes are in each set, but if you observed the pattern $10$ times then you'd need to be observing about $2.8 \times 10^{15}$ random bytes total (about $2.8$ petabytes) to dismiss this as a coincidence.
This does not strictly follow from the expected value calculation alone; you also need some guarantee that the number of such blocks is unlikely to deviate much from its expected value. This is true but I'm not sure what the simplest way to show it is. Basically you can show that the number of appearances of $S$ is approximately Poisson, with rate parameter approximately $\lambda = \frac{n}{a^s}$, so that you can use known tail bounds for how quickly the Poisson distribution decays away from its mean. You can see this Poisson behavior in numerical experiments by generating long strings of random bytes and counting, say, the number of appearances of a specific string of $2$ or $3$ bytes ($6$ would take awhile as we've seen above).
A: Probably not the kind of answer you are looking for (see Qiaochu Yuan for the standard probabilistic calculation).
But a simple empirical procedure to test for the randomness of some (long) text, especially if you suspect about repeated patterns, is to compress it using a standard compressor (gzpip, zip, winzip, 7z...). If the text is truly random, then the entropy of it is $H=\log N$ bits per symbol, where $N$ is the number of allowed symbols. Hence (first Shannon theorem) the optimal coding should tend to this amount of bits - in the case of random bytes, you would have 8 bits per byte, that is, no compression at all. The standard generic compressors mentioned above are ussually based on Lempel-Zip coding, which seek to detect repeated patterns, and which tend to the optimal (entropic) coding for very large (and stationary) sequences.
If the compression attains a lower size, then you can deduce that the sequence is not totally random.
