Random promenader på avgränsade grad expander grafer har många tillämpningar, både i teoretiska och praktiska beräkningsproblem. En viktig egenskap hos dessa promenader är att de snabbt konvergerar till sin stationära fördelning. I detta arbete definierar vi hög ordning slumpmässiga promenader: Dessa är generaliseringar av slumpmässiga promenader på grafer till högdimensionella simplial komplex, som är de högdimensionella analogerna av grafer. Ett simplial komplex av dimension d har hörn, kanter, trianglar, pyramider, upp till d-dimensionella celler. För alla 0 ≤ i < d, en slumpmässig höggradig gång på dimension i rör sig mellan angränsande i-ansikten (t.ex., kanter) av komplexet, där två ifaces anses grannar om de delar en gemensam (i + 1)-ansikte (t.ex. en triangel). Fallet i = 0 återvinner den väl studerade slumpmässiga vandringen på grafer. Vi tillhandahåller ett lokalt till globalt kriterium på ett komplex som innebär en snabb konvergens av alla slumpmässiga övergångar på hög nivå. Specifikt bevisar vi att om de 1-dimensionella skeletten i alla länkar av ett komplex är spektralexpanders, då för alla 0 ≤ i < d den höga ordningen slumpmässiga gå på dimension i konvergerar snabbt till dess stationära fördelning. Vi härleder vårt resultat genom en ny uppfattning om högdimensionell kombinatorisk expansion av komplex som vi kallar färgstark expansion. Detta begrepp är en naturlig generalisering av kombinatorisk expansion av grafer och är starkt relaterad till konvergensen av den höga ordningen slumpmässiga promenader. Vi visar också en tydlig familj av avgränsade gradkomplex som uppfyller detta kriterium. Specifikt, vi visar att Ramanujan komplex uppfyller detta kriterium, och därmed bilda en explicit familj av avgränsad grad högdimensionella simplicial komplex där alla den höga ordningen slumpmässiga promenader snabbt konvergerar till deras stationära fördelning.
Begreppet en slumpmässig gång på grafer generaliserades till simplial komplex i arbetet av Kaufman och Mass REF till "uppifrån" och "ned-upp" slumpmässiga promenader, vars tillstånd är k-faces av en simplial komplex.
High Dimensional Random Walks and Colorful Expansion
{'venue': 'ITCS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}