Dwa zadania z kulami i urnami

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
gokuruto
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 21 cze 2018, o 00:38
Płeć: Mężczyzna
Lokalizacja: Wrocław

Dwa zadania z kulami i urnami

Post autor: gokuruto » 5 gru 2018, o 14:20

1.Wrzucamy niezależnie losowo kole do n urn. Pokaż, że dla pewniej stałej \(\displaystyle{ c_1 > 0}\), jeżeli wrzucamy \(\displaystyle{ c_1\sqrt{n}}\) kul to prawdopodobieństwo, ze żadne dwie kule nie wylądują w jednej urnie wynosi co najwyżej \(\displaystyle{ \frac{1}{e}}\). Podobnie pokaż, że istnieje stała \(\displaystyle{ c_2 > 0}\), jeżeli wrzucamy \(\displaystyle{ c_n\sqrt{n}}\) kul to prawdopodobieństwo, że żadne dwie kule nie wylądują w jednej urnie wynosi co najmniej \(\displaystyle{ \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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14923
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 133 razy
Pomógł: 4940 razy

Re: Dwa zadania z kulami i urnami

Post autor: Premislav » 5 gru 2018, o 17:24

1. Jeżeli wrzucamy \(\displaystyle{ k}\) kul do \(\displaystyle{ n}\) urn, to prawdopodobieństwo, że żadne dwie kule nie wylądują w jednej urnie wynosi
\(\displaystyle{ \frac{k!{n \choose k}}{n^k}= \prod_{i=1}^{k}\left( 1-\frac{i-1}{n}\right)}\)
Skorzystamy teraz z nierówności \(\displaystyle{ 1+x\le e^x}\) dla \(\displaystyle{ x\in \RR}\):
dla \(\displaystyle{ k\le n}\) mamy
\(\displaystyle{ \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
\(\displaystyle{ k\le n}\) jest tak dobrane, by \(\displaystyle{ \exp\left( \frac{(1-k)k}{2n}\right) \le \frac{1}{e}}\), to nasze prawdopodobieństwo jest ograniczone z góry przez \(\displaystyle{ \frac{1}{e}}\).
\(\displaystyle{ e^x}\) jest funkcją rosnącą, zatem wystarczy, by
\(\displaystyle{ \frac{(1-k)k}{2n}\le -1}\)
a równoważnie \(\displaystyle{ k^2-k\ge 2n}\), a to jest nierówność kwadratowa zmiennej \(\displaystyle{ k}\) z parametrem \(\displaystyle{ 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 \(\displaystyle{ k}\) zachodzi
\(\displaystyle{ k^2-k\ge\frac 1 2 k^2}\), więc jeśli zajdzie
\(\displaystyle{ \frac{1}{2}k^2\ge 2n}\), czyli jeśli \(\displaystyle{ k\ge 2\sqrt{n}}\), to będzie OK. Czyli stała \(\displaystyle{ 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 \(\displaystyle{ a\in(0,1)}\) i dowolnego \(\displaystyle{ x>-1}\) zachodzi
\(\displaystyle{ 1+ax\ge (1+x)^a}\)
(jest to jeden z przypadków nierówności Bernoulliego).
Niech teraz \(\displaystyle{ x=-\frac 1 2}\), a otrzymamy, że dla \(\displaystyle{ a\in(0,1)}\) zajdzie
\(\displaystyle{ 1-\frac a 2\ge \left( \frac 1 2\right)^a}\)
Korzystamy z takich nierówności kolejno dla
\(\displaystyle{ a=\frac{2(i-1)}{n}, \ i=1\ldots k}\)
i otrzymujemy po wymnożeniu stronami nierówność
\(\displaystyle{ \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 \(\displaystyle{ f(x)=\left( \frac 1 2\right)^x}\) jest malejąca w dodatnich, jeśli więc zajdzie
\(\displaystyle{ 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
\(\displaystyle{ k(k-1)\le n}\), a ponieważ w całkowitych dodatnich większych niż \(\displaystyle{ 1}\) jest
\(\displaystyle{ k^2>k(k-1)}\), więc jeśli \(\displaystyle{ k^2\le n}\), to także \(\displaystyle{ k(k-1)\le n}\) (a nawet nierówność jest wówczas ostra), toteż można wziąć \(\displaystyle{ c_2=1}\) i wówczas dla
\(\displaystyle{ k\le c_2 \sqrt{n}}\) rozważane prawdopodobieństwo wynosi co najmniej \(\displaystyle{ \frac 1 2}\).

gokuruto
Użytkownik
Użytkownik
Posty: 15
Rejestracja: 21 cze 2018, o 00:38
Płeć: Mężczyzna
Lokalizacja: Wrocław

Re: Dwa zadania z kulami i urnami

Post autor: gokuruto » 5 gru 2018, o 21:07

mam tylko jedno pytanie co do ostatniego zdania czy \(\displaystyle{ k\le c_2 \sqrt{n}}\) bedzie w tym przypadku tym samym co \(\displaystyle{ 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 ?

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 14923
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 133 razy
Pomógł: 4940 razy

Re: Dwa zadania z kulami i urnami

Post autor: Premislav » 5 gru 2018, o 21:23

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

ODPOWIEDZ