Introdução aos Processos Estocásticos Teoremas
Eduardo M. A. M. Mendes
DELT - UFMG
Programa de Pós-Graduação em Engenharia Elétrica
Universidade Federal de Minas Gerais
[email protected]
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
1 / 30
Motivação
1) Lei dos Grandes Números - Justifica a interpretação de “frequência
relativa” relativa da probabilidade.
Exemplo: Lança-se uma moeda 1.000.000 vezes e conta-se o número
de caras.
número de caras
= 0, 4999
1.000.000
Logo
P[caras] = 0, 5
≈ frequência relativa
= frequência relativa quando N → ∞
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
2 / 30
Motivação (cont.)
2) Teorema do Limite Central - justifica a suposição de distribuição
gaussiana dos resultados.
Exemplo: Uma pessoa escolhida aleatoreamente → medida do peso.
P = Peso Genético + Stress no Trabalho + Dieta + Educação + . . .
ou seja, uma variedade de fatores que podem influenciar.
Em princı́pio temos a necessidade de ter a modelagem das várias VAs.
O TLC diz
X1 + X2 + · · · + XN ∼ Gaussiana quando N → ∞
para Xi IID.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
3 / 30
Leis dos Grandes Números
Definição: Se um evento de probabilidade p é observado repetidamente em
ocasiões independentes, a proporção da freqüência observada deste evento
em relação ao número total de repetições converge em direção a p à
medida que o número de repetições se torna arbitrariamente grande.
Lei Fraca dos Grandes Números - Dada uma variável aleatória X, a
sua média amostral converge em probabilidade para o seu valor
esperado.
Lei Forte dos Grandes Números - Dada uma variável aleatória X, a sua
média amostral converge quase certamente para o seu valor esperado.
Obs.: Se a variável aleatória não tem média, a Lei dos Grandes Números
não se aplica.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
4 / 30
Leis dos Grandes Números (cont.)
Considere o lançamento de uma moeda não viciada várias vezes. Os
resultados são
X1 , X2 , X3 , . . . , XN , . . .
Xi
= 1 se cara
= 0 se coroa
Assuma que Xi é IID, ou seja:
1) Independentes - o lançamento de uma moeda não “depende” do
i ∩Xi−1 )
lançamento anterior, ou seja, P(Xi |Xi−1 ) = P(X
P(Xi−1 ) = P(Xi ).
2) Identicamente Distribuı́dos - A mesma moeda é usada e lançada de
uma mesma maneira toda vez. A lei de distribuição é mantida.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
5 / 30
Leis dos Grandes Números (cont.)
O resultado aleatório do experimento pode ser modelado por
T
X = X1 X2 · · · XN
e a PMF
pXi [k] = pX [k] =
1
2
1
2
k=0
k=1
Seja
X̄ =
N
1 X
Xi
N
i=1
para N = 2 → X̄ =
1
2
(X1 + X2 ). X̄ = 0, 12 , 1, . . . possui uma PMF.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
6 / 30
Leis dos Grandes Números (cont.)
Calculando o valor esperado da nova variável aleatória (N qualquer),
temos:
#
"
N
1 X
Xi
EX [X̄ ] = EX
N
i=1
=
1
N
N
X
EX Xi
i=1
N
X
=
1
N
=
1
N
=
N
1 X1
1
=
N
2
2
EXi Xi
i=1
N X
0×
i=1
1
1
+1
2
2
i=1
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
7 / 30
Leis dos Grandes Números (cont.)
Var (X̄ ) = Var
N
1 X
Xi
N
!
i=1
=
1
N2
N
X
i=1
Var (
Xi
)
|{z}
Independentes
mas
Var (Xi ) = EXi (Xi2 ) − EX2i (Xi )
1
1
= 0 × + 12 × −
2
2
1 1
1
=
− =
2 4
4
2
2
1
2
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
8 / 30
Leis dos Grandes Números (cont.)
logo
Var (X̄ ) =
N
1
1 X1
4
=
N2
4
N
i=1
quando N → ∞ → Var (X̄ ) = 0. Lei dos Grandes Números - Veja
probprob15.1.r.
P
Seja X̄N = N1 N
i=1 Xi
X̄N →
1
= EX [X ]
2
quando N → ∞
Em geral, a Lei dos Grandes Números diz que, para VAs IID,
N
1 X
Xi → EX [X ]
N
quando N → ∞
i=1
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais emmendes
9 / 30
Leis dos Grandes Números (cont.)
e
Ê (g (X )) =
N
1 X
g (Xi )
N
i=1
Teorema: Se X1 , X2 , . . . , XN são IID com média EX (x) e variância σ 2
então
lim X̄N
N→∞
= EX (x)
ou
lim P |X̄N − EX (x)| > = 0
N→∞
para qualquer > 0 pequeno, ou seja, convergência em probabilidade
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 10
emmendes
/ 30
Leis dos Grandes Números (cont.)
Prova 1: Considere




P |X̄N − EX (x)| > = P | X̄N − EX̄ (X̄N ) | > 
|{z} | {z }
Y
E (Y )
Usando a desigualdade de Chebyshev
P [|Y − E (Y )| > ] ≤
mas Var (Y ) = Var (X̄N ) =
Logo
Var (Y )
2
σ2
N.
σ2
N
2
σ2
N2
σ2
lim P |X̄N − EX (x)| > ≤ lim
=0
N→0
N→∞ N2
P |X̄N − EX (x)| > ≤
=
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 11
emmendes
/ 30
Leis dos Grandes Números (cont.)
Prova 2: Usando a expansão de séries de Taylor para funções complexas,
sabemos que a função caracterı́stica de uma variável aleatória X com
média finita pode ser escrita como
φX (ω) = 1 + iωE (X ) + o(ω),
t→0
Repare que todas as variáveis X1 , X2 , X3 , . . . têm a mesma função
caracterı́stica. Usando propriedades da função caracterı́stica podemos
escrever
ω
φ 1 X (ω) = φX
e φX +Y (ω) = φX (ω)φY (ω),
N
N
se X e Y independentes, temos
h ω iN h
ω iN
ω
φX̄ (ω) = φX
= 1 + iE (X ) + o
→ e iωE (X ) ,
N
N
N
quando
N → ∞.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 12
emmendes
/ 30
Leis dos Grandes Números (cont.)
Repare que o limite e iωE (X ) é a função caracterı́stica de uma variável
aleatória constante E (X ) e assim
D
X̄ −→ E (X )
para n → ∞
Mas como a variável é constante, a convergência em distribuição é
equivalente à convergência em probabilidade, logo
P
X̄ −→ E (X )
Exemplo: Determinar se um sinal S = A (constante) está presente em
meio à contaminação por ruı́do.
Xi = s + wi = A + wi
i = 1, 2, . . .
para W sendo IID com Ew (w ) = 0 e Var (W ) = σ 2 < ∞.
X̄N → EX (x) = A quando N → ∞
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 13
emmendes
/ 30
Leis dos Grandes Números (cont.)
Quando não há sinal
X̄N → EX (x) = EW (w ) = 0
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 14
emmendes
/ 30
Teorema do Limite Central
A Lei dos Grandes Números dá informação sobre a largura e localização da
PDF/PMF de X̄N .
largura → 0
localização → EX (x)
E sobre a PDF quando N → ∞?
Exemplo:
Xi
1 1
é IID e Xi ∼ U − ,
2 2
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 15
emmendes
/ 30
Teorema do Limite Central (cont.)
2
(b−a)
com E (x) = a+b
2 e Var (x) =
12 . A PDF de X1 e X2 é obtida pela
convolução da PDF de X1 com a PDF de X2
pS2
= pX (x) ∗ pX (x)
pS3
= pX (x) ∗ pX (x) ∗ pX (x)
Podemos, então, calcular
3
X
!
1 1
E (S3 ) = E
Xi = 0 Xi ∼ U − ,
2 2
i=1
!
3
X
1
Var (S3 ) = Var
Xi = 3Var (Xi ) = 3
12
i=1
que é uma boa aproximação para a Gaussiana (repare que a média é zero).
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 16
emmendes
/ 30
Teorema do Limite Central (cont.)
Exemplo: Quando E (X ) 6= 0. Considere
SN =
N
X
Xi
∼ U(0, 1)
i=1
logo
E (X ) =
Var (X ) =
a+b
1
= =
6 0
2
2
(b − a)2
1
=
12
12
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 17
emmendes
/ 30
Teorema do Limite Central (cont.)
O valor esperado é
E (SN ) = E
N
X
!
Xi
i=1
=
N
X
E (Xi ) = NE (X )
i=1
= N×
1
N
=
2
2
Var (SN ) = NVar (X ) =
→ “anda” com o valor de N.
N
12
Repare que
N ↑→
E (SN ) ↑ e Var (SN ) ↑
É necessário normalizar, ou seja, E (•) = 0 e Var (•) = 1
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 18
emmendes
/ 30
Teorema do Limite Central (cont.)
Zn =
=
SN − E (SN )
p
Var (SN )
SN − NEX (X )
p
NVar (X )
A PDF da soma normalizada de um grande número de VAs contı́nuas IID
convergirá para uma PDF Gaussiana.
N→∞
→
Zn ∼ N(0, 1)
Teorema: Se X1 , X2 , . . . , XN são VAs contı́nuas IID com média EX (X ) e
variância Var (X ) então para N → ∞.
PN
X
i=1
p i
− NEX (X )
NVar (X )
→ N(0, 1)
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 19
emmendes
/ 30
Teorema do Limite Central (cont.)
Exemplo: Dado Xi ∼ N(0, 1), examine PDF de Y =
N → ∞. A verdadeira PDF é Y ∼ χ2N .
PN
2
i=1 Xi
quando
Para aplicar TLC precisamos verificar
a) Independência - X1 , X2 , . . . , XN são independentes logo X12 , X22 , . . . , XN2
são independentes.
b) Identicamente distribuidos - X1 , X2 , . . . , XN têm a mesma PDF logo
X12 , X22 , . . . , XN2 têm a mesma PDF.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 20
emmendes
/ 30
Teorema do Limite Central (cont.)
PN
X 2 − NE (X 2 )
i=1
p i
=?
NVar (X 2 )
com
2
X ∼
χ21
→
EX (X 2 ) = 1
Var (X 2 ) = 2
Normalizando temos
PN
Zn =
X2
i=1
√ i
2N
−N
→ N(0, 1)
e
√
Zn
|{z}
N(0,1)
2N + N =
N
X
Xi2
i=1
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 21
emmendes
/ 30
Teorema do Limite Central (cont.)
Logo
N
X
Xi2 ∼ N(N, 2N)
i=1
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 22
emmendes
/ 30
Esboço da Prova do TLC
N −NEX (X )
Seja Zn = S√
. Para Zn → N(0, 1), vamos usar a função
NVar (X )
caracterı́stica
1
φZN (ω) → φZ (ω) = e − 2 ω
2
Portanto
φZN (ω) = EZN e ωZN
" PN X −NE
= EX e
=
N
Y
ω
EXi e
X (Xi )
i=1
√ i
NVar (Xi )
X −EX (Xi )
NVar (Xi )
ω √i
#
i=1
X −EX (X ) N
ω √
NVar (X )
= EX e
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 23
emmendes
/ 30
Esboço da Prova do TLC (cont.)
Olhando para EX e
X −EX (X )
ω √
X −EX (X ) ω √
NVar (X )
EX e
NVar (X )
, temos

!k 
∞
k
X
(ω)
X − E (X )

p
=
EX 
|{z}
k!
NVar
(X
)
k=0
séries

!k 
∞
k
X
(ω)
X − E (X )

=
EX  p
k!
NVar
(X
)
k=0
"
#
X − E (X )
=
1 + ωEX p
+
NVar (X )

!2 
1
X − E (X )
 + ...
(ω)2 EX  p
2
NVar (X )
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 24
emmendes
/ 30
Esboço da Prova do TLC (cont.)
Mas
"
#
X − E (X )
EX p
= 0
NVar (X )

!2 
EX (X − E (X ))2
X − E (X )
1


p
EX
=
=
NVar (X )
N
NVar (X )
Desconsiderando os termos de alta-ordem
1
1 N
1 + (ω)2
2
N
N
1 2
1 ω2
=
1−
→ e − 2 ω quando N → ∞
2N
φZN (ω) =
= φZ (ω), Z ∼ N(0, 1).
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 25
emmendes
/ 30
Observações sobre o TLC
O resultado do TLC pode ser escrito como
! Z
u2
1
x − NE (X )
2
√ e −x dx,
≤ u2 =
lim P u1 ≤ p
N→∞
2π
NVar (X )
u1
para todo u1 e u2 finitos.
Note que, para N finito, a distribuição da soma
X = X1 + X2 + . . . + XN pode ser bem diferente da Gaussiana no que
se refere às caudas. Entretanto o peso dessas regiões não-gaussianas
tendem a zero quando N tende a infinito.
O TLC se preocupa mais com a região central que tem um peso finito
para N grande.
As principais hipóteses que asseguram a validade do TLC Gaussiano são:
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 26
emmendes
/ 30
Observações sobre o TLC (cont.)
Os Xi têm que ser variáveis aleatórias independentes, ou pelo menos
não muito correlacionadas (a função de correlação deve ter um
decaimento suficiente rápido quando |i − j| se torna grande).
As variáveis aleatórias Xi não precisam ser necessariamente
identicamente distribuı́das. O que deve acontecer é que a variância de
todas essas distribuições não sejam muito diferentes tal que não haja
dominância de uma destas variâncias sobre as outras.
X = a1 X1 + a2 X2 + . . . + aN XN
onde ai são coefientes arbitrários.
Formalmente o TLC só é aplicado quando N tende a infinito. Na
prática N é finito e deve ser grande suficiente para que a parte central
da distribuição seja parecida com a Gaussiana. O valor mı́nimo de N
para que isso aconteça depende da distribuição de Xi , sua distância
para a Gaussiana e de quanto a Gaussiana pode aproximar as caudas.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 27
emmendes
/ 30
Observações sobre o TLC (cont.)
o TLC não diz nada sobre as caudas da distribuição de X mas
somente que a região central da distribuição poder ser bem descrita
por
√ uma Gaussiana. A região central é uma região com pelo menos
Nσ em torno da média de X. A largura da região que pode ser bem
aproximada pela Gaussiana depende da distribuição de X .
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 28
emmendes
/ 30
TLC e Teoria da Informação
A quantidade I denominada Entropia (quantidade de informação faltante
ou perdida) associada à função de distribuição de probabilidade P é
definida como
Z
I(P) = − P(x)log (P(x))dx
A distribuição que maximiza I(P) para um dado valor de variância é
obtida tomando a derivada funcional com respeito a P(x)
Z
Z
∂
02
0
0
0
0
0
I(P) − ξ x P(x )dx − ξ
P(x )dx = 0
∂P(x)
R
onde ξ é fixado pela condição x 2 p(x)dx = σ 2 e ξ 0 pela normalização de
P(x). A solução da igualdade acima é a Gaussiana.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 29
emmendes
/ 30
TLC e Teoria da Informação (cont.)
O valor númerico da Entropia para a Gaussiana é:
IG =
1 1
+ log(2π) + log(σ) ≈ 1, 419 + log(σ)
2 2
O valor númerico da Entropia para a Exponencial é:
IE = 1 +
log 2
+ log(σ) ≈ 1, 346 + log(σ)
2
Observe que a operação de convolução (soma de variáveis) é uma
operação de queima de informação, pois todos os detalhes da distribuição
elementar vão sendo perdidos até que a Gaussiana surja.
A Gaussiana é a lei da máxima entropia ou mı́nima informação.
Eduardo Mendes (DELT - UFMG Programa de Pós-Graduação MACSIN
em Engenharia Elétrica Universidade Federal de Minas Gerais 30
emmendes
/ 30