Przesuwamy losowo slipy w wielu wymiarach i słuchamy muzyki

Przestrzenią euklidesową wymiaru n nazywamy zbiór ciągów liczbowych o długości n. Jest to po prostu wspólne określenie dla prostej, płaszczczyzny, "naszej" przestrzeni, i przestrzeni o wyższym skończonym wymiarze (ludzie lubiący mocne słowa mówią: hiperprzestrzeni). Podobnie - wygodnie jest używać jednego słowa "miara" na wspólne określanie długości, pola, objętości figur czy kształtów na prostej, płaszczyźnie, przestrzeni. Wyższy wymiar - możemy mówić o hiperobjętości, ale po co, poza tym to brzydko. "Miara" wystarczy.

Kratą całkowitą nazywamy zbiór punktów o współrzędnych całkowitych. Na płaszczyźnie, pokratkowanej jak w zeszycie do rachunków, kratę całkowitą stanowią punkty przecięcia linii, czyli wierzchołki kwadratów. Przyjmujemy długość jednostkową boku.

W notce andsola "Nie wstrząsać się przed użyciem" pojawiło się proste zadanie (zwane też lematem Minkowskiego), moimi słowami:

Dowolną figurę o mierze mniejszej niż 1 można przesunąć tak, by nie zawierała żadnego wierzchołka kraty całkowitej.

Przez figurę rozumiemy taki podzbiór przestrzeni euklidesowej, któremu można przypisać miarę, np. pole powierzchni - figurze płaskiej, objętość- bryle, etc.

Komentarze u andsola pokazują ewolucję początkowego nierozumienia i niemożności rozwiązania tego zadania, nawet w przypadku płaszczyzny, przechodzących w powolne bądź nagłe rozumienie. W nierozumieniu byłem pierwszy, ale też w końcu zrozumiałem... w czym byłem ostatni. Postanowiłem zapisać rozwiązanie w miarę rygorystycznie, przy tym cieszy mnie rozwiązanie probabilistyczne. Pojawi się ono pod koniec niniejszej notki, oddzielone baraszkami na temat figur i kształtów.

Zostańmy przez czas jakiś na płaszczyźnie, gdyż jest najbardziej naturalną...hm... jak by tu powiedzieć... a niech tam! - najbardziej naturalną płaszczyzną ludzkiej percepcji.

Gdy mówię o "dowolnej figurze", zapraszam najbardziej skomplikowane, wychodzące poza podstawowe prostokąty lub trójkąty. Zresztą, i z nich można poukładać skomplikowane figury, jak słynne chińskie Tangramy.

Jeżeli wydają sie wciąż proste - proszę bardzo, oto japońska kaligrafia, wykonana przez współczesnego artystę (bagatela, 25 tys ¥, czyli circa $250). Inskrypcja głosi w wolnej transkrypcji:

"Nawet najmniejsza drobina pyłu kosmicznego zawiera cały szeroki świat."

Można poprosić dziecko, gdy kto ma pod ręką, by wykonało "kształt" za darmo, a już na pewno za cukierka, a nawet za pochwałę (samo pozwolenie mazania farbą po białej ścianie jest wystarczającą nagrodą).

Tak, pole powinno być wyliczalne, ale nie ma co się tym przejmować, w tym zadaniu to nieważne - wystarczy przyjąć, że "jakoś pole można przypisać, zmierzyć, wyliczyć".

No, czas na dowód (niezależny od wymiaru). Jego konstrukcja przypomina strukturę Bolero Ravela.

Wprowadźmy najpierw indykator zbioru lub zdania logicznego:

$[;1\hspace{-3pt} {\rm I}_A(x),\mbox{ lub } 1\hspace{-3pt} {\rm I}_{\{...\}};]$

Przyjmuje on wartość 1, gdy x jest elementem A lub gdy zdanie {...} jest prawdziwie, wartość zero - w przeciwnym razie. Zapewniam - baaardzo wygodne. Na przykład, dzięki niemu łatwo zbudować "licznik". Niech A będzie figurą w naszej przestrzeni - powiedzmy d-wymiarowej, zaś n niech przebiega kratę całkowitą (mamy n=(n₁,...,n_d ) , lecz to nie takie ważne)

$[;L(A)=\displaystyle \sum_n 1\hspace{-3pt} {\rm I}_A(n);]$

Idziemy sobie z tym n, idziemy - i jak tylko trafi ten wierzchołek w zbiór A, licznik zwiększa się o 1. Jak nie trafi - bez zmian. No, licznik liczy.

Wprowadźmy teraz przesunięcie figury o wektor x=(x₁,...,x_d ):

$[;A+x=\{a+x\,:\,a\in A\};]$

Zauważmy, jak ładnie przesunięcie współpracuje z operacjami mnogościowymi, np. iloczynem:

$[;(A\cap B) +x=(A+x)\cap (B+x);]$

Czy najpierw przeciąć dwa zbiory, a potem przesunąć; czy najpierw przesunać, a potem przeciąć - na jedno wychodzi. Stąd (małe ćwiczenie):

$[; A\cap (B+x)=[(A-x)\cap B]+x ;]$

Wprowadzamy następny element zabawy - oznaczenie miary, po prostu |A|, np. pole na płaszczyźnie lub objętość w przestrzeni 3D. Ponieważ miara figury przesuniętej nie zmienia się, więc powyższe pociąga wzorek, prawdziwy dla dowolnych figur A, B:

$[; |A\cap (B+x)|=[|(A-x)\cap B|\hspace{2in} (*) ;]$

Ha! Pozbyliśmy się jednego x ! Ustalmy naszą figurę (w oryginale - vide link u andsola - była nazwana slip - rodzaj bielizny, którą można ściągać i w górę, i w dół). Dajmy jej więc S na imię. Niech jej miara |S|<1. Badamy licznik tego (lub tej) S, przesuniętego o x, oznaczając

$[;N(x)=L(S-x)=\displaystyle \sum_n 1\hspace{-3pt} {\rm I}_{S-x}(n)=\sum_n 1\hspace{-3pt} {\rm I}_{S-n}(x);]$

(jeżeli to niejasne - rozpiszmy znaczenie indykatora, zdanie brzmi "n∈ S-x", co znaczy dokładnie "x∈ S-n" - ta sama treść, nieco inny wygląd). Zatem, wartością funkcji N(x) jest liczba wierzchołków kraty, która znajduje się w S. Może być nawet i nieskończona, gdy figura jest nieograniczona. Jak kogo to niepokoi, niech o takich figurach zapomni - nieważne tutaj.

Teza zadania - lemat Minkowskiego - mówi, że dla co najmniej jednego przesunięcia x, N(x)=0.

Czas na następny instrument - zmienne losowe o wartościach w naszej przestrzeni. Ano, mamy teraz X, tylko nie ustalone x, lecz losowe przesunięcie. Jak nałożymy indykator, powstaje prościutka zmienna losowa o wartościach 1 i 0 (zwą ją zmienną Bernoulliego, ale to nieważne). Jak zmienna losowa - to i prawdopodobieństwo P, i ekspektancja E.

Tak, czytelniku i czytelniczko - nie lubię określenia "wartość oczekiwana", bo niby na co i po co miałby kto oczekiwać? Ekspektancja brzmi ładnie, kojarzy się z Salamanką, Kalifornią, flamenco i elegancją, oraz innymi przyjemnymi miejscami i rzeczami. Ekspektancja elegancko współpracuje z indykatorem:

$[;E 1\hspace{-3pt} {\rm I}_A (X)= P(X\in A);]$

(Dlaczego? Bo to masło maślane). Zatem,

$[;E N(X)=\displaystyle\sum_n P(X\in S-n) \hspace{2in} (**);]$

Gdyby lemat Minkowskiego był fałszywy, to by zawsze E N(X)≥ 1. Zatem, by ów udowodnić, wystarczy znaleźć jedną nawet głupią zmienną losową byle taką, by E N(X)<1. Wtedy z dodatnim prawdopodobieństwem N(X)<1, a ponieważ licznik dostarcza tylko liczby całe, więc N(X)=0. Gdy zmienna losowa ma rozkład ciągły - nie tylko jedno, ale nieskończenie wiele przesunieć się znajdzie by uniknąć wierzchołków.

Że to przesada, że by jedno znaleźć - trzeba nieskończoności? Nie "trzeba", ale wystarcza. Zresztą, czy nie tak robimy na codzień? Mamy ochotę strzelić maluszka - kupujemy pół litra. Chcemy jabłko - o, cała torba trafia do domu. Potrzebujemy gwoździka by przybić obrazek - najmniejsze opakowanie to kilo gwoździ... (nie zawsze da się pożyczyć od sąsiadki).

Najprostsza zmienna losowa, która przychodzi do głowy, ma rozkład jednostajny na jakimś przedzialiku jednostkowym o końcach z kraty, nazwijmy go U. Jak ten rozkład jednostajny pracuje? Bardzo prosto... no, jednostajnie:

$[;P(X\in A)=|U\cap A|;]$

Zatem (**) a zaraz potem (*) prowadzą do

$[;E N(X)=\displaystyle\sum_n | U\cap (S-n)|= \sum_n | (U+n)\cap S| ;]$

A teraz... grand finale! Zauważamy, że wszystkie przesunięcia U+n są rozłączne, i wypełniają całą przestrzeń (dajmy jej na imię Ω - a co!), stąd (suma miar równa jest mierze sumy)

$[;E N(X)=\displaystyle sum_n | (U+n)\cap S|=|\Omega\cap S|=|S|<1 ;]$