szukanie zaawansowane
 [ Posty: 4 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 5 gru 2018, o 15:20 
Użytkownik

Posty: 15
Lokalizacja: Wrocław
1.Wrzucamy niezależnie losowo kole do n urn. Pokaż, że dla pewniej stałej c_1 > 0, jeżeli wrzucamy c_1\sqrt{n} kul to prawdopodobieństwo, ze żadne dwie kule nie wylądują w jednej urnie wynosi co najwyżej \frac{1}{e}. Podobnie pokaż, że istnieje stała c_2 > 0, jeżeli wrzucamy c_n\sqrt{n} kul to prawdopodobieństwo, że żadne dwie kule nie wylądują w jednej urnie wynosi co najmniej \frac{1}{2}.

2.Załóżmy, że n kul jest wrzucanych niezależnie do n urn.
    a)Wylicz prawdopodobieństwo, że pierwsza urna ma 1 kule pod warunkiem, że dokładnie 1 kula
    wpadła do pierwszych 3 urn.
    b)Wylicz wartość oczekiwaną liczby kul w pierwszej urnie pod warunkiem, że do drugiej urny nie
    wpadła żadna kula.
    c)Napisz wzór na prawdopodobieństwo, że w pierwszej urnie jest więcej kul niż w drugiej.
Góra
Mężczyzna
PostNapisane: 5 gru 2018, o 18:24 
Użytkownik
Avatar użytkownika

Posty: 14103
Lokalizacja: Wrocław
1. Jeżeli wrzucamy k kul do n urn, to prawdopodobieństwo, że żadne dwie kule nie wylądują w jednej urnie wynosi
\frac{k!{n \choose k}}{n^k}= \prod_{i=1}^{k}\left( 1-\frac{i-1}{n}\right)
Skorzystamy teraz z nierówności 1+x\le e^x dla x\in \RR:
dla k\le n mamy
\prod_{i=1}^{k}\left( 1-\frac{i-1}{n}\right)\le \exp\left( - \sum_{i=1}^{k} \frac{i-1}{n}\right)=\exp\left( -\frac{k(k-1)}{2n}\right)
Zatem jeżeli
k\le n jest tak dobrane, by \exp\left( \frac{(1-k)k}{2n}\right) \le \frac{1}{e}, to nasze prawdopodobieństwo jest ograniczone z góry przez \frac{1}{e}.
e^x jest funkcją rosnącą, zatem wystarczy, by
\frac{(1-k)k}{2n}\le -1
a równoważnie k^2-k\ge 2n, a to jest nierówność kwadratowa zmiennej k z parametrem n, można to po prostu rozwiązać, a można też zauważyć (nie mamy wszak wskazywać optymalnej stałej!), że dla interesujących nas k zachodzi
k^2-k\ge\frac 1 2 k^2, więc jeśli zajdzie
\frac{1}{2}k^2\ge 2n, czyli jeśli k\ge 2\sqrt{n}, to będzie OK. Czyli stała c_1=2 działa.

Druga część zadania pierwszego też jest bardzo prosta, tylko że skorzystamy z nieco innej nierówności:
dla dowolnej stałej a\in(0,1) i dowolnego x>-1 zachodzi
1+ax\ge (1+x)^a
(jest to jeden z przypadków nierówności Bernoulliego).
Niech teraz x=-\frac 1 2, a otrzymamy, że dla a\in(0,1) zajdzie
1-\frac a 2\ge \left( \frac 1 2\right)^a
Korzystamy z takich nierówności kolejno dla
a=\frac{2(i-1)}{n}, \ i=1\ldots k
i otrzymujemy po wymnożeniu stronami nierówność
\prod_{i=1}^{k}\left( 1-\frac{i-1}{n}\right)  \ge \left( \frac 1 2\right)^{2 \sum_{i=1}^{k}\frac{i-1}{n} }
Oczywiście f(x)=\left( \frac 1 2\right)^x jest malejąca w dodatnich, jeśli więc zajdzie
2 \sum_{i=1}^{k} \frac{i-1}{n}\le 1,
to warunki zadania będą spełnione. Ze wzoru na sumę wyrazów ciągu arytmetycznego to przekształcamy do
k(k-1)\le n, a ponieważ w całkowitych dodatnich większych niż 1 jest
k^2>k(k-1), więc jeśli k^2\le n, to także k(k-1)\le n (a nawet nierówność jest wówczas ostra), toteż można wziąć c_2=1 i wówczas dla
k\le c_2 \sqrt{n} rozważane prawdopodobieństwo wynosi co najmniej \frac 1 2.
Góra
Mężczyzna
PostNapisane: 5 gru 2018, o 22:07 
Użytkownik

Posty: 15
Lokalizacja: Wrocław
mam tylko jedno pytanie co do ostatniego zdania czy k\le c_2 \sqrt{n} bedzie w tym przypadku tym samym co k= c_2 \sqrt{n} o ile dobrze rozumiem a uzycie znaku mniejsze rowne troche mnie na koncu zmylilo i sie zastanawiam czy czegos nie pojałem czy poprostu tak sie napsialo ?
Góra
Mężczyzna
PostNapisane: 5 gru 2018, o 22:23 
Użytkownik
Avatar użytkownika

Posty: 14103
Lokalizacja: Wrocław
Jeśli to przeanalizujemy, pokazałem, że nierówność jest spełniona dla dowolnego k całkowitego dodatniego nie większego od \sqrt{n}, w szczególności dla k=\sqrt{n} (o ile n jest kwadratem). Działa też dowolna stała c_2 dodatnia mniejsza od 1 (podobnie w poprzedniej części moglibyśmy wziąć dowolne c_1 nie mniejsze niż 2, oczywiście ma to sens, póki zachowamy warunek k\le n, w przeciwnym razie z zasady szufladkowej Dirichleta wiemy, że do którejś urny trafią co najmniej dwie kule).
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 4 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Zadania testowe - pemutacje, zwracanie :)  Anonymous  2
 Pojemniki z kulami-ilość sposobów rozmieszczenia kul.  qwertyyyy  2
 3 zadania...  Ciapanek  2
 Zadania z kombinatoryki  neworder  1
 Dwa SKOMPLIKOWANE zadania :)))  domel666  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl