Dgdrxrt

I have a software test failing from time to time, due to the fact that the string 123 appears when generating a string with SecureRandom.hex(32) (Ruby), which gives a 64 symbols string.

This includes (A-F) and (0-9), so 16 symbols possible.

I have played a little, and I noticed that it can roughly happens 1500 times over 100,000 calls to the function, so around 1.5%.

What would be the formula to have the exact probability of this test failing?

As a developer, I had to share a little bit of code: JS Fiddle.

Edit: Answer's WolframAlpha link

54392126209570846953192790832763093471349103670511891931049735583247364107/
3618502788666131106986593281521497120414687020801267626233049500247285301248
≈0.0150317
≈1.50317%

An exact answer, via Inclusion Exclusion Principle:

Let $A_i =$ the set of 64-long strings where "123" appears starting at the $i$th position ($1 le i le 62$). E.g. if "123" appears at both the 2nd and 40th positions in string $x$, then $x in A_2$ and $x in A_40$, i.e. $x in A_2 cap A_40 $.

Then $S = bigcup_i A_i=$ the set of strings where "123" appears at least once, and your desired probability is $|S|/16^64$.

The Inclusion Exclusion Principle gives:

$$|S| = |bigcup A_i| = sum_i |A_i| - sum_i<j |A_i cap A_j| + sum_i<j<k |A_i cap A_j cap A_k| - dots $$

Obviously $|A_i| = 16^61$ as the other 61 positions can be anything. So the first term is $sum_i |A_i| = 62 cdot 16^61$.

Now two occurrences of "123" cannot overlap (unlike e.g. if you're looking for "111" in which case they CAN overlap). So if $j - i < 3$, then $|A_i cap A_j| = 0$. For the non-trivial case of $j - i ge 3$, the other $64 - 3 - 3 = 58$ positions can be filled with anything, so $|A_i cap A_j| = 16^58$.

Meanwhile, how many $(i, j)$ pairs are there s.t. $j - i ge 3$? Imagine "merging" each "123" into a new character "!", so the final string length is now $64-2-2 = 60$ instead and there are two "!" characters. The number of ways to do this is simply $60 choose 2$. Thus the 2nd term is:

$$ sum_i<j |A_i cap A_j| = 60 choose 2 16^58$$

The $m$th term is similar and we have:

$$ sum_i_1 < i_2 < cdots < i_m |A_i_1 cap A_i_2 cap cdots cap A_i_m| = 64 - 2m choose m 16^64 - 3m $$

So the final result is:

$$ |S| = sum_m=1^21 (-1)^m+1 64 - 2m choose m 16^64 - 3m $$

This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set words of length $ngeq 0$ built from the alphabet $mathcalV=0,ldots,9,A,ldots,F$ and the set $B=123$ of bad words, which are not allowed to be part of the words we are looking for.

• We derive a generating function $f(s)$ with the coefficient of $s^n$ being the number of these words of length $n$.




• Since we are looking for the number of words which contain the bad word $123$, the resulting generating function is the generating function of all words minus $f(s)$
  beginalign*
  &1+16s+16^2s^2+16^3s^3cdots-f(s)=frac11-16s-f(s)
  endalign*

According to the paper (p.7) the generating function $f(s)$ is
beginalign*
f(s)=frac11-ds-textweight(mathcalC)tag1
endalign*
with $d=|mathcalV|=16$, the size of the alphabet and $mathcalC$ the weight-numerator of bad words with
beginalign*
textweight(mathcalC)=textweight(mathcalC[123])
endalign*

We calculate according to the paper
beginalign*
textweight(mathcalC)=textweight(mathcalC[123])&=-s^3tag2\
endalign*

It follows from (1) and (2)

beginalign*
f(s)=frac11-16s+s^3\
endalign*
and the generated function counting all strings which contain $123$ is
beginalign*
&colorbluefrac11-16s-frac11-16s+s^3=s^3 + colorblue32 s^4 + 768 s^5 + 16,383 s^6 +cdotstag3\
endalign*

The coefficients of the series were calculated with the help of Wolfram Alpha. We see for instance there are $colorblue32$ words of length $4$ which contain the bad word $123$. These are $$(0..9,A..F)123qquadtext and qquad 123(0..9,A..F).$$

The coefficient of $s^n$

In fact we are interested in the coefficient of $s^64$. We calculate the coefficient of $s^n$ from (3). It is convenient to use the coefficient of operator $[s^n]$ to denote the coefficient of $s^n$ of a series.

We obtain from (3) for $ngeq 0$

beginalign*
colorblue[s^n]&colorblueleft(frac11-16s-frac11-16s+s^3right)\
&=[s^n]sum_m=0^infty 16^ms^m-[s^n]sum_m=0^infty s^m(16-s^2)^m\
&=16^n-[s^n]sum_m=0^infty s^msum_k=0^mbinommk(-1)^ks^2k16^m-k\
&=16^n-sum_m=0^n[s^n-m]sum_k=0^mbinommk(-1)^ks^2k16^m-k\
&=16^n-sum_m=0^n[s^m]sum_k=0^n-mbinomn-mk(-1)^ks^2k16^n-m-k\
&=16^n-sum_m=0^lfloor n/2 rfloor [s^2m]sum_k=0^n-2mbinomn-2mk(-1)^ks^2k16^n-2m-k\
&=16^n-sum_m=0^lfloor n/3 rfloorbinomn-2mm(-1)^m16^n-3m\
&,,colorblue=sum_m=1^lfloor n/3 rfloorbinomn-2mm(-1)^m+116^n-3mtag4\
endalign*

Finally we obtain from (4) in accordance with the answer of @antkam the wanted probability

beginalign*
colorblue[s^64]colorblueleft(frac11-16s-frac11-16s+s^3right)16^-64&colorblue=sum_m=1^21binom64-2mm(-1)^m+116^-3m\
&colorbluesimeq 0.01503,16662,40506
endalign*

which gives roughly $colorblue1.5%$.

Just a quick hint: total number of all possible strings is $16^32$, the number of strings that contain at least one occurrence of "$123$" is $32 cdot 16^29=2cdot 16^30$ ($32$ spots to put substring "$123$" and we need to fill remaining $29$ positions). The probability for truly random generation should be $$frac2cdot 16^3016^32=frac1128$$