View
105
Download
2
Category
Preview:
Citation preview
Deterministic Random Walks
Tobias Friedrich
Max-Planck-Institut für Informatik Saarbrücken
Friedrich-Schiller-Universität Jena
Tobias Friedrich
Random Walk vs. Propp Machine
Ein-Knoten-Diskrepanz
Aggregating Model
Übersicht
= Theorie
= Praxis/Anwendung
Tobias Friedrich
RandomWalk auf Z2
Tobias Friedrich
Zusätzlich Zeiger an jeder Position:
Propp Machine
Tobias Friedrich
Propp Machine
Tobias Friedrich
Propp Machine Detailansicht:
1.
2.
3.
4.
(";! ;#;Ã )Kreisförmige Rotor Sequence
(";! ;#;(";! ;(";
Tobias Friedrich
Propp Machine Detailansicht:
1.
2.
4.
3.
(";! ;Ã ;#)(";(";! ;(";! ;Ã ;Nicht-Kreisförmige Rotor Sequence
Tobias Friedrich
Fragestellung
Wie gut beschreibt die Propp Machine einen Random Walk?
Tobias Friedrich
Voraussetzung 1 Anfangskonfiguration hat Chips nur auf einer Parität
Tobias Friedrich
(1,0)
(0,1)
(0,-1)
(0,0)(-1,0)
Angepaßtes Koordinatensystem
Voraussetzung 2
Tobias Friedrich
(1,1)(-1,1)
(-1,-1) (1,-1)
(0,0)
Angepaßtes Koordinatensystem
Voraussetzung 2
Tobias Friedrich
Für feste Anfangskonfiguration
Notation
rw(x;t) := erwartete Anzahl Chips an Position xnach t zufÄalligen Schritten
pr opp(x;t) := Anzahl Chips an Position xnach t Propp Schritten
[ Rechnung siehe Tafel ]
H (x;t) := WSK, dass Chip von x in t zufÄalligenSchritten am Ursprung ankommt
Weitere Notation
Tobias Friedrich
Bekannte Ergebnisse
Cooper und Spencer [1]:
Cooper, Spencer, Doerr, Tardos [2]:
maxx2Zd
maxt¸ 0
¡pr opp(x;t) ¡ rw(x;t)
¢· cd
maxx2Z1
maxt¸ 0
¡pr opp(x;t) ¡ rw(x;t)
¢¼2:29
[1] Joshua Cooper, Joel Spencer: “Simulating a random walk with constant error.”Zu erscheinen in “Combinatorics, Probability and Computing”
[2] Joshua Cooper, Benjamin Doerr, Joel Spencer, Gábor Tardos: “Deterministic random walks on the integers”.Zu erscheinen in “European Journal of Combinatorics”
Tobias Friedrich
Unser Ergebnis
maxx2Z2
maxt¸ 0
jpr opp(x;t) ¡ rw(x;t)j Auf dem zwei-dimensionalen Gitter Z2
¼
(7:83 fÄur kreisfÄormige Rotor Sequences
7:28 fÄur nicht-kreisfÄormige R.S.
Tobias Friedrich
Intuition
Propp Machine
Wir wollen pr opp(0;t) ¡ rw(0;t) maximieren
Tobias Friedrich
Intuition
14141414
14141414
14141414
14141414
14
12
14
14
12
14
12
12
Random WalkPropp Machine
Das ergibt pr opp(0;2) ¡ rw(0;2) = 4¡ 1= 3.
Tobias Friedrich
Ein einfaches Beispiel
pr opp(0;t) ¡ rw(0;t)¼6:68.
Tobias Friedrich
Ein besseres Beispiel
pr opp(0;t) ¡ rw(0;t)¼7:77.
fÄur (%;& ;. ;- )
nur erlaubt falls - und. in Rotor Sequenceaufeinanderfolgend sind
Tobias Friedrich
pr opp(0;t) ¡ rw(0;t)¼7:22.
Ein besseres BeispielfÄur (%;- ;& ;. )
Tobias Friedrich
Obere Schranke
Satz: Diskrepanz kann nach oben abgeschätzt werden durch die Summe der worst-case Beiträge aller Positionen:
jpr opp(0;t) ¡ rw(0;t)j ·X
x2Z2
con(x)
Tobias Friedrich
Pfeil = Chip in diese Richtung geschickt zu bestimmter Zeit
Pfeillänge = Beitrag dieses Chips
Roter Pfeil = negativer Beitrag
Worst-case fÄur (%;- ;. ;& )
Tobias Friedrich
Worst-case KonfigurationenKreisfÄormige Rotor Sequence
(%;- ; . ;& )Nicht-kreisfÄormige Rotor Seq.
(%;- ;& ;. )
Tobias Friedrich
103 ¢con(x)
BeitrÄage verschiedener xKreisfÄormige Rotor Sequence
(%;- ; . ;& )Nicht-kreisfÄormige Rotor Seq.
(%;- ;& ;. )
Tobias Friedrich
Beweise
Berechne
X
kxk1 >800
con(x) · 0:16
ObereSchranke
X
kxk1 · 800
con(x) ¼
(7:83 fÄur kreisfÄormige R.S.
7:28 for nicht-kreisfÄormige R.S.
Tobias Friedrich
Untere Schranke
Untere Schranke = obere Schranke !!
Worst-case Konfigurationen sind konstruierbar
Arrow-forcing Theorem:FÄur jedes ar r : (x;t) ! f%;& ;. ; - g gibtes eine Anfangskon̄ guration, so da¼dasresultierende Spiel gerade Zeiger ar r (x;t) hat.
Tobias Friedrich
Zusammenfassung Theorieteil
Ergebnisse für die 2D Propp Machine:
Diskrepanz 7.83/7.28 für kreisförmige/nicht-kreisförmige Rotor Sequences (scharf!)
Erster Beweis, daß die Reihenfolge in der die Nachbarn bedient werden überhaupt einen Einfluß hat
Genaue Charakterisierung der Worst-cases
Tobias Friedrich
Offene Fragen
Welche Graphen haben „Propp-Eigenschaft“?
Was ist mit durchschnittlicher Diskrepanz? Was passiert auf Intervallen von Zeit/Ort? ...
Tobias Friedrich
Aggregating Model
Diffusion Limited Aggregation:
Beschreibt Schneeflocken, Korallen, Blitze, Kristalle, Nebel, Rauch, …
Tobias Friedrich
Aggregating Model
Random Walk von 100 Chips:
Tobias Friedrich
Aggregating Model
Random Walk von 1600 Chips:
Tobias Friedrich
Aggregating Model
Random Walk von 25600 Chips:
Tobias Friedrich
Aggregating Random Walk
Differenz Inkreis/Umkreisradius mit hoher Wahrscheinlichkeit O(n1/3)
Experimentell anscheinend O(log n)
Tobias Friedrich
Aggregating Propp Machine
Tobias Friedrich
Aggregating Propp Machine
Konvergiert gegen Kreis Experimentell anscheinend konstant(!!)
Tobias Friedrich
Aggregating Propp Machine
#Ã ! "
Danke!
#Ã "!
#! Ã " #! "Ã
0.92
0.92
1.61
1.61
#"Ã !1.85
#"! Ã1.85
Recommended