Buscando uma trilha de evidências em um labirinto

Considere um grafo com um conjunto de vértices e arestas orientadas conectando pares de vértices. Cada vértice está associado a uma variável aleatória e assume-se que estas são independentes. Nesse contexto, suponha que desejamos resolver o seguinte problema de teste de hipótese: sob a hipótese nula, as variáveis aleatórias têm uma distribuição comum N (0, 1), enquanto sob a alternativa, existe um caminho desconhecido ao longo do qual as variáveis aleatórias têm uma distribuição N (μ, 1), μ > 0, e uma distribuição N (0, 1) longe dele. Para quais valores do desvio médio μ pode-se detectar de forma confiável e para quais valores isso é impossível? Considere, por exemplo, a rede regular usual com vértices da forma (i, j): 0≤i, −i≤j≤i e j com a paridade de i e arestas orientadas (i, j) → (i+1, j+s), onde s=±1. Mostramos que para caminhos de comprimento m começando na origem, as hipóteses tornam-se distinguíveis (em um sentido minimax) se μ = 1/m, enquanto não são se μm≪1/log m. Derivamos resultados equivalentes em um contexto Bayesiano onde se assume que todos os caminhos têm a mesma probabilidade; lá, o limite assintótico é μm≈m−1/4. Obtivemos resultados correspondentes para árvores (onde o limite é da ordem de 1 e independente do tamanho da árvore), para distribuições diferentes da gaussiana e para outros grafos. O conceito de perfil de previsibilidade, introduzido pela primeira vez por Benjamini, Pemantle e Peres, desempenha um papel crucial em nossa análise.