Książka o prawdopodobieństwie

32

Chociaż zdałem kilka kursów z teorii prawdopodobieństwa, zarówno w szkole średniej, jak i na uniwersytecie, trudno mi czytać artykuły TCS, jeśli chodzi o prawdopodobieństwo.

Wydaje się, że autorzy artykułów TCS są bardzo dobrze zaznajomieni z prawdopodobieństwem. Magicznie działają ze wzorami prawdopodobieństwa i bardzo łatwo dowodzą twierdzeń; podczas gdy muszę spędzić kilka dobrych godzin, aby zrozumieć, w jaki sposób wyprowadzono jedną formułę i jak udowodniono tożsamości (lub nierówności).

Postanowiłem rozwiązać problem raz na zawsze: chcę przeczytać książkę od deski do deski.

Jeśli więc zostaniesz poproszony o zasugerowanie jednej i tylko jednej książki prawdopodobieństwa, jaką książkę polecisz?

Niesamowite
źródło
3
+1, ponieważ doceniłbym dobre referencje. Czy mogę również zasugerować, że taka książka musiałaby obejmować wnioskowanie bayesowskie?
Steve
4
@Incredible: Czy możesz wyjaśnić więcej? Książka prawdopodobieństwa w ogóle, czy książka prawdopodobieństwa koncentrująca się na związku z teoretyczną informatyką?
Yoshio Okamoto
@Yoshio: Nie szukam książki, w której wyjaśnione jest prawdopodobieństwo w kontekście TCS. Potrzebuję tylko książki, którą po przeczytaniu od deski do deski mogę poznać prawdopodobieństwo, dzięki czemu czytanie i odtajnianie kart TCS działa jak urok.
Niesamowite
@ Steve: Tak, wniosek Bayesa jest doceniany. Niedawno przeczytałem artykuł ( Lower Bounds for Zero Knowledge w Internecie ), w którym wnioskowanie bayesowskie zostało wykorzystane w istotny sposób, i nie mogłem łatwo odszyfrować twierdzeń i lematów.
MS Dousti,
1
dlaczego to nie stało się CW?
Suresh Venkat

Odpowiedzi:

22

Próbowałeś już tych dwóch książek?

  1. Prawdopodobieństwo i obliczenia: algorytmy randomizowane i analiza probabilistyczna Mitzenmachera i Upfala.
  2. Losowe algorytmy Motwani i Raghavan

Zauważ, że te dwie książki obejmują znacznie więcej niż tylko algorytmy losowe, np. Obejmują Metodę Probabilistyczną, Teorię Łańcucha Markowa, Martingalesa itp., Oczywiście z wieloma aplikacjami w TCS. Pierwsza książka jest łatwiejsza do odczytania z wieloma przykładami, których dowody zostały szczegółowo opracowane. Druga książka jest naprawdę klasyczna, niezbyt zaktualizowana, ale wciąż bardzo przydatna. Obaj mają dużo ćwiczeń, więc będziesz miał mnóstwo materiału do ćwiczenia tego, czego się nauczyłeś.

Dai Le
źródło
12

Kanoniczny podręcznik licencjacki z teorii prawdopodobieństwa pozostaje pierwszym kursem prawdopodobieństwa Sheldona Rossa. Książka jest doskonałą referencją / odświeżeniem dla wszystkich innych. Niezależnie od tego, co twierdzą niektórzy zrzędliwi recenzenci internetowi, książka omawia wszystkie najważniejsze tematy z elementarnym prawdopodobieństwem w sposób wyraźny i z mocnymi motywującymi przykładami.

Huck Bennett
źródło
11

Myślę, że rozwiązaniem twojego problemu nie jest czytanie książki prawdopodobieństwa, ale czytanie kolejnych artykułów w TCS.

Większość dokumentów w TCS w rzeczywistości nie używa bardzo zaawansowanych narzędzi prawdopodobieństwa. Większość z nich używa niewielkiej kolekcji podstawowych i dobrze znanych sztuczek prawdopodobieństwa. Powodem, dla którego masz trudności z ich przestrzeganiem, jest to, że nie znasz jeszcze tej sztuczki, a wiele z tych artykułów nie zadaje sobie trudu, aby wyjaśnić te sztuczki, ponieważ zakładają, że czytelnik je zna. Niektóre z tych sztuczek nie są nauczane w większości ksiąg prawdopodobieństwa, a przynajmniej nie w określonej formie, w jakiej są używane w artykułach TCS.

{0,1}n

Tak więc, czytając więcej artykułów TCS, zapoznasz się z torbą popularnych sztuczek i terminologią, a z czasem będą one łatwiejsze do zrozumienia.

To powiedziawszy, czytanie książki o prawdopodobieństwie jest zawsze dobrym pomysłem. Wśród książek zasugerowanych powyżej znam tylko „Prawdopodobieństwo i obliczenia: randomizowane algorytmy i analiza probabilistyczna” Mitzenmachera i Upfala, i jest to bardzo dobra lektura - w szczególności pomoże ci zapoznać się z niektórymi terminami i sztuczki stosowane w TCS.

Lub Meir
źródło
Dobrze powiedziane! Żałuję, że nie mogliśmy zebrać niektórych przedmiotów z tej „torby sztuczek”, aby pomóc początkującym w polu. Może możesz założyć wiki społeczności z jednym przykładem.
MS Dousti
1
Jeśli chodzi o przykład zmiennych losowych: pamiętam 6 lat temu, kiedy miałem to samo pytanie: dlaczego RV TCS nie są zdefiniowane w rzeczywistości? Szukałem i znalazłem odpowiedź: RV to coś więcej niż uczymy się w elementarnych klasach prawdopodobieństwa. Oto link dla zainteresowanych: en.wikipedia.org/wiki/… .
MS Dousti,
9

Kolejnym klasykiem prawdopodobieństwa zorientowanego na TCS / Combinatorics jest Alon i metoda probabilistyczna Spencera .

Yonatan
źródło
1
To dobra rekomendacja. Jak powiedział Or Meir w swojej odpowiedzi, TCS stosuje stosunkowo ograniczony zestaw sztuczek z teorii prawdopodobieństwa. Książka Alona i Spencera koncentruje się na tej torbie sztuczek, nie zagłębiając się w szczegóły techniczne z teorii prawdopodobieństwa, które nie są tak istotne dla TCS.
Timothy Chow,
8

Kilka powiązanych tematów na różnych stronach internetowych SE:

  1. Rezerwuj na prawdopodobieństwo
  2. Wymagania wstępne dotyczące teorii prawdopodobieństwa
  3. Literatura uzupełniająca do badań teorii prawdopodobieństwa
  4. Jaką książkę poleciłbyś niestatystom (głównie książkom statystycznym)

Chociaż nie czytałem żadnej z tych książek, miałem luksus spojrzenia na niektóre z nich. Podobał mi się trzytomowy serial HPS (Hoel, Port i Stone). Nie spodziewał się zbyt dużego tła i istniało wyraźne rozróżnienie między prawdopodobieństwem tematów, statystykami i procesami stochastycznymi (osobny tom poświęcony jest każdemu tematowi). Co więcej, każdy tom jest raczej krótki.

Muszę ponownie podkreślić, że nie znam treści żadnej z wymienionych książek. Zapraszam innych członków do komentowania tego postu.

M.S. Dousti
źródło
6

Kilka plakatów w tej dyskusji zalecało zestaw dwóch tomów Fellera . Nowszym i podobno bardzo dobrym podręcznikiem jest Grimmett i Stirzaker . Również tutaj jest ciekawa bibliografia przez profesjonalnych statystyk.

Michaił Glushenkov
źródło
Mam Fellera, Grimmeta i Stirzakera. W połączeniu z internetowym kursem MIT „Podstawy prawdopodobieństwa” okazało się dobrą bramą do koncepcji prawdopodobieństwa, których będziesz potrzebować jako zaawansowany student / absolwent.
chazisop
4

Bardzo dobra książka:

Prawdopodobieństwo Leo Breimana

Sylvain Peyronnet
źródło
4
Przedmowa mówi: „Warunkiem wstępnym jest znajomość teorii zmiennych rzeczywistych, takich jak pojęcia miary, mierzalne funkcje itp. Z grubsza, pierwsze siedem rozdziałów teorii miary Paula Halmosa stanowi wystarczające tło… Brak wcześniejszej wiedzy zakłada się prawdopodobieństwo, ale przeglądanie podstawowej książki, takiej jak ta autorstwa Williama Fellera (t. I) ... daje doskonałe wyczucie tematu. ” To musi być zaawansowana książka!
MS Dousti
4

Konkretna matematyka Knutha i in. Prawdopodobieństwo ustalenia wielkości wszechświata jest duże, a stamtąd to, którą frakcją wszechświata jesteś zainteresowany.

Chad Brewbaker
źródło
4

Doskonałą wstępną książką prawdopodobieństwa dla informatyków jest Henk Tijms, Understanding Probability, Cambridge University Press, 2. wydanie, 2007. Ta książka wyróżnia się spośród innych wstępnych tekstów prawdopodobieństwa, kładąc nacisk na to, dlaczego prawdopodobieństwo działa i jak go stosować.

Chris
źródło
4

Spośród wymienionych książek zgadzam się z „Prawdopodobieństwem” Briemana, książką Sheldona Rossa „Pierwszy kurs prawdopodobieństwa” Książką „Prawdopodobieństwo” Hoela, Porta i Stone'a z ich trzech serii Tomowych. Większość innych książek, których albo nie znam, albo nie uważam za odpowiednie. Statystyka bayesowska nie jest częścią teorii prawdopodobieństwa. „Kurs teorii prawdopodobieństwa” Kai Li Chunga jest tym, z którego nauczyłem się wraz z tomem II książki Fellera „Wprowadzenie do teorii prawdopodobieństwa i jej zastosowań” to dobre książki, z których się nauczyłem. Feller jest dobry dla heurystyki i interesujących problemów. Chung jest dobry dla formalnej matematyki. Feller i Chung mogą być jednak trudne do odczytania, zwłaszcza do samodzielnej nauki. Innym świetnym pisarzem książek prawdopodobieństwa jest Sid Resnick. Jego książka „Ścieżka prawdopodobieństwa” jest przyjemna do przeczytania. „Rachunek prawdopodobieństwa” Neveu to kolejna książka, którą wykorzystaliśmy na moim kursie prawdopodobieństwa dla absolwentów.

Michael Chernick
źródło
2

Świetna książka z EE skos: http://www.mhhe.com/engcs/electrical/papoulis/ fantastyczna książka z CS skos: http://www.amazon.com/dp/0471333417/ .

użytkowników4563
źródło
Lubię też Papoulisa, choć nie jestem pewien, czy potrzebował 50% wzrostu lub nowego autora do nowej edycji. Jeśli zauważysz, że starsze wydanie (np. Przedruk drugiego wydania, które zostało opublikowane przez firmę Dell i sprzedane w dużych ilościach) idzie tanie, kup je.
András Salamon,