piprobabilityrandom
This isn't homework, I'm actually (please don't ask me why) wondering how likely it is that any particular 11-digit telephone number will occur in the first billion digits of pi. My probability course was way too long ago, and the idea of creating a monte carlo simulation to figure this out seems a little extreme!
(And I realize that pi is not a random number, I'm just assuming that the digits are sequenced in a randomlike way.)
I know this question just celebrated its 8th birthday, sorry. I always think that better late than never.
The range of the output has nothing to do with the period. You can have a truly random generator that produces bits one by one, and it won't be periodic, even if its output only has 2 different values. In your case, the range of the output is from 1 to 30, rather than from 0 to 1, but the idea is the same.
Now, the output of the LCG does have a period of 30, but the output of the shuffle does not. Numbers that enter the Bays-Durham array aren't extracted in the same order they entered, but in a pseudo-random order; a particular number in the array may be delayed for quite some draws compared to others. This changes the periodicity: while the LCG's state can only hold 30 possible values, and hence its period can't be more than 30, the Bays-Durham array and internal index provide additional state that alters the period, without changing the output range nor significantly altering the probability of any particular number. An upper bound for the period of this combined generator is given by the number of its possible states, which if my numbers aren't wrong, is $30^9·8 = 1.57464·10^{14}$ (eight numbers from 1 to 30 in the array, one number from 1 to 30 in the LCG and 8 possible values for the internal index); that's approximately 47.16 bits of information. I don't know if it will achieve that period, though, but that upper limit suggests that it's not expected to be short.
As another example, if the input to the shuffle is the sequence $1, 2, 3, ..., 29, 30, 1, 2, 3, ...$ which obviously has period 30, the first 100 numbers of the output are:
3, 1, 11, 10, 13, 4, 12, 14, 15, 18, 5, 2, 16, 20, 6, 21, 24, 7, 25, 27, 29, 8, 28, 1, 22, 26, 30, 3, 4, 8, 2, 9, 17, 23, 5, 10, 12, 16, 13, 19, 18, 20, 14, 19, 21, 22, 25, 6, 15, 23, 26, 27, 1, 11, 17, 24, 2, 3, 7, 28, 7, 9, 4, 8, 11, 12, 15, 29, 10, 16, 5, 14, 17, 20, 30, 18, 23, 24, 6, 21, 27, 28, 25, 1, 13, 22, 30, 2, 4, 8, 29, 7, 10, 19, 26, 3, 9, 13, 5, 12
No sign of periodicity there, as you can see, even though the input is anything but random. The number 3, for example, appears 4 times, in positions 1, 28, 58 and 96. It's followed by 1 the first time, by 4 the second, by 7 the third, and by 9 the fourth.
If you draw the output in pairs, you can of course plot them in a 30×30 square, because you will have lots of (pseudo)independent pairs. You're not limited to 15 different pairs; you would if you took the period-30 output of the LCG.
This also explains why Bays-Durham breaks the "hyperplanarity" of the LCG: the numbers that were consecutive are no longer consecutive, but instead separated by a (pseudo)random distance, therefore if we try to plot pairs of numbers, we won't be plotting numbers that are consecutive in the LCG.
The above series uses Knuth's method to derive the index, which applied to this case, is $j = \lfloor\frac{8·(X_i-1)}{30}\rfloor$ (as a zero-based index). But the book uses a different method: $j = X_i\bmod 8$, adding 1 to make it 1-based. With that method, I get the following plot out of 5,000 pairs:
I don't know how it compares to either of the images because I can't see them.
Suppose $n$ is repeated. There are 9 other numbers that can occur. And the other digit can occur in 4 possible positions giving $36$ possibilities.
There are $10$ possibilities for $n$ so the total number of combinations with exactly three digits the same is $360$.
Best Answer
The problem is actually fairly complicated, and I would refer you to the article "A unified approach to word occurrence probabilities" (link) for an exhaustive analysis. But we can approximate the result more simply.
Note that the expected number of occurrences (counting overlaps) is trivial to obtain: there are $N-n+1$ possible starting positions, and the probability of an occurrence at each such position is $10^{-n}$, so the expected number of occurrences is exactly $(N-n+1)10^{-n}$. For $N=10^9$ and $n=11$, this is $10^{-2} - 10^{-10} \approx 0.01$. So we know that $$ \sum_{i=0}^{\infty}i\cdot p_i = p_1 + 2p_2 + \cdots=p_{\ge 1}+p_{\ge 2}+\cdots=(N-n+1)10^{-n}, $$ where $p_i$ is the probability of exactly $i$ occurrences and $p_{\ge i}$ is the probability of at least $i$ occurrences. In particular, we have this exact result: $$ p_0=1-p_{\ge 1}=1-(N-n+1)10^{-n}+p_{\ge 2}+p_{\ge 3}+\cdots. $$ We see that the likelihood of there being no occurrences increases, perhaps surprisingly, along with the likelihood of there being multiple occurrences. Now, in your case $N\gg n$, so we can largely ignore the existence of one occurrence when looking for another: any pairs are almost certain to be far apart, so the probability of any pairs is about $\frac{1}{2}(0.01)^2$, giving $$ p_0 \approx 1 - 0.01 + \frac{1}{2}(0.01)^2=0.99005. $$ However, there are two exceptions arising from self-overlapping phone numbers. If the phone number consists of a single digit (1-111-111-1111), then given one occurrence, an immediate recurrence has probability $10^{-1}$. This makes $p_{\ge 2}\approx 10^{-3}$ instead (twenty times larger than usual), hence $p_0\approx 0.991$. Similarly, if the phone number consists of a repeating pair of digits (1-212-121-2121), then an immediate recurrence has probability $10^{-2}$. This combines with the (comparable) probability of an independent second occurrence to give $p_{\ge 2}\approx 1.5\times 10^{-4}$ (three times larger than usual), hence $p_0\approx 0.99015$. (Phone numbers that self-overlap at longer intervals, like 1-213-121-3121, are also slightly less likely to occur, but there the effect is small enough to be ignored.)