📊 statistics

Hash-augmented adaptive multilevel splitting Monte Carlo algorithm for accurate estimation of two-sample permutation test p-values

Este artigo introduz um algoritmo de Monte Carlo de divisão multinível adaptativo aumentado por hash, implementado no pacote Python `hamstest`, para estimar com precisão p-valores arbitrariamente pequenos para testes de permutação de duas amostras com estatísticas complexas, ao mesmo tempo em que aborda desafios relacionados à discretização da distribuição e garante intervalos de confiança válidos.

Autores originais: Nikita Golikov, Vladimir Sukhov, Gennady Korotkevich, Alexey Sergushichev

Publicado 2026-07-15

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Nikita Golikov, Vladimir Sukhov, Gennady Korotkevich, Alexey Sergushichev

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você é um detetive tentando capturar um criminoso muito raro em uma cidade de milhões de habitantes. Você tem uma lista de suspeitos (seus dados) e quer saber: "Qual é a probabilidade de que este padrão específico de pistas tenha ocorrido apenas por pura sorte?" No mundo da estatística, isso é chamado de teste de permutação. Você embaralha as pistas milhões de vezes para ver com que frequência um padrão "sortudo" aparece.

Normalmente, se o padrão é comum, você pode simplesmente contar os embaralhamentos sortudos. Mas e se o padrão for tão raro que só acontece uma vez em um trilhão de tentativas? Isso é como procurar um grão de areia específico em uma praia do tamanho de um planeta. Se você tentar encontrar esse grão escolhendo grãos aleatoriamente um por um (o antigo método Monte Carlo), poderá passar a vida inteira escolhendo areia e ainda assim nunca encontrar esse grão específico. Você precisaria escolher $10^{10}$ grãos apenas para ter um palpite decente para uma probabilidade minúscula como $10^{-10}$ , o que é totalmente impraticável.

O Problema: O Elevador "Travado"

Os autores deste artigo perceberam que os métodos padrão batem em um muro quando lidam com essas probabilidades minúsculas, especialmente porque os "grãos de areia" (combinações de dados) não são todos únicos. Às vezes, milhares de embaralhamentos diferentes resultam na mesma pontuação exata. É como um elevador que só para nos andares 1, 10 e 100, mas pula do 2 ao 99. Ele ignora o 2 ao 99 porque não pode parar lá. Essa "discretização" faz com que a matemática trave, tornando impossível estimar o quão raro um evento realmente é.

A Solução: A "Tag" de Hash e a Escada de Divisão

A equipe, liderada por Nikita Golikov e colegas, construiu uma nova ferramenta chamada hamstest. O segredo deles é um truque inteligente chamado divisão multinível adaptativa com aumento de hash (hash-augmented adaptive multilevel splitting).

Veja como funciona, usando uma analogia divertida:

A Escada (Divisão Multinível): Em vez de tentar saltar diretamente para o topo da montanha (o evento raro), eles constroem uma escada. Eles começam na base e perguntam: "Quantas pessoas conseguem alcançar o primeiro degrau?" Depois, "Quantas dessas pessoas conseguem alcançar o segundo degrau?" Eles continuam dividindo o grupo em grupos cada vez menores conforme sobem. Isso transforma um salto impossível em uma série de passos fáceis e gerenciáveis.
A "Tag" de Hash (O Conserto para Elevadores Travados): O grande problema era que muitas pessoas estavam paradas no mesmo degrau (a mesma pontuação), tornando impossível dividir o grupo mais adiante. Para resolver isso, os autores deram a cada pessoa uma tag de hash única e invisível (um número aleatório). Mesmo que duas pessoas tenham exatamente a mesma pontuação, suas tags de hash são diferentes. Isso permite que o algoritmo diga: "Ok, não podemos dividir pela pontuação, mas podemos dividir pela tag de hash". Isso transforma um andar plano e travado em uma escadaria suave e contínua, onde o algoritmo sempre consegue encontrar o próximo degrau.

O Que Eles Descobriram (e o Que Não Descobriram)

Os autores testaram este novo método em dois testes estatísticos clássicos: o teste Kolmogorov–Smirnov e o teste Mann–Whitney U.

Os Resultados: Em suas simulações, o novo método foi incrivelmente preciso. Quando tentaram estimar probabilidades tão minúsculas quanto $10^{-243}$ (isso é um 1 seguido de 243 zeros!), a estimativa do método caiu exatamente sobre o valor real. Eles também calcularam intervalos de confiança (uma faixa onde a resposta verdadeira provavelmente está escondida) e, em cerca de 95% de suas execuções de teste, a resposta verdadeira estava dentro desse intervalo.
A Regra do "Reamostragem Total": Eles testaram algumas formas diferentes de executar a simulação. Descobriram que um método chamado "reamostragem total" (full resampling — onde eles embaralham todos os dados em cada etapa) é o mais confiável e robusto. Eles sugerem usar uma configuração específica chamada $\alpha = 1$ como o padrão, pois foi o que funcionou melhor em seus testes.
O Que Eles Descartaram: Eles mostraram explicitamente que a forma antiga de fazer as coisas (apenas usar a pontuação sem a tag de hash) falha quando os dados têm "grandes saltos" ou muitos empates. Eles provaram que, sem a tag de hash, o algoritmo pode travar e dar respostas erradas. Também observaram que, embora seu método funcione bem para testes unilaterais (procurando um padrão em uma direção), a versão bilateral do teste Kolmogorov–Smirnov é complicada porque o "elevador" pode ficar desconectado no topo, exigindo um tratamento especial.

Quão Rápido É?

A equipe mediu quanto tempo o algoritmo levou em um computador moderno (um Apple M3 Pro). Eles descobriram que o tempo que leva depende principalmente de quão raro é o evento. Se você estiver procurando por algo extremamente raro (como um p-valor de $10^{-100}$ ), leva mais tempo porque você tem que subir mais degraus na escada. No entanto, para o teste Mann–Whitney U, o tempo não dependeu muito do tamanho do conjunto de dados, porque a matemática para esse teste específico é muito eficiente para atualizações.

A Conclusão

Os autores não "resolveram" todos os problemas estatísticos do universo, mas construíram uma ferramenta muito poderosa e flexível que funciona para qualquer estatística de teste personalizada que um cientista possa inventar. Eles empacotaram essa ferramenta em uma biblioteca Python gratuita chamada hamstest.

Eles sugerem que, para a maioria das pessoas, usar o método de reamostragem total com $\alpha = 1$ é a melhor opção. Eles também apontam que, embora seu método seja rápido, o tempo exato que ele leva depende da matemática específica do teste que você está executando. Se você é um pesquisador lidando com probabilidades minúsculas e dados bagunçados, esta ferramenta sugere uma maneira de obter respostas precisas sem esperar pela morte térmica do universo.

Em resumo: Eles transformaram um elevador quebrado e travado em uma escada rolante suave e de alta velocidade que pode levar você ao topo da montanha estatística, mesmo quando o caminho está cheio de buracos.

Resumo Técnico: Divisão Multinível Adaptativa Aumentada por Hash para Valores-p de Testes de Permutação

Problema
Testes de permutação não paramétricos, como os testes de Kolmogorov–Smirnov e Mann–Whitney U, são fundamentais para testes de hipóteses estatísticas, particularmente ao comparar dois grupos sem assumir uma distribuição específica de dados. Embora o cálculo exato do valor-p seja o ideal, ele é frequentemente algoritmicamente intratável para estatísticas de teste complexas ou customizadas devido ao número exponencial de permutações possíveis ( $\binom{n+m}{n}$ ). Consequentemente, pesquisadores dependem da amostragem de Monte Carlo. No entanto, os métodos padrão de Monte Carlo sofrem de baixa precisão relativa ao estimar valores-p muito pequenos (ex: $10^{-10}$ ou menores), exigindo um número impraticável de amostras para alcançar poder estatístico após múltiplas correções de hipóteses.

Além disso, aplicar a divisão multinível (multilevel splitting) — uma técnica projetada para estimar probabilidades de eventos raros através da decomposição em um produto de probabilidades condicionais — a testes de permutação introduz desafios específicos. Os testes de permutação operam em espaços discretos onde a distribuição da estatística de teste frequentemente apresenta grandes saltos (discreticidade). Nesses casos, muitas combinações distintas de dados podem resultar em valores de estatística idênticos. Essa discreticidade pode impedir a seleção adaptativa de níveis intermediários necessária para a divisão multinível, fazendo com que o algoritmo falhe ou produza estimativas enviesadas quando a probabilidade condicional de mover-se para o próximo nível não pode ser mantida próxima de uma constante alvo (ex: 0,5).

Metodologia
Os autores propõem um algoritmo de Monte Carlo de divisão multinível adaptativa aumentada por hash para abordar os problemas de discreticidade inerentes aos testes de permutação. A metodologia central envolve três componentes principais:

Ordenação Aumentada por Hash: Para resolver o problema de múltiplas combinações compartilhando o mesmo valor de estatística, os autores introduzem uma ordem total estrita sobre as combinações. Em vez de ordenar apenas pela estatística do teste $S(A)$ , eles definem uma ordem $A \succ_{S,h} B$ baseada primeiro no valor da estatística e, em seguida, por um valor de hash $h(A)$ caso as estatísticas sejam iguais.
- A função de hash $h(A)$ mapeia combinações para inteiros. Uma implementação prática utiliza uma soma de inteiros independentes atribuídos a cada elemento, permitindo atualizações $O(1)$ durante as etapas de Cadeia de Markov Monte Carlo (MCMC).
- Este aumento efetivamente "suaviza" a distribuição discreta, garantindo que, para qualquer limite de nível, um próximo limite válido possa ser encontrado de modo que a probabilidade condicional permaneça estimável.
Divisão Multinível Adaptativa com MCMC: O algoritmo estima o valor-p $Pr(S \ge \gamma)$ decompondo-o em um produto de probabilidades condicionais sobre uma sequência de eventos aninhados definidos pela ordem aumentada por hash.
- Níveis Adaptativos: Partindo de um nível trivial, o algoritmo amostra combinações e utiliza seus quantis (ex: a mediana) para definir o próximo limite de nível.
- Amostragem MCMC: Para gerar amostras para o próximo nível, o algoritmo emprega um procedimento MCMC do tipo Metropolis. Ele parte de amostras existentes que satisfazem a nova condição de limite e as perturba (trocando elementos) para gerar novas amostras independentes.
- Estratégias de Reamostragem: O artigo avalia a "reamostragem total" (duplicando as amostras válidas existentes e perturbando todas elas) versus a "reamostragem parcial" (perturbando apenas um subconjunto). A reamostragem total mostrou-se mais robusta contra vieses de amostragem introduzidos pela natureza discreta do problema.
Estimativa em Espaço Logarítmico: O algoritmo estima o logaritmo do valor-p para lidar com valores extremos sem underflow numérico. Utiliza as funções digama ( $\psi$ ) e trigama ( $\psi_1$ ) para calcular a média e a variância das estimativas logarítmicas, derivadas das propriedades das estatísticas de ordem de distribuições uniformes. Isso permite a construção de intervalos de confiança válidos.

Principais Contribuições

Inovação Algorítmica: A introdução de um esquema de ordenação aumentada por hash que permite que a divisão multinível adaptativa funcione corretamente em espaços de permutação discretos, superando o problema de "grandes saltos" onde métodos padrão falham.
Implementação Robusta: Uma análise detalhada das estratégias de reamostragem (total vs. parcial) e dos critérios de parada de MCMC, demonstrando que a reamostragem total com um parâmetro de escala específico ( $\alpha=1$ ) fornece o melhor equilíbrio entre velocidade de convergência e redução de viés.
Lançamento de Software: O desenvolvimento e lançamento em código aberto do pacote Python hamstest, que implementa o algoritmo proposto. Ele permite que usuários definam estatísticas de teste customizadas e fornece interfaces eficientes (incluindo backends em C++) para estimativa de valor-p de alto desempenho.
Validação: Comparação rigorosa contra algoritmos exatos para os testes de Kolmogorov–Smirnov e Mann–Whitney U, demonstrando que o método proposto estima valores-p tão pequenos quanto $10^{-243}$ com intervalos de confiança válidos.

Resultados
Os autores avaliaram o algoritmo tanto em testes de Kolmogorov–Smirnov quanto de Mann–Whitney U através de vários tamanhos de amostra ( $n+m$ até 10.000) e valores-p alvo (até $10^{-100}$ ).

Precisão: Os valores-p estimados aproximaram-se dos valores reais (calculados via métodos exatos, onde disponíveis), sem viés visível. A mediana das estimativas alinhou-se com o valor-p real em todos os parâmetros testados.
Intervalos de Confiança: Os intervalos de confiança de 95% construídos (baseados em $\log \hat{p} \pm 2\hat{\sigma}$ ) capturaram com sucesso o log valor-p real na vasta maioria das execuções independentes, validando as estimativas teóricas de variância.
Desempenho: Os tempos de execução mostraram-se dependentes principalmente da magnitude do valor-p e do tamanho da amostra. O algoritmo demonstrou escalabilidade linear em relação ao número de níveis necessários, tornando-o viável para estimar valores-p extremamente pequenos que são computacionalmente proibitivos para o Monte Carlo padrão.
Comparação de Reamostragem: A variante "full-median" (reamostragem total com seleção de limite pela mediana) superou consistentemente as variantes de reamostragem parcial em termos de velocidade de convergência e robustez ao viés, particularmente para o teste de Kolmogorov–Smirnov, onde a discreticidade da distribuição é mais pronunciada.

Significância
O artigo afirma que este trabalho representa uma melhoria significativa em relação às abordagens clássicas de Monte Carlo para estimativa de valores-p em testes de permutação. Ao abordar as armadilias específicas de espaços discretos — nomeadamente a incapacidade de definir níveis intermediários devido a valores de estatística empatados — o algoritmo proposto permite a estimativa precisa e eficiente de valores-p arbitrariamente pequenos. Essa capacidade é crítica para aplicações de alto rendimento modernas (ex: genômica, neurociência), onde milhares de testes são realizados simultaneamente e o controle preciso das taxas de falsa descoberta exige uma estimativa confiável das probabilidades de cauda. Os autores observam que uma versão anterior deste algoritmo (sem o aumento por hash) já era bem-sucedida na Análise de Enriquecimento de Conjuntos de Genes (GSEA); o presente trabalho estende essa utilidade para uma classe mais ampla de estatísticas de duas amostras e resolve os problemas de instabilidade encontrados com distribuições de entrada específicas. A disponibilidade do pacote hamstest garante que essas capacidades estatísticas avançadas estejam acessíveis para estatísticas definidas pelo usuário em fluxos de trabalho de pesquisa práticos.

O Problema: O Elevador "Travado"

A Solução: A "Tag" de Hash e a Escada de Divisão

O Que Eles Descobriram (e o Que Não Descobriram)

Quão Rápido É?

A Conclusão

Mais como este