Tänk på en graf med en uppsättning hörn och orienterade kanter som förbinder par hörn. Varje vertex är associerad med en slumpmässig variabel och dessa antas vara oberoende. I denna inställning, anta att vi vill lösa följande hypotes testning problem: under null, de slumpmässiga variablerna har gemensam fördelning N (0, 1) medan under alternativet, det finns en okänd väg längs vilken slumpmässiga variabler har distribution N (μ, 1), μ > 0, och distribution N (0, 1) bort från det. För vilka värden av medelvärdet skift μ kan man på ett tillförlitligt sätt upptäcka och för vilka värden är detta omöjligt? Detta papper utvecklar detektionströsklar för två typer av gemensamma grafer som uppvisar ett annat beteende. Den första är den vanliga vanliga vanliga lattice med hörn av formen {(i, j) : 0 ≤ i, − i ≤ j ≤ i och j har paritet av i} och orienterade kanter (i, j) → (i+1, j +s) där s = ±1. Vi visar att för stigar av längd m börjar vid ursprunget, hypoteserna blir särskiljande (i en minimax mening) om μ m  på log m, medan de inte är om μ m  på log m. Vi härleder likvärdiga resultat i en Bayesian inställning där man antar att alla stigar är lika troligt; där den asymptotiska tröskeln är μ m  och m −1/4. Vi får motsvarande resultat för träd (där tröskeln är av ordning 1 och oberoende av storleken på trädet), för andra fördelningar än Gaussian, och för andra grafer. Begreppet förutsägbarhetsprofil, som först introducerades av Benjamini, Pemantle och Peres, spelar en avgörande roll i vår analys. Nyckelord. Upptäcka en kedja av noder i ett nätverk, minimax detektion, Bayesian detektion, förutsägbar profil av en stokastisk process, martingales, exponentiella familjer av slumpmässiga variabler.
I REF, en okänd väg som motsvarar icke-noll medelvariabler måste upptäckas av noll medelvariabler i ett nätverk med noder anslutna i en graf.
Searching for a Trail of Evidence in a Maze
{'venue': 'Annals of Statistics 2008, Vol. 36, No. 4, 1726-1757', 'journal': None, 'mag_field_of_study': ['Mathematics']}