Historia losowości - History of randomness
W starożytnej historii , pojęcia przypadku i losowości przeplatały się z tego losu. Wiele starożytnych ludów rzucało kośćmi, aby decydować o losie, co później przekształciło się w gry losowe . Jednocześnie większość starożytnych kultur wykorzystywała różne metody wróżenia, próbując ominąć przypadkowość i los.
Chińczycy byli prawdopodobnie pierwszymi ludźmi, którzy sformalizowali szanse i szanse 3000 lat temu. W greccy filozofowie omówione losowości w długości, ale tylko w formach innych niż ilościowych. Dopiero w XVI wieku włoscy matematycy zaczęli formalizować kursy związane z różnymi grami losowymi. Wynalazek współczesnego rachunku różniczkowego pozytywnie wpłynął na formalne badanie losowości. W XIX wieku w fizyce wprowadzono pojęcie entropii .
Na początku XX wieku nastąpił szybki rozwój formalnej analizy losowości i wprowadzono matematyczne podstawy prawdopodobieństwa, co doprowadziło do jego aksjomatyzacji w 1933 roku. Jednocześnie pojawienie się mechaniki kwantowej zmieniło naukowe spojrzenie na zdeterminowanie . Od połowy do końca XX wieku idee algorytmicznej teorii informacji wprowadziły do dziedziny nowe wymiary poprzez koncepcję algorytmicznej przypadkowości .
Chociaż losowość przez wiele stuleci była często postrzegana jako przeszkoda i uciążliwość, w XX wieku informatycy zaczęli zdawać sobie sprawę, że celowe wprowadzanie losowości do obliczeń może być skutecznym narzędziem do projektowania lepszych algorytmów. W niektórych przypadkach takie randomizowane algorytmy są w stanie przewyższyć najlepsze metody deterministyczne.
Od starożytności do średniowiecza
Przedchrześcijanie mieszkający w rejonie Morza Śródziemnego rzucali kośćmi, aby decydować o losie, co później przekształciło się w gry losowe. Istnieją również dowody na gry losowe, w które grali starożytni Egipcjanie, Hindusi i Chińczycy, datowane na 2100 r. p.n.e. Chińczycy używali kości przed Europejczykami i mają długą historię grania w gry losowe.
Ponad 3000 lat temu problemy związane z rzucaniem kilkoma monetami były rozważane w I Ching , jednym z najstarszych chińskich tekstów matematycznych, datowanym prawdopodobnie na 1150 rpne. Dwa główne elementy, yin i yang, zostały połączone w I Ching w różnych formach, aby wytworzyć permutacje głów i ogonów typu HH, TH, HT itd., a Chińczycy wydają się być świadomi istnienia trójkąta Pascala na długo przed sformalizowaniem go przez Europejczyków. w XVII wieku. Jednak filozofia zachodnia aż do XVI wieku koncentrowała się na niematematycznych aspektach przypadku i przypadkowości.
Rozwój pojęcia przypadku na przestrzeni dziejów był bardzo stopniowy. Historycy zastanawiali się, dlaczego postęp w dziedzinie przypadkowości był tak powolny, biorąc pod uwagę, że ludzie od starożytności spotykali się z przypadkiem. Deborah J. Bennett sugeruje, że zwykli ludzie napotykają nieodłączną trudność w zrozumieniu przypadkowości, chociaż pojęcie to jest często uważane za oczywiste i oczywiste. Cytuje badania Kahnemana i Tversky'ego ; doszli do wniosku, że zasad statystycznych nie uczy się z codziennego doświadczenia, ponieważ ludzie nie zwracają uwagi na szczegóły niezbędne do zdobycia takiej wiedzy.
Greccy filozofowie byli pierwszymi zachodnimi myślicielami zajmującymi się przypadkiem i przypadkowością. Około 400 rpne Demokryt przedstawił pogląd na świat rządzony jednoznacznymi prawami porządku i uważał losowość za pojęcie subiektywne, które wywodziło się jedynie z niezdolności ludzi do zrozumienia natury wydarzeń. Posłużył się przykładem dwóch mężczyzn, którzy wysyłali swoje sługi, aby przynieśli wodę w tym samym czasie, aby doprowadzić ich do spotkania. Słudzy, nieświadomi planu, uznaliby spotkanie za przypadkowe.
Arystoteles postrzegał przypadek i konieczność jako przeciwstawne siły. Twierdził, że natura ma bogate i stałe wzorce, które nie mogą być wynikiem samego przypadku, ale wzorce te nigdy nie wykazywały maszynowej jednolitości koniecznego determinizmu. Przypadkowość postrzegał jako autentyczną i rozpowszechnioną część świata, ale podporządkowaną konieczności i porządkowi. Arystoteles podzielił zdarzenia na trzy typy: pewne zdarzenia, które zachodzą z konieczności; prawdopodobne zdarzenia, które mają miejsce w większości przypadków; i niepoznawalne zdarzenia, które dzieją się przez czysty przypadek. Uważał wynik gier losowych za niepoznawalny.
Około 300 pne Epikur zaproponował koncepcję, że losowość istnieje sama w sobie, niezależnie od ludzkiej wiedzy. Uważał, że w świecie atomowym atomy będą skręcać losowo na swojej drodze, powodując losowość na wyższych poziomach.
Przez kilka następnych stuleci idea przypadku nadal splatała się z losem. Wróżbiarstwo było praktykowane w wielu kulturach przy użyciu różnych metod. Chińczycy analizowali pęknięcia w skorupach żółwi, podczas gdy Niemcy, którzy według Tacyta najbardziej szanowali losy i wróżby, wykorzystywali paski kory. W Cesarstwie Rzymskim przypadek był uosobieniem Bogini Fortuna . Rzymianie brali udział w grach losowych, symulując to, co zdecydowałaby Fortuna. W 49 roku p.n.e. Juliusz Cezar podobno po rzuceniu kostką podjął decyzję o przekroczeniu Rubikonu .
Arystotelesowski podział zdarzeń na trzy klasy: pewne , prawdopodobne i niepoznawalne został przyjęty przez filozofów rzymskich, ale musieli go pogodzić z deterministycznymi naukami chrześcijańskimi, w których nawet zdarzenia niepoznawalne dla człowieka uważano za z góry określone przez Boga. Około 960 biskup Wibold z Cambrai poprawnie wyliczył 56 różnych wyników (bez permutacji) gry trzema kostkami. W Europie przed 1350 r. nie znaleziono wzmianki o grze w karty. Kościół głosił przeciwko grze w karty, a gry karciane rozprzestrzeniały się znacznie wolniej niż gry oparte na kościach. Kościół chrześcijański wyraźnie zabronił wróżbiarstwa ; a gdziekolwiek poszło chrześcijaństwo, wróżbiarstwo straciło większość swojej dawnej mocy.
Przez wieki wielu chrześcijańskich uczonych zmagało się z konfliktem między wiarą w wolną wolę i jej dorozumianą przypadkowością, a ideą, że Bóg wie wszystko, co się dzieje. Święci Augustyn i Akwinata próbowali pogodzić uprzednią wiedzę i wolną wolę, ale Marcin Luter sprzeciwiał się przypadkowości i przyjął stanowisko, że wszechwiedza Boga czyni ludzkie działania nieuniknionymi i zdeterminowanymi. W XIII wieku Tomasz z Akwinu postrzegał przypadkowość nie jako skutek jednej przyczyny, ale kilku przyczyn zbiegających się przypadkowo. Chociaż wierzył w istnienie przypadkowości, odrzucał ją jako wyjaśnienie ukierunkowania natury na cel, ponieważ widział w naturze zbyt wiele wzorców, by można je było uzyskać przypadkowo.
Grecy i Rzymianie nie zauważyli wielkości względnych częstotliwości gier losowych. Przez wieki w Europie dyskutowano o losie bez podstaw matematycznych i dopiero w XVI wieku włoscy matematycy zaczęli dyskutować o wynikach gier losowych jako proporcjach. W swoim Liber de Lude Aleae z 1565 roku (podręczniku hazardzisty opublikowanym po jego śmierci) Gerolamo Cardano napisał jeden z pierwszych formalnych traktatów analizujących szanse wygranej w różnych grach.
XVII-XIX wiek
Około 1620 Galileusz napisał artykuł zatytułowany O odkryciu dotyczącym kości, w którym wykorzystał wczesny model probabilistyczny do odpowiedzi na konkretne pytania. W 1654, zainspirowany zainteresowaniem Chevaliera de Méré hazardem, Blaise Pascal nawiązał korespondencję z Pierre'em de Fermatem i położono wiele podwalin pod teorię prawdopodobieństwa. Zakład Pascala był znany z wczesnego użycia pojęcia nieskończoności i pierwszego formalnego użycia teorii decyzji . Prace Pascala i Fermata wpłynęły na prace Leibniza nad rachunkiem nieskończenie małym , co z kolei nadało pędu formalnej analizie prawdopodobieństwa i losowości.
Pierwszą znaną sugestię postrzegania losowości w kategoriach złożoności przedstawił Leibniz w mało znanym XVII-wiecznym dokumencie odkrytym po jego śmierci. Leibniz pytał, skąd można wiedzieć, czy zbiór punktów na kartce został wybrany losowo (np. przez rozpryskiwanie atramentu), czy nie. Biorąc pod uwagę, że dla dowolnego zbioru punktów skończonych zawsze istnieje równanie matematyczne, które może opisywać punkty (np. przez interpolację Lagrange'a ), pytanie skupia się na sposobie matematycznego wyrażenia punktów. Leibniz uważał punkty za losowe, jeśli opisująca je funkcja musiała być niezwykle złożona. Trzy wieki później ta sama koncepcja została sformalizowana jako losowość algorytmiczna przez AN Kołmogorowa i Gregory'ego Chaitina jako minimalna długość programu komputerowego potrzebna do opisania skończonego ciągu jako losowego.
The Doctrine of Chances , pierwszy podręcznik teorii prawdopodobieństwa, został opublikowany w 1718 roku i od tego czasu dziedzina ta nadal się rozwijała. Teoria częstotliwość podejście do prawdopodobieństwa została opracowana przez Roberta Ellisa i John Venn koniec w 19 wieku.
Podczas gdy matematyczna elita czyniła postępy w zrozumieniu przypadkowości od XVII do XIX wieku, ogół społeczeństwa nadal polegał na praktykach takich jak wróżenie w nadziei na okiełznanie przypadku. Wróżby przepowiadali na wiele sposobów zarówno na Wschodzie (gdzie wróżby nazwano później nałogiem), jak iw Europie przez Cyganów i innych. Angielskie praktyki, takie jak czytanie jajek wrzuconych do szklanki, były eksportowane do społeczności purytańskich w Ameryce Północnej.
Termin entropia , który jest obecnie kluczowym elementem w badaniu losowości, został ukuty przez Rudolfa Clausiusa w 1865 roku, gdy badał silniki cieplne w kontekście drugiej zasady termodynamiki . Clausius jako pierwszy stwierdził, że „entropia zawsze wzrasta”.
Od czasów Newtona do około 1890 roku powszechnie uważano, że znając stan początkowy układu z dużą dokładnością i jeśli wszystkie siły działające na układ można sformułować z równą dokładnością, w zasadzie byłoby to możliwe. , aby przewidywać stan wszechświata przez nieskończenie długi czas. Granice takich przewidywań w układach fizycznych stały się jasne już w 1893 roku, kiedy Henri Poincaré wykazał, że w astronomicznym problemie trzech ciał małe zmiany stanu początkowego mogą skutkować dużymi zmianami trajektorii podczas numerycznego całkowania równań.
W XIX wieku, gdy teoria prawdopodobieństwa została sformalizowana i lepiej zrozumiana, stosunek do „losowości jako uciążliwości” zaczął być kwestionowany. Goethe napisał:
Tkanka świata zbudowana jest z konieczności i przypadkowości; intelekt ludzi umieszcza się między nimi i może je kontrolować; rozważa konieczność i rację swojego istnienia; wie, jak można zarządzać, kontrolować i wykorzystywać losowość.
Słowa Goethego okazały się prorocze, gdy w XX wieku randomizowane algorytmy odkryto jako potężne narzędzia. Pod koniec XIX wieku model mechanicznego wszechświata Newtona zanikał, gdy Maxwell i Boltzmann badali statystyczny obraz zderzeń cząsteczek w gazach . Równanie Boltzmanna S = k log e W (zapisane na jego nagrobku) najpierw powiązało entropię z logarytmami .
XX wiek
W XX wieku pięć głównych interpretacji teorii prawdopodobieństwa (np. klasyczna , logiczna , częstotliwościowa , skłonność i subiektywna ) zostało lepiej zrozumianych, omówionych, porównanych i przeciwstawionych. W tym stuleciu opracowano wiele obszarów zastosowań, od finansów po fizykę. W 1900 r. Louis Bachelier zastosował ruch Browna do wyceny opcji na akcje , skutecznie wprowadzając dziedziny matematyki finansowej i procesów stochastycznych .
Émile Borel był jednym z pierwszych matematyków, którzy formalnie zajęli się losowością w 1909 roku i wprowadził liczby normalne . W 1919 Richard von Mises podał pierwszą definicję algorytmicznej przypadkowości jako niemożność systemu hazardowego . Rozwijał częstościową teorię losowości w kategoriach tego, co nazwał zbiorowością , czyli ciągiem losowym . Von Mises uważał losowość kolektywu za prawo empiryczne, ustanowione przez doświadczenie. Powiązał „nieporządek” lub przypadkowość kolektywu z brakiem sukcesu systemów hazardowych. Takie podejście doprowadziło go do zaproponować definicję losowości, który został później wyrafinowane i wykonany matematycznie rygorystyczny przez Alonzo Church przy użyciu funkcje obliczalne w 1940. Von Misesa przyrównać zasadę niemożności systemu hazardu z zasadą zachowania energii , a prawo, którego nie można udowodnić, ale które sprawdza się w powtarzanych eksperymentach.
Von Mises nigdy nie sformalizował całkowicie swoich reguł selekcji podciągów, ale w swoim artykule z 1940 r. „O pojęciu losowej sekwencji” Alonzo Church zasugerował, że funkcje używane do ustawiania miejsc w formalizmie von Misesa są funkcjami obliczalnymi, a nie arbitralnymi. początkowych segmentów sekwencji, odwołując się do tezy Kościoła-Turinga o skuteczności.
Pojawienie się mechaniki kwantowej na początku XX wieku i sformułowanie zasady nieoznaczoności Heisenberga w 1927 roku oznaczało koniec newtonowskiego sposobu myślenia fizyków dotyczącego determinacji natury . W mechanice kwantowej, nie jest jeszcze droga do rozważenia wszystkich obserwowalnych elementów w systemie jako zmiennych losowych na raz , ponieważ wiele obserwable nie dojeżdża.
Na początku lat czterdziestych podejście do prawdopodobieństwa oparte na teorii częstotliwości było dobrze akceptowane w kręgu wiedeńskim , ale w latach pięćdziesiątych Karl Popper zaproponował teorię skłonności . Biorąc pod uwagę, że podejście częstotliwościowe nie może poradzić sobie z „pojedynczym rzutem” monetą i może dotyczyć tylko dużych zespołów lub kolektywów, prawdopodobieństwa pojedynczego przypadku były traktowane jako skłonności lub szanse. Koncepcja skłonności wynikała również z chęci radzenia sobie z jednorazowymi ustawieniami prawdopodobieństwa w mechanice kwantowej, np. prawdopodobieństwem rozpadu określonego atomu w określonym momencie. Mówiąc bardziej ogólnie, podejście częstotliwościowe nie może zająć się prawdopodobieństwem śmierci konkretnej osoby, biorąc pod uwagę, że śmierć nie może się powtórzyć dla tej osoby. Karl Popper powtórzył ten sam pogląd, co Arystoteles, postrzegając losowość jako podporządkowaną porządkowi, kiedy pisał, że „pojęcie przypadku nie jest sprzeczne z pojęciem prawa” z natury, pod warunkiem, że weźmie się pod uwagę prawa przypadku.
Rozwój teorii informacji Claude'a Shannona w 1948 r. dał początek entropiowemu spojrzeniu na losowość. Z tego punktu widzenia losowość jest przeciwieństwem determinizmu w procesie stochastycznym . Zatem jeśli układ stochastyczny ma entropię zero, nie ma on losowości, a każdy wzrost entropii zwiększa losowość. Sformułowanie Shannona nie odpowiada XIX-wiecznemu sformułowaniu entropii Boltzmanna w przypadku, gdy wszystkie prawdopodobieństwa są równe. Entropia jest obecnie szeroko stosowana w różnych dziedzinach nauki, od termodynamiki po chemię kwantową .
Martingale do badania szans i strategii obstawiania zostały wprowadzone przez Paula Lévy'ego w latach 30. XX wieku i sformalizowane przez Josepha L. Dooba w latach 50. XX wieku. Zastosowanie hipotezy błądzenia losowego w teorii finansów po raz pierwszy zaproponował Maurice Kendall w 1953 r. Później promowali ją Eugene Fama i Burton Malkiel .
Struny losowe zostały po raz pierwszy zbadane w latach sześćdziesiątych przez AN Kołmogorowa (który dostarczył pierwszą aksjomatyczną definicję teorii prawdopodobieństwa w 1933), Chaitina i Martina-Löfa . Algorytmiczne losowość z ciągu określono jako minimalna wielkość programu (np bitów) wykonywane na uniwersalnym komputerem że plony ciąg. Liczba Omega Chaitina powiązała później losowość i prawdopodobieństwo zakończenia działania programów.
W 1964 roku Benoît Mandelbrot zasugerował, że większość modeli statystycznych zbliża się jedynie do pierwszego etapu radzenia sobie z indeterminizmem i że ignoruje wiele aspektów turbulencji w świecie rzeczywistym. W 1997 roku zdefiniował siedem stanów losowości , od „łagodnej do dzikiej”, przy czym tradycyjna losowość znajduje się na łagodnym końcu skali.
Pomimo postępów matematycznych, w XX wieku kontynuowano poleganie na innych metodach radzenia sobie z przypadkiem, takich jak wróżenie i astrologia . Rząd Mjanmy podobno ukształtował XX-wieczną politykę gospodarczą opartą na wróżbiarstwie i zaplanował przeprowadzkę stolicy kraju w oparciu o rady astrologów. Szef sztabu Białego Domu Donald Regan skrytykował zaangażowanie astrologa Joan Quigley w decyzje podejmowane podczas prezydentury Ronalda Reagana w latach 80-tych. Quigley twierdzi, że od siedmiu lat jest astrologiem Białego Domu.
W XX wieku lepiej rozumiano ograniczenia w radzeniu sobie z przypadkowością. Najbardziej znanym przykładem zarówno teoretycznych, jak i operacyjnych ograniczeń przewidywalności jest prognozowanie pogody, po prostu dlatego, że modele są używane w tej dziedzinie od lat pięćdziesiątych. Prognozy pogody i klimatu są z konieczności niepewne. Obserwacje pogody i klimatu są niepewne i niekompletne, a modele, do których wprowadzane są dane, są niepewne. W 1961 roku Edward Lorenz zauważył, że bardzo mała zmiana danych początkowych przesłanych do programu komputerowego do symulacji pogody może skutkować zupełnie innym scenariuszem pogodowym. Później stało się to znane jako efekt motyla , często parafrazowany jako pytanie: „ Czy trzepot skrzydeł motyla w Brazylii wywołał tornado w Teksasie? ”. Kluczowym przykładem poważnych praktycznych ograniczeń przewidywalności jest geologia, gdzie zdolność przewidywania trzęsień ziemi na poziomie indywidualnym lub statystycznym pozostaje odległą perspektywą.
Pod koniec lat 70. i na początku 80. informatycy zaczęli zdawać sobie sprawę, że celowe wprowadzanie losowości do obliczeń może być skutecznym narzędziem do projektowania lepszych algorytmów. W niektórych przypadkach takie randomizowane algorytmy przewyższają najlepsze metody deterministyczne.