Sparse Rekonstruktion in Spinsystemen. I: iid Spins

Zusammenfassung: Für eine Sequenz von Booleschen Funktionen fₙ: \{ - 1, 1\ ^{Vₙ}} \ - 1, 1\ f n: − 1, 1 V n → − 1, 1, die auf wachsenden Konfigurationsräumen zufälliger Eingaben definiert sind, sagen wir, dass eine spärliche Rekonstruktion vorliegt, wenn es eine Sequenz von Teilmengen U n ⊆ V n der Koordinaten gibt, die ∣ U n ∣ = o (∣ V n ∣) erfüllen, sodass das Wissen um die Koordinaten in U n uns eine nicht verschwindende Menge an Informationen über den Wert von f n gibt. Zunächst zeigen wir, dass, wenn das zugrunde liegende Maß ein Produktmaß ist, keine spärliche Rekonstruktion für beliebige Sequenzen von transitiven Funktionen möglich ist. Wir diskutieren die Frage in verschiedenen Rahmen, messen den Informationsgehalt in L 2 und mit Entropie. Zudem heben wir einige interessante Verbindungen zur kooperativen Spieltheorie hervor. Über transitive Funktionen hinaus zeigen wir, dass das links-rechts Überkreuz-Ereignis für kritische planare Perkolation auf dem quadratischen Gitter ebenfalls keine spärliche Rekonstruktion zulässt. Einige dieser Ergebnisse beantworten Fragen, die von Itai Benjamini aufgeworfen wurden.