Probability that at least 5 adjacent length-4 blocks of a certain kind occur in a string of 26 random digits

51 Views Asked by At

Let a "$(4,2)$-block" be any string of four digits exactly two of which are equal.

Question: What is the probability that in a string of $26$ decimal digits, chosen independently and uniformly at random, there occur at least $5$ adjacent non-overlapping $(4,2)$-blocks?

An example of this occurring would be the outcome $141592(6535)(8979)(3238)(4626)(4338).$ The $1415$ block is not counted because it is not adjacent to the other five.

So far, I have only a poor upper bound using Boole's inequality. If we let $A$ denote the event whose probability we seek, then $A$ is the union of the following seven events, where each 'xxxx' denotes some $(4,2)$-block and each 'y' denotes an arbitrary digit:

A1:  xxxx xxxx xxxx xxxx xxxx yyyyyy
A2:  y xxxx xxxx xxxx xxxx xxxx yyyyy
A3:  yy xxxx xxxx xxxx xxxx xxxx yyyy
A4:  yyy xxxx xxxx xxxx xxxx xxxx yyy
A5:  yyyy xxxx xxxx xxxx xxxx xxxx yy
A6:  yyyyy xxxx xxxx xxxx xxxx xxxx y
A7:  yyyyyy xxxx xxxx xxxx xxxx xxxx

With hopefully obvious notation, we have, by Boole's inequality,

$P(xxxx)\\ \le P(ee..)+P(e.e.)+P(e..e)+P(.ee.)+P(.e.e)+P(..ee)\\ \le 6\times ({10\times 100\over 10^4})\\ \le{3\over 5}$

where 'e's denote the equal digits and '.'s denote arbitrary digits. Then, again by Boole's inequality,

$P(A)\\ \le P(A_1)+\dots+P(A_7)\\ \le 7\times({3\over 5})^5\\ \le 0.544$