Deja-Vu Detector

random streams can feel eerily familiar

Starting values — Deja-Vu Detector

Sequence length	40
Pattern window size	3
Simulation trials	3000

Change any control above and the results recompute from these.

Loading interactive simulation...

Certainty needs 120 symbols. Even money needs 13. 🖖

Pigeonhole says when a repeat becomes unavoidable: with 64 possible three-symbol windows, a 120-symbol run holds 118 windows and cannot dodge one. It says nothing about when a repeat becomes likely — that is the birthday bound, and it lands far earlier, around 1.177 × √64 ≈ 9 windows. Push 200,000 random sequences through this tool’s own window counter and the crossover sits at length 13: 11 windows, 51.2%. The shortest sequence it will draw, 10 symbols, already repeats 30.5% of the time, and its smallest preset of 30 symbols repeats 99.6% of the time. Familiarity does not wait for the guarantee.

Why familiar patterns are unavoidable 🖖

That flash of 'I've seen this before' is your brain's pattern-matcher firing, but in a short stream built from only 4 symbols, local repeats are ordinary rather than eerie. With window size 3 there are just 4³ = 64 possible patterns, so a 120-symbol run (118 windows) is forced to repeat at least one by the pigeonhole principle. This tool counts the real repeats and compares them against a random baseline, separating genuine surprise from routine chance.

Some patterns clump more than others 🖖

Two windows of the same length are not equally prone to bunching up. A self-overlapping motif like AAAA or ABAB can line up with a shifted copy of itself, so once it appears it tends to recur immediately, giving it higher variance in its repeat count than a non-overlapping window like ABCD. Guibas and Odlyzko captured this with a pattern's autocorrelation. So the déjà vu you feel depends on which motif recurs, not merely how long it is.

Problem solved in full

A 3-symbol window sliding along a stream of 50 symbols 6 steps
A stream of 50 symbols is drawn from the 4 letters A, B, C, D, and a 3-symbol window slides along it. This is the panel's length 50, window 3 state. How many of those windows should show a pattern that has already appeared? Derive the count, then find the shortest stream for which a repeat is already better than even money.
1. Count the windows before counting anything else. A 3-symbol window can start at position 1 and at every position up to 48, because starting at 49 runs it off the end. That gives 48 windows, and 48 is the denominator every repeat count on the panel is reported against.
  
  $N = L - w + 1 = 50 - 3 + 1 = 48$
2. Now count what they could be. 3 slots, 4 letters each, so 64 patterns exist. There are fewer windows than patterns, which means nothing forces a repeat — the pigeonhole argument gives you nothing here, and whatever happens is chance.
  
  $K = 4^{w} = 4^{3} = 64, N = 48 < K = 64$
3. Turn the question inside out and ask about one pattern, say ABD. A single window fails to be ABD with probability 63/64. Treat the 48 windows as independent draws, as the panel's own expectation does, and they all fail together with probability (63/64)⁴⁸ = 0.4696, so ABD turns up at least once with probability 1 − 0.4696 = 0.5304.
  
  $(1 - \frac{1}{64})^{48} = e^{48 l n (63/64)} = e^{- 0.7559} = 0.4696$
4. That 0.5304 is the chance for every pattern equally, so multiply it by all 64 of them to get the expected number of distinct patterns the stream actually contains.
  
  $E [D] = K [1 - (\frac{63}{64})^{48}] = 64 \times 0.5304 = 33.95$
5. A window is a repeat exactly when its pattern has been seen before, so each pattern that is present contributes precisely one window that is not a repeat. Subtract the distinct patterns from the total windows and the repeats fall out.
  
  $E [R] = N - E [D] = 48 - 33.95 = 14.05$
6. A second route explains why the answer is so large. Instead of asking about patterns, ask about pairs of windows: any two windows carry the same 3 symbols with probability 1/64, and there are 1128 pairs to try.
  
  $(2 48) = \frac{48 \times 47}{2} = 1128, \frac{1128}{64} = 17.6$
Answer

14.05 of the 48 windows repeat, and 17.6 expected matching pairs is why that is not a near miss. Run the pair count backwards to find where a repeat first becomes better than even money. A count with mean λ is zero with probability e^(−λ), and that drops below a half exactly at λ = ln 2, so set the expected matches to ln 2 and you need only 10 windows — a stream of 12 symbols. That is the birthday paradox with 64 birthdays instead of 365, and it is why a 50-symbol stream repeating itself is not a signal but the floor. Carry one caveat with you: neighbouring windows share 2 of their 3 symbols, so they are not the independent draws either count assumes, and the real break-even sits a symbol or so longer.

$\frac{1}{K} (2 N) = ln 2 ⟹ N (N - 1) = 2 (64) (0.6931) = 88.7, N \approx 10, L = N + w - 1 = 12$

References (1)

Insight block 3 — why AAAA clumps and ABCD does not: L. J. Guibas and A. M. Odlyzko, "String overlaps, pattern matching, and nontransitive games." Journal of Combinatorial Theory, Series A 30(2), 183–208, 1981 — the correlation polynomial that measures how a pattern overlaps a shifted copy of itself.

By the 42Math team · Updated 2026-07-29

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Statistics & Finance lessons →

Example problems

short run - Short sequence with 3-symbol windows: repeats still appear quickly.
medium run - Medium sequence shows that repeated motifs are normal by chance.
dense deja-vu - Longer sequences with bigger windows still generate deja-vu clusters.