QUANDO O EMBARALHAMENTO POR CIMA ESQUECE O BARALHO?

Embaralhar cartas é uma versão concreta de uma questão básica da probabilidade: quanto tempo um processo aleatório leva para esquecer de onde partiu? Um baralho recém-aberto está em ordem. Cada embaralhada o bagunça um pouco mais, até que nenhum vestígio da ordem original possa ser detectado.

Os matemáticos distinguem dois níveis de resposta. O tempo de mistura dá a ordem de grandeza. Um cutoff (corte abrupto) diz muito mais: em torno de um momento preciso, o baralho passa de “claramente não misturado” a “completamente misturado” quase de uma vez. Embaralhe um pouco menos que isso e ainda dá para perceber; um pouco mais, e já não dá.

O embaralhamento, visto por um matemático

No embaralhamento por cima, você segura o baralho numa mão e deixa cair pequenos montes de cartas na outra. O artigo o modela assim: cada um dos n − 1 intervalos entre cartas vizinhas é cortado de forma independente com probabilidade p, e a ordem dos montes resultantes é invertida. Uma passada completa pelo baralho conta como uma embaralhada.

Segundo o artigo, trabalhos anteriores já haviam determinado a ordem de grandeza. Pemantle situou o tempo de mistura entre n² e n² log n; Jonasson mostrou depois que n² log n é a ordem certa. Mas a constante exata, e a própria existência de um cutoff nítido, continuavam em aberto: Diaconis e Pal listaram o cutoff do embaralhamento por cima como problema em aberto em 2022.

O resultado

Yunjiang Jiang prova que o cutoff existe e o localiza.

Teorema. Para uma probabilidade de corte p fixa, o embaralhamento por cima mistura, em primeira ordem, em

p² / (2(1 − p)π²) × n² log n

embaralhadas. Um pouco antes, o baralho continua longe do aleatório; um pouco depois, está perto do aleatório.

Para p = 1/2 — um corte em metade dos intervalos, em média — a fórmula se torna n² log n / (4π²).

Como a prova funciona

A prova tem três partes independentes.

1. O limite inferior acompanha uma única carta. Sua posição evolui de um jeito notavelmente limpo: padrões exatos em forma de cosseno decaem a uma taxa conhecida, mesmo para um baralho finito. Somados sobre o baralho todo, eles guardam um vestígio detectável da ordem inicial até o momento previsto.
2. O limite superior compara dois baralhos que diferem apenas pela troca de duas cartas. Com os mesmos cortes aleatórios, a diferença se comporta como duas posições marcadas que vagueiam pelo baralho até se tornarem vizinhas e poderem se fundir. A taxa com que isso acontece coincide com o limite inferior.
3. Uma desigualdade estática sobre permutações, sem relação com o embaralhamento, transforma essa comparação numa afirmação sobre o baralho inteiro. É a parte mais técnica do artigo, construída por recursão sobre tabelas que contam como as cartas se distribuem entre blocos.

O artigo também prova um cutoff para outra medida de desordem, a entropia relativa, sem determinar sua localização exata.

O que a fórmula diz sobre um baralho de verdade

Aplicar a fórmula a um baralho de 52 cartas com p = 1/2 dá 52² × ln 52 / (4π²), cerca de 270 embaralhadas. Essa conta é nossa, não um número do artigo, e deve ser lida como uma indicação aproximada: o teorema descreve o comportamento de baralhos muito grandes, e o termo de correção não é quantificado. Para comparação, o artigo cita a escala de (3/2) log₂ n estabelecida por Bayer e Diaconis para o embaralhamento americano (riffle shuffle) — cerca de 8,6 para 52 cartas, com a mesma ressalva. A distância entre n² log n e log n é o que torna o embaralhamento por cima tão lento.

Primeira ordem, mãos idealizadas

O resultado é de primeira ordem: não dá a largura da janela de transição nem sua forma exata. A probabilidade de corte é mantida fixa, e os cortes são supostos independentes, uma idealização das mãos reais. Numa nota de rodapé, o autor afirma que o sistema de IA GPT-6 Astra foi “usado no desenvolvimento de argumentos, na verificação de cálculos e na preparação da exposição” e que o autor é responsável pelo conteúdo matemático. O artigo é um preprint.