EXERCÍCIOS DE MÉTODOS PROBABILÍSTICOS 2O. SEMESTRE DE 2000

1. Prove as seguintes estimativas. Nesta questão, escrevemos O(f(x)) para qualquer termo y tal que |y| ≤ C|f(x)| para todo x satisfazendo |x| ≤ x_{0}, onde C e x_{0} > 0 são constantes absolutas. (Observe que, nestas estimativas, estamos intessados em uma vizinhança de 0.)

(i) 1 + x ≤ e^{x} para todo x ∈ ℝ. (ii) 1 + x > exp {x − x^{2}/2} para todo 0 < x ≤ 1. (iii) 1−x > exp {−x−x^{2}} para todo 0 < x < x_{0}, para algum x_{0} > 0.

De fato, podemos tomar, por exemplo, x_{0} = 0.68. (iv) 1 + x ≥ exp {x + O(x^{2})} para todo x > −1.

(v) 1 + x ≥ exp {x − x^{2}/2 + O(x^{3})} para todo x > −1. [Sugestão. Lembre que 1/(1 − x) = 1 + x + x^{2} + … uniformemente se |x| ≤ x_{0} e x_{0} < 1. Integre ambos os lados para obter

− log(1 − x) = x + \frac{1}{2}x^{2} + \frac{1}{3}x^{3} + …]

{Data de entrega: 4/9/2000}

2. Prove as seguintes estimativas para \binom{a}{b}, onde a e b são inteiros nãonegativos. (i)

\binom{a}{b} ≥ (\frac{a}{b})^{b} .  (1)

(ii)

\binom{a}{b} ≤ \frac{a^{b}}{b!} .  (2)

(iii) Para todo b > 0,

\binom{a}{b} ≤ (\frac{ea}{b})^{b} .  (3)

[Sugestão para (iii ). Avalie (1 + x)^{a} por cima e por baixo para x = b/a. Use, para tanto, 1 + x ≤ e^{x} e o binômio de Newton.]

{Data de entrega: 4/9/2000}

3. Suponha que n é um inteiro positivo e que 0 ≤ p ≤ 1. Seja X uma v.a. binomial de parâmetros n e p: X ∼ Bi(n, p). Isto é,

ℙ(X = k) = \binom{n}{k}p^{k}(1 − p)^{n−k}

Date: Versão de 17 de outubro de 2000.

para todo k inteiro. Prove que

ℙ(X ≥ k) ≤ \binom{n}{k}p^{k} ≤ (\frac{eμ}{k})^{k} ,  (4)

onde μ = 𝔼(X). {Data de entrega: 4/9/2000}

4. Suponha 2 ≤ k ≤ n. Prove que existe uma família de conjuntos F ⊂ \binom{[n]}{k} linear (i.e., |F ∩ F′| ≤ 1 para todo F e F′ ∈ F distintos) com

|F| ≥ c_{k}\binom{n}{2},  (5)

onde c_{k} é uma constante positiva que depende apenas de k (procure maximizar c_{k}). Prove que qualquer tal família satisfaz

|F| ≤ \binom{k}{2}^{−1}\binom{n}{2},  (6)

e portanto a melhor constante possível em (5) é \binom{k}{2}^{−1}. [Sugestão. Para provar a existência da família F, ponha em uma família auxiliar G cada elemento de \binom{[n]}{k} com probabilidade p, independentemente. Para cada par (G, G′) ∈ G × G com 1 < |G ∩ G′| < k, remova G′ de G. Escolha um p adequado para que a família resultante F satisfaça (5).] {Data de entrega: 4/9/2000}

5. Prove que existe uma família linear F ⊂ \binom{[n]}{3} com

|F| ≥ (\frac{1}{3} − o(1)) \binom{n}{2},

onde o(1) denota um termo que tende a 0 conforme n → ∞. Note que, em vista de (6), tal família F tem tamanho assintoticamente ótimo. [Sugestão. Para cada \{a, b, c\} ∈ \binom{[n]}{3}, considere a + b + c (mod n).] {Data de entrega: 4/9/2000}

6. Generalize o resultado da questão anterior, mostrando que existe uma família F de k-subconjuntos de [n] tal que quaisquer dois de seus membros têm no máximo k − 2 elementos em comum e

|F| ≥ (\frac{1}{k} − o(1)) \binom{n}{k − 1}.

Mostre que tal F tem tem tamanho assintoticamente ótimo. {Data de entrega: 4/9/2000}

7. Suponha que p = p(n) = ωn^{−1/3}, onde ω = ω(n) → ∞ conforme n → ∞, e considere o grafo aleatório G(n, p). Seja 0 < ε < 1 uma constante arbitrária. Mostre que para quase todo G = G(n, p) (i.e., que com probabilidade tendendo a 1 conforme n → ∞) temos que todo conjunto de vértices S ⊂ V (G) com |S| ≥ εn induz um triângulo K^{3} em G. [Sugestão. Considere famílias lineares de triplas em S.] {Data de entrega: 11/9/2000} 8. Seja G um grafo. Escrevemos χ_{3}(G) para o número K^{3}-cromático

de G, i.e., o número mínimo de partes em uma partição V (G) = ⋃_{i} V_{i}, onde cada V_{i} induz um subgrafo livre de K^{3} em G. Equivalentemente, χ_{3}(G) é o número mínimo de cores com que podemos colorir os vértices de G de forma que não haja nenhum triângulo monocromático.

(i) Mostre que K^{7} é tal que χ_{3}(K^{7}) > 3. (ii) Mostre que existem grafos G com χ_{3}(G) > 3 livres de K^{7} (i.e.,

que não contêm K^{7} como subgrafo). {Data de entrega: 11/9/2000}

9. Lembre que escrevemos ν(n) para o número de primos que dividem n. Seja N um inteiro positivo, e considere [N] como um espaço de probabilidade, com todos os seus elementos equiprováveis. Mostramos que

𝔼(ν) = log log N + O(1)  (7)

e que

Var(ν) ≤ log log N + O(1).  (8)

(i) Deduza cuidadosamente de (7) e (8) que se λ > 1 é uma constante, então

ℙ \{|ν − log log N| > λ\sqrt{log log N}\} ≤ λ^{−2} + o(1)  (9)

conforme N → ∞. (ii) Deduza de (9) que

ν(n) ∼ log log N

para quase todo n ∈ [N], isto é,

lim_{N→∞} ℙ {|ν − log log N| > ε log log N} = 0.

para todo ε > 0 fixo. {Data de entrega: 11/9/2000}

10. Suponha que

p = p(n) = \frac{log n + f}{n} ,  (10)

onde f = f(n), e considere o grafo aleatório G(n, p). Prove que as seguintes asserções valem para quase todo G = G(n, p).

(i) Se f = f(n) → ∞, então G não tem vértices isolados. (ii) Se f = f(n) → −∞ e |f| ≤ log n, então G tem vértices isolados.

De fato, o número de vértices isolados X = X(G) em G satisfaz

X ∼ exp{−f}.

(iii) O que você consegue dizer sobre o caso em que f = f(n) → f_{0}

para alguma contante f_{0}? {Data de entrega: 11/9/2000} 11. Considere a identidade

∑_{0≤k≤n} \binom{n}{k} = 2^{n},  (11)

e seja ω = ω(n) uma função com ω → ∞ conforme n → ∞. Podemos dizer que a soma em (11) está ‘concentrada’ nos termos com k satisfazendo

|k − \frac{n}{2}| ≤ ω\sqrt{n},  (12)

pois

∑_{k}^{∗} \binom{n}{k} ∼ 2^{n},  (13)

onde ∑_{k}^{∗} indica soma sobre todos os k satisfazendo (12) e escrevemos f(n) ∼ g(n) se lim_{n} f(n)/g(n) = 1.

Suponha agora que ε > 0 é um número real fixo. Podemos dizer que a soma em (11) está ‘exponencialmente concentrada’ nos termos com k satisfazendo

|k − \frac{n}{2}| ≤ εn,  (14)

pois

∑′_{k} \binom{n}{k} ≤ 2^{n} exp\{−c_{ε}n\},  (15)

onde ∑′_{k} indica soma sobre todos os k para os quais (14) não vale, e c_{ε} > 0 é uma constante que depende apenas de ε.

(i) Prove (13). (ii) Prove que a condição de que ω → ∞ é necessária para que (13)

valha. Para tanto, use a fórmula de Stirling. Uma versão desta fórmula é como segue: para todo n ≥ 1, existe α_{n} com 1/(12n + 1) < α_{n} < 1/12n tal que

n! = \sqrt{2πn} (\frac{n}{e})^{n} e^{α_{n}}

= \sqrt{2πn} (\frac{n}{e})^{n} (1 + \frac{1}{12n} + O (\frac{1}{n^{2}} )) . (16)

Use (16) para provar que se k = k(n) = n/2+c_{n}\sqrt{n}, onde c_{n} → c (n → ∞) e c é uma constante, então

\binom{n}{k} = \frac{n!}{k!(n − k)!} ∼ \frac{d}{\sqrt{n}}2^{n},  (17)

onde d = d(c) > 0 é uma constante que depende apenas de c. (iii) Prove (15). {Data de entrega: 25/9/2000} 12. Para todo N, definimos R_{N} ⊂ 2^{[N]} como sendo o hipergrafo cujos

membros são as progressões aritméticas contidas em [N]. Ademais, pomos

dev(R_{N}) = min_{f} max_{P} | ∑_{x∈P} f(x)|,  (18)

onde o mínimo é tomado sobre todas as funções f: [N] → {±1} e o máximo é tomado sobre todos membros P ∈ R_{N}. Prove que existem c > 0 e N_{0} ≥ 1 tais que

dev(R_{N}) ≤ c(N log N)^{1/2}  (19)

para todo N ≥ N_{0}. {Data de entrega: 25/9/2000}

13. Seja 0 < η < 1 um número real fixo. Mostre que existe uma constante c = c(η) > 0 para o qual vale o seguinte. Para todo ε > 0, existe um inteiro N_{0} = N_{0}(η, ε) ≥ 1 tal que se N ≥ N_{0}, então existe A ⊂ [N] tal que (i) ||A| − ηN| ≤ εηN e (ii) para toda progressão aritmética P ∈ R_{N}, temos

||P ∩ A| − η|P || ≤ c(N log N)^{1/2}.  (20)

{Data de entrega: 25/9/2000}

14. Mostre que existem constantes absolutas c > 0 e N_{0} ≥ 1 para os quais

temos

dev(R_{N}) ≥ cN^{1/4}  (21)

para todo N ≥ N_{0}. Use o teorema de Roth (veja Teorema 25A de Beck e Chen) que afirma que o ‘desvio’ em (20) (isto é, o lado esquerdo daquela desigualdade) é ≥ c′(η(1 − η))^{1/2}N^{1/4} (c′ > 0) para algum P = P_{A} ∈ R_{N} para todo A ⊂ [N] com |A| = ηN. Para tanto, considere M = 2N e se f: [N] → {±1}, considere A ⊂ [M] tal que A ∩ [N] = {x ∈ [N]: f(x) = +1} e A ∩ ([M] \ [N]) = {x ∈ [M] \ [N]: f(x − N) = −1}. {Data de entrega: 25/9/2000}

15. Suponha que as variáveis aleatórias X_{1}, …, X_{n} assumem apenas um número finito de valores. Dizemos que estas variáveis são independentes se para todo I ⊂ [n], e para toda família (R_{i})_{i∈I} com R_{i} ⊂ ℝ (i ∈ I), temos

ℙ (X_{i} ∈ R_{i} para todo i ∈ I) = ∏_{i∈I} ℙ (X_{i} ∈ R_{i}) .  (22)

(i) Suponha que as variáveis aleatórias X_{1}, …, X_{n} como acima são independentes. Deduza que

𝔼 ( ∏_{i∈I} X_{i}) = ∏_{i∈I} 𝔼 (X_{i}) .  (23)

(ii) Suponha que X_{1}, …, X_{n} sejam variáveis aleatórias independentes, que assumem valores em {±1}, e com 𝔼(X_{i}) = 0 para todo 1 ≤ i ≤ n. Mostre que o espaço Ω em que estas variáveis aleatórias estão definidas precisa satisfazer |Ω| ≥ 2^{n}. A hipótese de que estas variáveis tenham esperança nula é essencial? {Data de entrega: 25/9/2000}

16. Dizemos que as variáveis aleatórias X_{1}, …, X_{n} sao k-a-k independentes se, para todo I ⊂ [n] com |I| = k, as variáveis X_{i} (i ∈ I) formam uma família de k variáveis independentes.

(i) Fixe k ≥ 1 e n = 2^{k}. Construa um espaço de probabilidade (Ω, ℙ) com |Ω| = n e variáveis aleatórias X_{1}, …, X_{n−1} definidas sobre Ω, tomando valores em {±1}, duas-a-duas independentes, e com 𝔼(X_{i}) = 0 para todo 1 ≤ i < n. [Sugestão. Considere as matrizes

(\begin{matrix}+ & + \\ + & − \end{matrix}) ,  (\begin{matrix}+ & + & + & + \\ + & − & + & − \\ + & + & − & − \\ + & − & − & + \end{matrix}) ,  etc.

Calcule o quadrado das matrizes acima.] (ii) Suponha que X_{1}, …, X_{n−1} é uma seqüência de variáveis ale-

atórias definidas sobre (Ω, ℙ), com |Ω| = n = 2^{k} e k ≥ 1 é um inteiro. Suponha que, para um certo inteiro ℓ, a família X_{i} (1 ≤ i < n) é uma família de variáveis aleatórias ℓ-a-ℓ independentes. Dê um limitante superior para ℓ.

(iii) Suponha que X_{1}, …, X_{m} é uma seqüência de variáveis aleatórias definidas sobre Ω, com |Ω| = n, tomando valores em {±1}, duasa-duas independentes, e com 𝔼(X_{i}) = 0 para todo 1 ≤ i ≤ m. Mostre que m < n. [Sugestão. Considere o espaço vetorial sobre ℝ das funções reais definidas em Ω. Observe que ⟨X_{i}, X_{j}⟩ = |Ω| 𝔼(X_{i}X_{j}), onde ⟨f, g⟩ denota o produto escalar canônico. Prove que, devido às hipóteses sobre os X_{i}, temos que a variável constante igual a 1 e os X_{i} (1 ≤ i ≤ m) são linearmente independentes.]

{Data de entrega: 25/9/2000}

17. Sejam Y_{1}, …, Y_{n} variáveis aleatórias independentes com ℙ(Y_{i} = 1) = 1 − ℙ(Y_{i} = 0) = p_{i} (1 ≤ i ≤ n). Ponha Y = ∑_{1≤i≤n} Y_{i}. Seja

p̄ = \frac{1}{n} ∑_{1≤i≤n} p_{i},

e considere uma variável aleatória binomial X de parâmetros n e p̄, isto é, X ∼ Bi(n, p̄).

(i) Use um argumento de convexidade para provar que

\begin{aligned}𝔼(e^{uY}) & = ∏_{1≤i≤n} (1 + p_{i}(e^{u} − 1)) \\ & ≤ (1 + p̄(e^{u} − 1))^{n} = 𝔼(e^{uX}) \end{aligned}  (24)

para todo u ∈ ℝ.

(ii) Deduza de (24) que se μ = 𝔼(Y), então, para todo 0 ≤ t ≤ n−μ, temos

ℙ (Y ≥ 𝔼(Y) + t) ≤ (\frac{μ}{μ + t})^{μ+t} (\frac{n − μ}{n − μ − t})^{n−μ−t} .

Note que podemos portanto concluir as desigualdades

ℙ (Y ≥ 𝔼(Y) + t) ≤ exp (−\frac{t^{2}}{2(μ + t/3)})  (25)

e

ℙ (Y ≤ 𝔼(Y) − t) ≤ exp (−\frac{t^{2}}{2μ})  (26)

para todo t ≥ 0. Ademais, para todo 0 ≤ ε ≤ 3/2, temos

ℙ (|Y − 𝔼(Y)| ≥ ε 𝔼(Y)) ≤ 2 exp (−\frac{ε^{2}}{3} 𝔼(Y)) .  (27)

(Não é necessário deduzir (25)–(27) explicitamente.) {Data de entrega: 2/10/2000}

18. Dado um conjunto A = {a_{1} < a_{2} < … } ⊂ ℕ, escrevemos f_{A}(n) para o número de pares (i, j) tais que i < j e a_{i} + a_{j} = n (n ∈ ℕ). Ademais, pomos A(n) = #{a ∈ A: a ≤ n}. Seja 0 < ε < 1/2 um número real fixo. Mostre que existe um conjunto A satisfazendo as seguinte duas condições: (P_{1}) Temos

lim_{n→∞} A(n)n^{−1/2+ε} = ∞.  (28)

(P_{2}) Existe uma constante C = C(ε) para a qual temos

f_{A}(n) ≤ C para todo n ≥ n_{0},  (29)
onde n_{0} = n_{0}(A) é uma constante.

Este é um resultado de Erdős e Rényi. {Data de entrega: 2/10/2000} 19. Seja k um inteiro arbitrário. Mostre que existem grafos G com

χ_{3}(G) > k

livres de K_{−}^{4}, o grafo completo com 4 vértices com uma aresta removida. Nesta questão, estamos usando a notação da Questão 8. Note que aqui provamos algo mais forte que o resultado daquela questão. [Sugestão. Use a desigualdade de Janson e aprecie o poder deste resultado.] {Data de entrega: 2/10/2000}

20. Suponha que H seja uma família 2-universal de funções h: U → T; isto é, para todo (x, y) ∈ U × U e para todo (z_{1}, z_{2}) ∈ T × T, temos

ℙ_{h∈_{R}H} ((h(x), h(y)) = (z_{1}, z_{2})) = \frac{1}{t^{2}} ,

onde t = |T |. Acima, o índice ‘h ∈_{R} H’ indica que a probabilidade é tomada sobre uma escolha uniforme de um membro h de H.

(i) Prove que para todo x ∈ U e para todo z ∈ T, temos

ℙ_{h∈_{R}H}(h(x) = z) = \frac{1}{t}.

(ii) Fixe x, y ∈ U e seja B ⊂ T. Ponha Z_{w} = [h(w) ∈ B] para w ∈ {x, y}, onde [P] = 1 se P ocorre e [P] = 0 caso contrário. Prove que

Cov(Z_{x}, Z_{y}) = 𝔼(Z_{x}Z_{y}) − 𝔼(Z_{x}) 𝔼(Z_{y}) = 0

se x ≠ y. (iii) Seja A ⊂ U e ponha Z = ∑_{x∈A} Z_{x}, onde a notação é como

em (ii). Determine 𝔼(Z) e Var(Z). {Data de entrega: 30/10/2000}

21. Suponha que H seja uma família 2-universal de funções h: U → T. Sejam dados A ⊂ U e B ⊂ T e ε > 0. Dizemos que h ∈ H é (A, B, ε)- bom se

| ℙ_{x∈_{R}U} (x ∈ A e h(x) ∈ B) − μ(A)μ(B)| ≤ ε,

onde μ(A) = |A|/|U| e μ(B) = |B|/|T |. Prove que, para quaisquer A, B, e ε > 0 como acima, temos

ℙ_{h∈_{R}H} (h é (A, B, ε)-bom) ≥ 1 − \frac{μ(A)μ(B)(1 − μ(B))}{ε^{2}|U|}.

[Sugestão. Use os resultados da Questão 20.] {Data de entrega: 30/10/2000}

22. No que segue, pomos Σ = {0, 1}. Uma linguagem L ⊂ Σ^{∗} pertence à classe RP se existem uma constante c_{SIM} > 0 , um polinômio r(n) = r_{L}(n), e um predicado q(x, y) = q_{L}(x, y) verificável em tempo polinomial para os quais temos que se x ∈ L, então |W_{x}| ≥ c_{SIM}2^{n} e se x ∉ L, então W_{x} = ∅, onde

W_{x} = {y ∈ Σ^{r}: q(x, y) = 1},  (30)

r = r(n), e n = |x| é o comprimento de x. Mostre que se L ∈ RP e ε > 0 é uma constante positiva, então existe um algoritmo probabilístico de tempo polinomial A para o qual temos que

se x ∈ L então ℙ(A(x) = 1) ≥ 1 − ε,  (31)

e

se x ∉ L então ℙ(A(x) = 0) = 1.  (32)

Formalmente, um algoritmo probabilístico de tempo polinomial A é uma máquina de Turing com duas fitas de entrada que admite um polinômio r(n) = r_{A}(n) que se comporta como segue: A recebe um par de palavras x e y ∈ Σ^{∗} como entrada, com cada palavra em uma fita, com |y| = r(|x|); a máquina A devolve 0 ou 1 em tempo polinomial em |x| + |y|. Para cada n ≥ 0, consideramos Σ^{r}, onde r = r(n), como um espaço de probabilidade uniforme. (Intuitivamente, x é a instância e y ∈ {0, 1}^{r(|x|)} é um string de ‘bits aleatórios.’) Podemos considerar os eventos ‘A(x, y) = u’ (u ∈ {0, 1}). Assim, por exemplo, a probabilidade que ocorre em (31) é

ℙ_{y∈_{R}Σ^{r}}(A(x, y) = 1).

{Data de entrega: 30/10/2000}

23. Uma linguagem L ⊂ Σ^{∗} pertence à classe BPP se existem constantes 0 ≤ c_{NAO} < c_{SIM} ≤ 1, um polinômio r(n) = r_{L}(n), e um predicado q(x, y) = q_{L}(x, y) verificável em tempo polinomial para os quais temos que se x ∈ L, então |W_{x}| ≥ c_{SIM}2^{r} e se x ∉ L, então |W_{x}| ≤ c_{NAO}2^{r}, onde W_{x} é como em (30). Mostre que se L ∈ BPP e ε > 0 é uma constante positiva, então existe um algoritmo probabilístico de tempo polinomial A para o qual temos que

se x ∈ L então ℙ(A(x) = 1) ≥ 1 − ε,  (33)

e

se x ∉ L então ℙ(A(x) = 0) ≥ 1 − ε.  (34)

{Data de entrega: 30/10/2000}

24. Defina a classe BPP′′ como sendo a família das linguagens L ∈ Σ^{∗} que admitem um polinômio r(n) e um predicado q(x, y) para os quais temos que se x ∈ L, então |W_{x}| > (1/r)2^{r} e se x ∉ L, então |W_{x}| ≤ (1/r^{2})2^{r}. Mostre que BPP = BPP′′. {Data de entrega: 30/10/2000}