https://xpil.eu/zcl 📋

Ktoś kiedyś postawił sobie następujące pytanie:

Jakiej długości jest najkrótsza sekwencja bitów, której nigdy nie przesłano przez Internet?

Pytanie wydaje się na pierwszy rzut oka nieco dziwne, ale już na drugi i trzeci - o ile ktoś ma tyle oczu - niekoniecznie.

No bo w końcu Internet nie jest nieskończenie wielki, prawda? Zatem musi istnieć taka sekwencja, której przezeń nigdy nie przesłano, można więc pokusić się o wyliczenie jej długości.

Tylko gdzie zacząć?

Jako osobnik pragmatyczny chętnie nadgryzłbym temat doświadczalnie. Jednak w przypadku Internetu, który - chociaż nie nieskończony - jest jednak cholernie duży, podejście eksperymentalne może się nie udać. Trzeba by wykonać kopię całej Sieci (obecnej i historycznej - najlepiej z serwerów NSA) na jakąś dyskietkę (czym większą, tym lepiej) i potem pracowicie przeszukiwać coraz to większe podciągi.

Odpada, bo w tym czasie Internet zdąży urosnąć i trzeba będzie zaczynać apiat' od nowa, tylko z większą dyskietką.

Skoro nie da się doświadczalnie, trzeba się zabrać do rzeczy statystycznie i teoretycznie.

Ale gdzie zacząć?

Zaczniemy sobie od przeformułowania pytania wyjściowego. Spróbujemy sobie odpowiedzieć na pytanie następujące:

Jaka jest długość najkrótszej sekwencji bitów, której nigdy nie przetransmitowano przez Internet, z prawdopodobieństwem co najmniej 50%?

Czemu tak?

A no temu, że skoro nie możemy zbadać własnoręcznie każdej sekwencji i musimy odwołać się do metod probabilistycznych, nie możemy odpowiedzieć na oryginalne pytanie ze stuprocentową pewnością, a więc musimy sobie ustalić jakiś próg. 50% jest równie dobre jak cokolwiek innego.

Kolejna sprawa: żeby się boksować z przeciwnikiem, warto chociaż wiedzieć do jakiej należy on kategorii wagowej. W tym przypadku: ile właściwie waży Internet, w bajtach?

Tu w sukurs przychodzi nam Wikipedia, która mówi, że od 1990 roku ludzkość przesłała przez Sieć łącznie około 4.25 zetabajtów danych (zetabajt to tysiąc eksabajtów czyli milion petabajtów)

No dobra. Znamy wagę przeciwnika na ringu (megasuperhiperurwałciężka), spróbujmy go teraz zaatakować.

Ale z głową.

Po pierwsze zauważmy, że chociaż ruch internetowy nie jest losowy (mnóstwo informacji się w nim powtarza, na przykład adresy www, standardowe nagłówki ramek TCP/IP i tak dalej), to jednak stale rosnąca obecność szyfrowania sprawia, że jest on *prawie* losowy (jak wiadomo informacje zaszyfrowane są nie do odróżnienia od losowych, przy braku kluczy deszyfrujących). To samo zresztą dotyczy multimediów: kompresja audio i wideo sprawia, że nawet niezaszyfrowane pliki multimedialne w większości przypadków - nie licząc nagłówków - wyglądają jak losowe ciągi danych. A więc możemy uprościć, bez zbyt wielkiego przekłamania, że ruch w Sieci *jest* losowy, a więc każda sekwencja bitów jest jednakowo prawdopodobna.

Po drugie możemy całkiem bezpiecznie oszacować granice (górną i dolną) odpowiedzi.

Granica górna:

• 128-bitowe wartosci UUID (zwane też GUID) są globalnie *prawie* unikalne (zapewnia to algorytm tworzenia UUID)
• Prawdopodobieństwo kolizji w zbiorze stu bilionów UUID-ów wynosi zaledwie 0.000000001 (jedna miliardowa).

Granica dolna:

• 32-bitowe systemy CRC wyszły z użycia już dość dawno, ze względu na ogromne ilości kolizji.
• 48-bitowe też.

Szukamy więc wartości między 48 a 128.

To już coś! Nie za wiele, ale - jak mawiają słuchacze niektórych stacji radiowych - lepszy rydz niż nic...

Jeżeli uznamy opisaną wyżej losowość poszczególnych bitów Internetu, to mamy następującą sytuację:

Wiaderko 4.25 zetabajtów losowych danych (czyli ciut ponad \(3.4*10^{22}\) bitów), dla którego mamy znaleźć maksymalne n takie, że wszystkie możliwe podciągi n-bitowe są w wiaderku. Na chłopski rozum zaczynamy od ciągów 49-bitowych. Jeżeli różnych kombinacji jest \(2^{49}\), szukamy podciągów 50-bitowych i tak dalej, aż dla pewnego n okaże się, że ilość istniejących różnych podciągów n-bitowych wynosi mniej, niż \(2^n\).

Strasznie mrówcza praca! Odpada. Trzeba skrótem.

Ciąg zer i jedynek możemy sobie na chwilę przedstawić w głowie jako ciąg rzutów dobrze wyważoną monetą. Orzeł - zero, reszka - jedynka.

No chyba, że rzucamy dwueurówką, wtedy obrazki będą inne...

Czego właściwie szukamy?

Szukamy pewnej sekwencji zer i jedynek, o długości X, która prawdopodobnie NIE pojawia się wśród naszych trzydziestu czterech hakiem tryliardów bitów.

Niniejszy link podaje przepis na wyliczenie oczekiwanej liczby rzutów monetą, po której wyrzucimy ciąg samych reszek o zadanej długości N, z prawdopodobieństwem 50%. Liczba ta wynosi \(X = 2^{N+1}-2\). Tyle razy trzeba, średnio, rzucić monetą, żeby wśród wyników pojawił się - z prawdopodobieństwem 0.5 - ciąg N reszek bez orła.

Czyli po naszemu ciąg samych jedynek.

Zauważmy jednak, że nie musimy ograniczać się do ciągu samych jedynek - skoro bowiem *każda* sekwencja jest jednakowo prawdopodobna, również nasza nieistniejąca sekwencja podlega temu wzorowi.

Uwaga: powyższe stwierdzenie może wywołać wewnętrzny sprzeciw (i zazwyczaj to właśnie robi, przynajmniej w przypadku osób słabo orientujących się w statystyce). Jak to, każda sekwencja jest jednakowo prawdopodobna?? Owszem, tak właśnie jest. Szansa, że w totolotku wypadną liczby 1,2,3,4,5,6 jest taka sama jak ta, że wypadną 4, 7, 15, 18, 32, 41. Jeżeli się z tym nie zgadzasz, nie czytaj dalej tylko sięgnij po opinię osób trzecich, a może nawet czwartych, nieco lepiej zorientowanych w temacie niż autor jakiegoś tam niszowego blogu.

Jesteśmy już blisko mety, jeszcze tylko ostatnia prosta!

Czyli tak: rzucamy naszą internetową "monetą" 34 tryliardy razy. Jaka jest *maksymalna* długość ciągu X, gwarantująca - według powyższego wzoru - wystąpienie *każdego* podciągu z prawdopodobieństwem 50%? Jeżeli X zaokrąglimy w górę do wartości całkowitej, uzyskamy naszą odpowiedź!

Problem sprowadza się do wyznaczenia n przy znanym X:

\(X = 2^{n+1} - 2\)

Podstawiamy:

\(X = 3.4*10^{22} \)

Czyli:

\(3.4*10^{22} = 2^{n+1} - 2 \)

Po kilku prostych przekształceniach (trzeba po drodze zlogarytmować obie strony o podstawie 2) dostaniemy:

n ~= 73.8

Stąd wniosek, że wszystkie podciągi 73-bitowe zostały *prawdopodobnie* wykorzystane, a 74-bitowe - jeszcze nie.

Ilość danych przesyłanych przez Sieć stale rośnie. Jeżeli wierzyć analitykom z firmy Cisco, do 2021 roku długość najkrótszego ciągu bitów, który jeszcze nie został przesłany Internetem zwiększy się o dwa bity i wyniesie 76.

Może kiedyś nawet pokuszę się o znalezienie i opublikowanie takiego ciągu 🙂

https://xpil.eu/zcl 📋