Detector de Déjà Vu

sequências aleatórias podem parecer estranhamente familiares

Valores iniciais — Detector de Déjà Vu

Comprimento da sequência	40
Tamanho da janela do padrão	3
Tentativas de simulação	3000

Altere qualquer controlo acima e os resultados são recalculados.

A carregar a simulação interativa...

A certeza precisa de 120 símbolos; o cara ou coroa, de 13 🖖

O princípio da casa dos pombos diz quando uma repetição se torna inevitável: com 64 janelas possíveis de três símbolos, uma sequência de 120 símbolos tem 118 janelas e não escapa de uma. Ele não diz nada sobre quando uma repetição se torna provável — isso é o limite do aniversário, e ele chega muito antes, por volta de 1,177 × √64 ≈ 9 janelas. Passe 200.000 sequências aleatórias pelo contador de janelas desta própria ferramenta e a virada fica no comprimento 13: 11 janelas, 51,2%. A sequência mais curta que ela sorteia, 10 símbolos, já se repete 30,5% das vezes, e seu menor preajuste, de 30 símbolos, 99,6%. A familiaridade não espera pela garantia.

Por que padrões familiares são inevitáveis 🖖

Aquele lampejo de 'já vi isto antes' é o detector de padrões do seu cérebro em ação, mas num fluxo curto formado por apenas 4 símbolos as repetições locais são comuns, não misteriosas. Com janela de tamanho 3 existem apenas 4³ = 64 padrões possíveis, de modo que uma sequência de 120 símbolos (118 janelas) é obrigada a repetir pelo menos um, pelo princípio da casa dos pombos. Esta ferramenta conta as repetições reais e as compara com uma linha de base aleatória, separando a surpresa genuína do acaso rotineiro.

Alguns padrões se aglomeram mais que outros 🖖

Duas janelas do mesmo comprimento não tendem a se agrupar igualmente. Um motivo autossobreposto como AAAA ou ABAB pode se alinhar com uma cópia deslocada de si mesmo, então, uma vez que aparece, tende a recorrer de imediato, com maior variância na contagem de repetições do que uma janela sem sobreposição como ABCD. Guibas e Odlyzko capturaram isso pela autocorrelação de um padrão. Assim, o déjà vu que você sente depende de qual motivo retorna, não apenas de seu comprimento.

Problema resolvido na íntegra

Uma janela de 3 símbolos a deslizar por um fluxo de 50 símbolos 6 passos
Um fluxo de 50 símbolos é extraído das 4 letras A, B, C, D, e uma janela de 3 símbolos desliza ao longo dele. Este é o estado de comprimento 50, janela 3 do painel. Quantas dessas janelas deverão apresentar um padrão que já tenha aparecido? Deduza essa contagem e, em seguida, encontre o fluxo mais curto para o qual uma repetição seja já mais provável do que não.
1. Conte as janelas antes de contar qualquer outra coisa. Uma janela de 3 símbolos pode começar na posição 1 e em todas as posições até 48, porque começar em 49 ultrapassa o fim. Isso dá 48 janelas, e 48 é o denominador em relação ao qual todas as contagens de repetições no painel são apresentadas.
  
  $N = L - w + 1 = 50 - 3 + 1 = 48$
2. Agora conte o que elas poderiam ser. 3 posições, 4 letras cada, pelo que existem 64 padrões. Há menos janelas do que padrões, o que significa que nada obriga a uma repetição — o princípio da casa dos pombos não ajuda em nada aqui, e tudo o que acontece é fruto do acaso.
  
  $K = 4^{w} = 4^{3} = 64, N = 48 < K = 64$
3. Inverta a pergunta e considere um único padrão, por exemplo, ABD. A probabilidade de uma janela não apresentar ABD é 63/64. Se tratarmos as 48 janelas como observações independentes, tal como faz o cálculo da esperança no próprio painel, a probabilidade de nenhuma apresentar ABD é (63/64)⁴⁸ = 0,4696. Logo, a probabilidade de ABD aparecer pelo menos uma vez é 1 − 0,4696 = 0,5304.
  
  $(1 - \frac{1}{64})^{48} = e^{48 l n (63/64)} = e^{- 0.7559} = 0.4696$
4. Esse valor de 0,5304 é a probabilidade de cada padrão em igual medida, pelo que deve multiplicá-lo por todos os 64 padrões para obter o número esperado de padrões distintos que o fluxo realmente contém.
  
  $E [D] = K [1 - (\frac{63}{64})^{48}] = 64 \times 0.5304 = 33.95$
5. Uma janela é uma repetição exatamente quando o seu padrão já apareceu. Assim, cada padrão presente corresponde a uma única janela que não é repetida. Subtraia do número total de janelas o número de padrões distintos e obtém o número de repetições.
  
  $E [R] = N - E [D] = 48 - 33.95 = 14.05$
6. Um segundo caminho explica por que razão a resposta é tão elevada. Em vez de perguntar sobre padrões, pergunte sobre pares de janelas: quaisquer duas janelas contêm os mesmos 3 símbolos com probabilidade 1/64, e existem 1128 pares para testar.
  
  $(2 48) = \frac{48 \times 47}{2} = 1128, \frac{1128}{64} = 17.6$
Resposta

Das 48 janelas, 14,05 são repetições, e os 17,6 pares coincidentes esperados mostram que o resultado não foi por pouco. Faça agora o cálculo dos pares ao contrário para descobrir quando uma repetição passa a ser mais provável do que improvável. Se uma contagem tem média λ, a probabilidade de ser zero é e^(−λ), que fica abaixo de metade exatamente quando λ = ln 2. Portanto, igualando o número esperado de coincidências a ln 2, bastam 10 janelas, ou seja, uma sequência de 12 símbolos. É o paradoxo dos aniversários, mas com 64 aniversários possíveis em vez de 365. Por isso, uma sequência de 50 símbolos repetir-se não é um sinal; é o mínimo que se deve esperar. Há, contudo, uma ressalva: janelas vizinhas partilham 2 dos seus 3 símbolos, portanto também não são as observações independentes pressupostas por ambos os cálculos. Na realidade, o ponto de equilíbrio surge aproximadamente um símbolo mais tarde.

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

Referências (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.

Pela equipa 42Math · Atualizado 2026-07-29

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Estatística e Finanças →

Problemas de exemplo

sequência curta - Sequência curta com janelas de 3 símbolos: as repetições ainda aparecem rapidamente.
sequência média - Uma sequência média mostra que motivos repetidos são normais por acaso.
déjà vu denso - Sequências mais longas com janelas maiores ainda geram agrupamentos de déjà vu.