Wybrane Zagadnienia Probabilistyczne Lista przygotowawcza 2012/13

1. Udowodnić (dla skończonego modelu probabilistycznego : Ω = {ω1, . . . , ωn}) addytywność wartości oczekiwanej, tzn. równość E(X + Y ) = EX + EY .

2. Jaka jest w grafie losowym G(n, p) (n > 3) wartość oczekiwana liczby trójek wierzcho lków tworz¸

acych graf pe lny (tzn. w tym wypadku trójk¸

at). Odpowiedź

szczegó lowo uzasadnić?

3. Udowodnić (dla skończonego modelu probabilistycznego: Ω = {ω1, . . . , ωn}) zasad¸

e pierwszego momentu, tzn. twierdzenie mowi¸

ace, że jesli EX ≤ α, to P [X ≤ α] > 0.

4. Udowodnić (dla skończonego modelu probabilistycznego: Ω = {ω1, . . . , ωn}) i dla zmiennej losowej X ≥ 0 nierówność Markowa: αP [X ≥ α] ≤ EX dla α ≥ 0.

5. Pokazać, pos luguj¸

ac si¸

e zasad¸

a pierwszego momentu, że jeśli w k-SAT jest mniej niż 2k klauzul, to k−SAT jest spe lnialna. Podać definicj¸

e klauzuli, k-SAT

i spe lnialności.

6. Sformu lować i udowodnić nierówność Czebyszewa.

7. Zdefiniować zbiór o różnych sumach. Pokzać, że jeśli A ⊆ {1, 2, . . . , n} jest zbiorem o różnych sumach, to |A| ≤ log n + log log n + O(1).

2

2

2

8. Zdefiniować zbiór o różnych sumach. Pokzać, że jeśli A ⊆ {1, 2, . . . , n} jest zbiorem o różnych sumach, to |A| ≤ log n + 1 log log n + O(1).

2

2

2

2

7. Sforrmu lować lokalny lemat Lovasza.

8.

Pos luguj¸

ac si¸

e lokalnym leamtem Lovasza, udowodnić, że jeśli w k-SAT

każda zmienna boolowska leży w nie wi¸

ecej niż 2k−2 klauzulach, to k-SAT jest spe lnialna. Podać definicj¸

e klauzuli, k-SAT i spe lnialności.

9. Jacek i Placek graj¸

a, rzucaj¸

ac na przemian symetryczn¸

a monet¸

a, w nast¸

epuj¸

ac¸

a

gr¸

e: jeśli pojawi si¸

e sekwencja OOO to wygrywa Jacek i gra si¸

e kończy, jeśli po-

jawi si¸

e sekwencja RR to wygrywa Placek i gra si¸

e kończy. Przedstawić t¸

e gr¸

e

jako lańcuch Markowa o skończonej ilości stanów, uwzgl¸

edniaj¸

ac start jako jeden ze stanów. Podać macierz przejścia.

10. Jakie stany nazywamy w lańcuchu Markowa: poch laniaj¸

acymi, nieistotnymi, powracaj¸

acymi, chwilowymi? Podać definicj¸

e jednorodnego lańcucha Markowa.

1