Vi analyserar Jim Propps P - maskin, en enkel deterministisk process som simulerar en slumpmässig promenad på Z d till inom en konstant. Beviset för felet bundna bygger på flera uppskattningar i teorin om enkla slumpmässiga promenader och en del noggrann summering. Vi nämner tre spännande gissningar om teckenförändringar och enmodalitet av funktioner i den linjära spännvidden av {p(·, x) : x  på Z d }, där p(n, x) är sannolikheten att en promenad från ursprunget anländer vid x vid tidpunkten n. Betrakta följande maskin, som vi kallar P-maskinen efter dess avkomma, Jim Propp. Vi börjar med en uppsättning marker på "jämn" hörn av Z d, dvs de en jämn L 1 -avstånd från ursprunget. Vi märker av Z 2d = {0, 1,.., 2d − 1} de 2d riktningar av Z d. (Till exempel: Nord, Syd, Öst och Väst för d = 2.) På varje vertex v kommer det att finnas en "rotor" som kommer att ha en stat j  på Z 2d. Rotorernas initialtillstånd kan ställas in godtyckligt. Rotorerna fungerar enligt följande: när man matar ett chip, ändras en rotor till tillstånd j + 1 (addition i Z 2d ) och skickar chipet till vertex i riktning j. Varje gång matar vi alla chips på varje vertex till rotorn på vertex. Resultatet är en ny distribution av marker. Vi föreställer oss att göra denna operation för total tid n. Nu, överväga följande process. Vi börjar återigen med en uppsättning marker på "jämn" hörn av Z d. Varje chip tar en n-steg enkel slumpmässig promenad från sin utgångspunkt. Vid tiden n, förväntar vi oss att P - maskinen och slumpmässiga processen bör ge upphov till liknande distributioner om de börjar med samma konfiguration av marker. För den slumpmässiga gångprocessen kan vi överväga det förväntade antalet marker som kommer att vara vid v vid tidpunkten n. Vårt huvudresultat är att skillnaden mellan detta förväntade antal och det faktiska antalet vid v vid tidpunkten n i den deterministiska P - maskin avgränsas enhetligt - oberoende av hur mycket tid har gått, vad den ursprungliga chip distribution var, starttillstånden för rotorerna, eller ens valet av v! - Vad är det för fel på dig?
Cooper och Spencer REF studerade d-dimensionella rutnät diagram, visar en konstant gräns på skillnaden mellan antalet polletter vid en given nod v i rotorrouter modellen och det förväntade antalet polletter vid v i random-walk modellen.
Simulating a Random Walk with Constant Error
{'venue': 'Combinatorics, Probability & Computing', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}