Tópico: Contando triângulos ‣ Capítulo 3 Somas de variáveis independentes ‣ Notas de aula: Probabilidade I

Vimos como a Lei Fraca dos Grandes Números seguiu de uma estimativa de segundo momento (mais precisamente usando a variância).

Nessa seção iremos mostrar como esse método é mais geral, se aplicando mesmo em situações onde as variáveis não são necessariamente independentes duas a duas.

Seja $V_{n}=\{1,\dots,n\}$ com $n\geq 3$ e $\mathcal{E}_{n}=\big{\{}\{x,y\}\subseteq V_{n};x\neq y\big{\}}$ . Chamamos o par $(V_{n},\mathcal{E}_{n})$ de grafo completo em $n$ vértices.

Definimos em um certo espaço de probabilidade $P_{n}$ , as variáveis aleatórias $(X_{e})_{e\in\mathcal{E}_{n}}$ de maneira \iidcom distribuição $\Ber(p)$ , onde $p\in[0,1]$ . Essas variáveis induzem um subgrafo aleatório $(V_{n},\mathcal{E}_{n}^{\prime})$ , onde

\mathcal{E}_{n}^{\prime}=\big{\{}e\in\mathcal{E}_{n};X_{e}=1\big{\}}.

(3.39)

Dizemos que os elos $e$ , tais que $X_{e}=1$ são abertos.

Definimos nesse espaço a variável aleatória

T_{n}=\#\big{\{}\text{tri\^{a}ngulos em $(V_{n},\mathcal{E}_{n}^{\prime})$}% \big{\}}.

(3.40)

Essa variável claramente pode ser escrita como

T_{n}=\sum_{x,y,z\in V_{n}\text{ distintos}}\1_{A_{\{x,y,z\}}},

(3.41)

onde $A_{\{x,y,z\}}=\big{[}\text{\{x,y,z\} formam um tri\^{a}ngulo em $(V_{n},% \mathcal{E}_{n}^{\prime})$}\big{]}$ .

Gostaríamos de entender algo sobre a distribuição de $T_{n}$ e começamos calculando

\begin{split}E^{n}(T_{n})&=\sum_{\{x,y,z\}\text{ distintos}}P^{n}(A_{\{x,y,z\}% })\\ &=\binom{n}{3}p^{3}=\frac{n(n-1)(n-2)}{6}p^{3}.\end{split}

(3.42)

Logo, $P[T_{n}>a]\leq n(n-1)(n-2)p^{3}/6a$ . Mais ainda,

\begin{split}E^{n}(T_{n}^{2})&=\sum_{\{x,y,z\}\text{ distintos}}\quad\sum_{\{x% ^{\prime},y^{\prime},z^{\prime}\}\text{ distintos}}P^{n}(A_{\{x,y,z\}}\cap A_{% \{x^{\prime},y^{\prime},z^{\prime}\}})\\ &=\underbrace{\binom{n}{6}\binom{6}{3}p^{6}}_{\text{todos distintos}}+% \underbrace{\binom{n}{5}\binom{5}{3}\binom{3}{1}p^{6}}_{\text{$1$-comum}}+% \underbrace{\binom{n}{4}\binom{3}{2}\binom{4}{3}p^{5}}_{\text{$2$ em comum}}+% \underbrace{\binom{n}{3}p^{3}}_{\text{iguais}}\end{split}

(3.43)

Donde

\Var^{n}(T_{n})=\frac{1}{36}n^{6}p^{6}-\frac{1}{36}n^{6}p^{6}+cn^{5}p^{5}+...% \leq c(n^{5}p^{5}+n^{3}p^{3}),

(3.44)

para todos $p\in[0,1]$ e $n\geq 1$ se escolhemos bem a constante $c>0$ .

Isso nos permite por exemplo estimar o que acontece em alguns regimes, como por exemplo, se $p=1/2$ , então

E^{n}(T_{n})=\frac{n(n-1)(n-2)}{48},

(3.45)

que cresce como $n^{3}$ , e $\Var^{n}(T_{n})\leq cn^{5}$ , logo

P^{n}\Big{[}\Big{|}T_{n}-E^{n}(T_{n})\Big{|}>\varepsilon n^{3}\Big{]}\leq\frac% {\Var^{n}(T_{n})}{\varepsilon^{2}n^{6}}\leq\frac{c}{\varepsilon^{2}n}.

(3.46)

\todosec

Tópico: Análise de DNAfazer "computational molecular biology- Pevzner seção 5.5…

\todosec

Tópico: Método Probabilístico Revisitadousando segundo momento agora