DesigualdadeBonferroni-Morais-2016

Prévia do material em texto

Universidade Federal do Rio Grande do Norte
Coordenação do Curso de Curso de Especialização em Ensino da
Matemática Para o Ensino Médio
Ionara Priscila da Silva Morais
DESIGUALDADE DE BONFERRONI
MARTINS-RN
2016
Ionara Priscila da Silva Morais
DESIGUALDADE DE BONFERRONI
Monografia apresentada ao Curso de Matemática
da SEDIS, como requisito para a obtenção parcial
do grau de LICENCIADO em Matemática.
Orientador: Iesus Carvalho Diniz
Doutor
MARTINS-RN
2016
Morais, Ionara
DESIGUALDADE DE BONFERRONI / Ionara Morais - 2016
xx.p
. I.T́ıtulo.
CDU xxx.xx
Ionara Priscila da Silva Morais
DESIGUALDADE DE BONFERRONI
Monografia apresentada ao Curso de Matemática
da SEDIS, como requisito para a obtenção parcial
do grau de LICENCIADO em Matemática.
Aprovado em 17 de julho de 2016
BANCA EXAMINADORA
Iesus Carvalho Diniz
Doutor
Danielle de Oliveira N. Vicente
Especialista
Odilon Júlio dos Santos
Mestre em Matemática
Dedico este trabalho com muito orgulho a mi-
nha mãe Iraci Antonia da Silva Morais, pois
é um exemplo de pessoa, de mãe e de profissi-
onal da qual quero seguir.
Agradecimentos
Agradeço a Deus em primeiro lugar por me proporcionar conhecimento e sabe-
doria para chegar até aqui, por sua segurança me protegendo durante essa longa trajetória
que percorri. Pela fé e esperança que nunca deixou eu desisti. A minha mãe Iraci Antonia
pelo incentivo de sempre, a compreensão e a dedicação em me ajudar nos momentos que
mais necessito. Um agradecimento especial ao meu esposo Agrimarildo Moreira, compa-
nheiro ativo. Agradeço por sua compreensão durante todo esse percurso de estudo. As
minhas irmãs Iara e Itamara por todo o companheirismo e a minha amiga quase irmã Ta-
miris Maria pelo companheirismo e desabafo de choro quando tudo parecia que o mundo
estava desabando sobre a minha cabeça. Agradeço a Iesus por aceitar esse desafio de me
orientar na construção deste trabalho.
Para ser um bom educador é necessário
ter o conhecimento de tudo que envolva
a aprendizagem, humildade, curiosidade
e esṕırito de equipe.
Autor desconhecido
Sumário
INTRODUÇÃO 4
1 Principio da Inclusão e Exclusão. 6
1.1 Desigualdade de Bonferroni. . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 CONSIDERAÇÕES FINAIS 14
Referências Bibliográficas 15
5
INTRODUÇÃO
A desigualdade de Bonferroni é muito importante e está relacionada a outras,
como exemplo ela generalizam a desigualdade de Boole as quais nos permitem obter
limitantes para o número de elementos de um conjunto formado a partir da união ou da
interseção de outros conjuntos. A sua demonstração não é usualmente feita em livros
básicos é consideradas em livros avançados e nesses não são utilizados procedimentos
básicos. Assim sendo uma regra bastante obscuro de probabilidade que pode ser bastante
útil.
6
1 Principio da Inclusão e Exclusão.
Para todo k ∈ {1, ..., n} e {i1, ..., ik} ⊂ {1, ..., n} os subconjuntos de ⊂ {1, ..., n} de tama-
nho k, seja Sk(n) =
∑
1≤i1<i2...<ik≤n
P (Ai1Ai2 ...Aik).
P (∪ni=1Ai) =
n∑
i=1
P (Ai)−
∑
1≤i1<i2≤n
P (Ai1Ai2) +
∑
1≤i1<i2<i3≤n
P (Ai1Ai2Ai3)
+... + (1)n−1P (Ai1A2...An) = S1 − S2 + S3 + ... + (−1)
n−1 Sn (1.1)
Demonstração. Solução: A prova será feita por indução em n.
Se n = 1, tem-se que P (∪ni=1Ai) = P (Ai) = S1.
Tem-se que A1 ∪ A2 = (A1Ac2) ∪ (A1A2) ∪ (Ac1A2). Assim, para n = 2
P (∪2i=2Ai) = P (A1Ac2) + P (A1A2) + P (Ac1A2) = P (A1) - P (A1A2) + P (A1A2) + P (A2)
- P (A1A2) = P (A1) + P (A2) - P (A1A2) =
2∑
i=1
P (Ai)−
2∑
1<i1<i2≤2
P (Ai1Ai2) =S1 − S2.
Como hipótese de indução, admitimos que o resultado vale para k = n, isto é:
P (∪ni=1Ai) =
n∑
k=1
(−1)k−1 Sk = S1 − S2 + S3 + ... + (−1)n−1 Sn (1.2)
Consideremos agora k = n + 1. Tem-se que ∪n+1i=1 A1 = (∪ni=1A1) ∪ An+1. Assim, do caso
n = 2 segue - se que
P
(
∪n+1i=1 A1
)
= P (∪ni=1A1) + P (An+1)− P ((∪ni=1A1)An+1) (1.3)
Da hipótese de indução em (1.3) e do fato que (∪ni=1Ai)An+1 = ∪ni=1Ai (AiAn+1)tem-se
que
P
(
∪n+1i=1 Ai
)
=
n∑
i=1
P (Ai)−
∑
16i1<i2≤n
P (Ai1Ai2) +
∑
16i1<i2<i3≤n
P (Ai1Ai2Ai3) + ...+ (−1)
n−2
∑
16i1<i2...<in−1≤n
P
(
Ai1Ai2 ...Ain−1
)
+ (1)n−1
∑
16i1<i2...<in≤n
P (Ai1Ai2 ...Ain) +
1 Principio da Inclusão e Exclusão. 7
P (An+1) - P (∪ni=1AiAn+1) =
n∑
i=1
P (Ai) + P (An+1) +
-
∑
16i1<i2≤n
P (Ai1Ai2) -
∑
16i≤n
P
(
AiAin+1
)
+
∑
16i1<i2<i3≤n
P (Ai1Ai2Ai3) +
∑
16i1<i2≤n
P
(
Ai1Ai2Ain+1
)
+
1.1 Desigualdade de Bonferroni. 8
(−1)n−2
∑
16i1<i2...<in−1≤n
P
(
Ai1Ai2 ...Ain−1
)
-(−1)n−3
∑
16i1<i2...<in−2≤n
P
(
Ai1Ai2 ...Ain−2An+1
)
+
(−1)n−1
∑
16i1<i2...<in≤n
P (Ai1Ai2 ...Ain)-(−1)
n−2
∑
16i1<i2...<in−1≤n
P
(
Ai1Ai2 ...Ain−1An+1
)
+
(−1)n−1
∑
16i1<i2...<in≤n
P (Ai1Ai2 ...AinAn+1) =
n+1∑
i=1
P (Ai)−∑
16i1<i2<≤n+1
P (Ai1Ai2) +∑
16i1<i2<i3≤n+1
P (Ai1Ai2Ai3) + ...
(−1)n−2
∑
16i1<i2...<in−1≤n+1
P
(
Ai1Ai2 ...Ain−1
)
+(−1)n−1
∑
16i1<i2...<in≤n+1
P (Ai1Ai2 ...Ain) +
(−1)n P
(
Ai1Ai2 ...Ain+1
)
= S1 − S2 +...+ (−1)n+1 Sn.
1.1 Desigualdade de Bonferroni.
Para todo j ∈ {1, ..., n} seja Sj (n) =
∑
16i1<...<ij≤n
P
(
Ai1 ...Aij
)
.
Mostre que:
P
(
∪nj=1Aj
)
≤
k∑
j=1
(−1)j−1 Sj (1.4)
se k for ı́mpar.
P
(
∪nj=1Aj
)
≥
k∑
j=1
(−1)j−1 Sj (1.5)
se k for par.
1.1 Desigualdade de Bonferroni. 9
observação 0.1 Se k = n, então pelo Pŕıncipio da Inclusão e Exclusão tem - se a
igualdade em (1.4) e (1.5).
Demonstração. será feita por indução em n, considerando a paridade de k.
Seja k ı́mpar.
Se k = 1, então devemos mostrar que
P
(
∪nj=1Aj
)
≤ S1 =
n∑
i=1
P (Ai). (1.6)
Consideremos a prova de (1.6) por indução em n, o números de conjuntos.
Se n = 2 o resultado segue - se de imediato, pois
P
(
∪2j=1Aj
)
= P (A1) + P (A2) - P (A1A2) ≤ P (A1) + P (A2) =
2∑
i=1
P (Ai).
Se n = 3, notemos que os conjuntos A1\ (A1A2), A3\ (A1 ∪ A2) e A2 são de
disjuntos e tais que:
(A1 ∪ A2 ∪ A3) = (A1\ (A1A2)) ∪ (A3\ (A1 ∪ A2)) ∪ A2. Assim
P (A1 ∪ A2 ∪ A3) = P (A1\ (A1A2)) + P (A3\ (A1 ∪ A2)) + P (A2) =
P (A1) - P (A1A2) + P (A3) - P (A1 ∪ A2) + P (A2)
≤ P (A1) + P (A2) + P (A3).
Admitamos como hipotese de indução que o resultado é valido para um certo l, i.e.,
P
(
∪lj=1Aj
)
≤ S1
l∑
i=1
P (Ai). (1.7)
e notemos que para l + 1 conjuntos segue-se que
P
(
∪l+1j=1Aj
)
= P
((
∪lj=1Aj
)
∪ Al+1
)
≤ P
(
∪lj=1Aj
)
+ P (Al+1)
1.1 Desigualdade de Bonferroni. 10
≤(1.7)
l∑
j=1
P (Aj) + P (Al+1) =
l+1∑
j=1
P (Aj).
Consideremos k ı́mpar e menor que n. Admitimos como hipotese de indução
que os resultados de (1.4) e (1.5) valem para um certo número l de conjuntos.
P
(
∪li=1Ai
)
≤
∑
1≤i≤l
P (Ai)−
∑
1≤i1<i2≤l
P (Ai1Ai2) +
∑
1≤i1<i2<i3≤l
P (Ai1Ai2Ai3) + ... +
(−1)k−2
∑
1≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1
)
+ (−1)k−1
∑
1≤i1<...<ik−1≤l
P (Ai1 ...Aik) (1.8)
P
(
∪li=1Ai
)
≥
∑
1≤i≤l
P (Ai)−
∑
1≤i1<i2≤l
P (Ai1Ai2) +
∑
1≤i1<i2<i3≤l
P (Ai1Ai2Ai3) + ... +
(−1)k−2
∑
1≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1
)
. (1.9)
Podemos reescrever (1.8) e (1.9) de maneira mais condensada, usando as
notação Sj(l) que representa a soma das probabilidades das interseções de subfamilias
de j conjuntos dos l conjuntos.
Assim,
P
(
∪li=1Ai
)
≤ S1(l)− S2(l) + S3(l) + ... + (−1)k−2 Sk−1(l) + (−1)k−1 Sk(l). (1.10)
P
(
∪li=1Ai
)
≥ S1(l)− S2(l) + S3(l) + ... + (−1)k−2 Sk−1(l). (1.11)
Acontece que
P
(
∪l+1i=1Ai
)
= P
(
∪li=1Ai ∪ Al+1
)
= P
(
∪li=1Ai
)
+ P (Al+1) - P
((
∪li=1Ai
)
∩ Al+1
)
= P
(
∪li=1Ai
)
+ P (Al+1)− P
(
∪li=1 (Ai ∩ Al+1)
)
(1.12)
≤(0.10) S1(l)- S2(l) + S3(l) +...+ (−1)k−2 Sk−1(l) + (−1)k−1 Sk(l) + P (Al+1)- P
(
∪li=1 (Ai ∩ Al+1)
)
.
1.1 Desigualdade de Bonferroni. 11
tem-se de (1.9) com Ai ∩ Al+1 em lugar de Ai que
P
(
∪li=1 (Ai ∩ Al+1)
)
−
∑
1≤i1<i2≤l
P (Ai1Ai2Al+1) +∑
1≤i1<i2<i3≤l
P (Ai1Ai2Ai3Al+1) + ... + (−1)
k−2
∑
1≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1Al+1
)
. (1.13)
De (1.13) em (1.12) segue-se que
P
(
∪l+1i=1Ai
)
≤(0.10) S1(l)- S2(l) + S3(l) +...+ (−1)k−2 Sk−1(l) + (−1)k−1 Sk(l) + P (Al+1)-
l∑
i=l
P (AiAl+1) -
∑
l≤i1<i2≤l
P (Ai1Ai2Al+1) +
∑
l≤i1<i2<i3≤l
P (Ai1Ai2Ai3Al+1) +
+...+ (−1)k−2
∑
l≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1Al+1
)
= S1(l) + P (Al+1) -
(
S2(l) +
l∑
i=l
P (AiAl+1)
)
+ S3(l) +
∑
l≤i1<i2≤l
P (Ai1Ai2Al+1)-
-
(
S4(l) +
∑
l≤i1<i2<i3≤l
P (Ai1Ai2A3Al+1)
)
+ ... +
...(−1)k−2 Sk−1(l)− (−1)k−3
∑
l≤i1<...<ik−2≤l
P
(
Ai1 ...Aik−2Al+1
)
+
(−1)k−1 Sk−2(l)− (−1)k−2
∑
l≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1Al+1
)
. (1.14)
Observe que
S1(l) + P (Al+1) =
l∑
i=l
P (Ai) + P (Al+1) =
l+1∑
i=l
P (Ai) = S1(l + 1). (1.15)
S2(l) +
l∑
i=1
P (AiAl+1) =
∑
1≤i1<i2≤l
P (Ai1Ai2) +
l∑
i=1
P (AiAl+1) =
=
∑
1≤i1<i2≤l+1
P (Ai1Ai2) = S2(l + 1). (1.16)
1.1 Desigualdade de Bonferroni. 12
S3(l) +
∑
1≤i1<i2≤l
P (Ai1Ai2Al+1) =
∑
1≤i1<i2<i3≤l
P (Ai1Ai2Ai3) +
+
∑
1≤i1<i2≤l
P (Ai1Ai2Al+1) =∑
1≤i1<i2<i3≤l+1
P (Ai1Ai2Ai3) = S3(l + 1). (1.17)
S4(l) +
∑
1≤i1<i2<i3≤l
P (Ai1Ai2Ai3Al+1) =
=
∑
1≤i1<i2<i3<i4≤l
P (Ai1Ai2Ai3Ai4Al+1) +
∑
1≤i1<i2<i3≤l
P (Ai1Ai2Ai3Al+1) = (1.18)
=
∑
1≤i1<i2<i3<i4≤l+1
P (Ai1Ai2Ai3Ai4Al+1) = S4(l + 1).
(−1)k−2 Sk−1(l)− (−1)k−3
∑
1≤i1<...<ik−2≤l
P
(
Ai1 ...Aik−2Al+1
)
=
(−1)k−2 Sk−1(l) + (−1)k−2
∑
1≤i1<...<ik−2≤l
P
(
Ai1 ...Aik−2Al+1
)
= (1.19)
(−1)k−2
(
Sk−1(l) +
∑
1≤i1<...<ik−2≤l
P
(
Ai1 ...Aik−2Al+1
))
= (−1)k−2 Sk−1(l + 1).
(−1)k−1 Sk(l) + (−1)k−2
∑
1≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1Al+1
)
=
(−1)k−1 Sk(l) + (−1)k−1
∑
1≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1Al+1
)
= (1.20)
(−1)k−1
(
Sk(l) +
∑
1≤i1<...<ik−1≤l
P
(
Ai1 ...Aik−1Al+1
))
= (−1)k−1 Sk(l + 1).
De (1.15),(1.16),(1.17),(1.18),...,(1.19) e (1.20) em (1.14) resulta que
P
(
∪l+1j=1
)
≤ S1(l + 1)− S2(l + 1) + S3(l + 1)− S4(l + 1) +...+
+..+(−1)k−2 Sk−1(l + 1) + (−1)k−1 Sk(l + 1).
Demonstração. Seja k par.
Se k = 2, então devemos provar que
P
(
∪nj=1Aj
)
≥ S1 − S2 =
n∑
i=l
P (Ai)−
∑
1≤i1<i2≤n
P (Ai1Ai2). (1.21)
1.1 Desigualdade de Bonferroni. 13
Consideremos a prova (1.21) por indução no número de conjuntos de n. Se n = 2 o
resultado segue-se de imediato. Tem-se neste caso a igualdade.
P
(
∪2j=1Aj
)
= P (A1) + P (A2) - P (A1A2) =
2∑
i=1
P (Ai) -
∑
1≤i1<i2≤2
P (Ai1Ai2).
Se n=3, do Prinćıpio de Inclusão Exclusão segue-se que
P
(
∪3j=1Aj
)
=
3∑
i=1
P (Ai) -
∑
1≤i1<i2≤2
P (Ai1Ai2) + P (A1A2A3).
≥
3∑
i=1
P (Ai) -∑
1≤i1<i2≤2
P (Ai1Ai2) = S1 − S2.
Admitimos como hipóteses de indução que o resultado é válido para um certo l, i.e.,
P
(
∪lj=1Aj
)
≥
l∑
i=1
P (Ai)−
∑
1≤i1<i2≤2
P (Ai1Ai2). (1.22)
Sejam agora os l + 1 conjuntos A1, ..., Al+1. Tem-se que
P
(
∪l+1j=1Aj
)
= P
((
∪lj=1Aj
)
∪ Al+1
)
= P
(
∪lj=1Aj
)
+ P (Al+1) - P
(
∪lj=1Aj
)
=
P
(
∪lj=1Aj
)
+ P (Al+1) - P
(
∪lj=1 (AjAl+1)
)
≥(0.6) P
(
∪lj=1Aj
)
+ P (Al+1) -
l∑
j=1
P (AjAl+1)
≥(0.22)
l∑
j=1
P (Aj) -
∑
1≤j1<j2≤l
P (Aj1Aj2) + P (Al+1) -
l∑
j=1
P (AjAl+1) =
l+1∑
j=1
P (Aj) -
∑
1≤j1<j2≤l+1
P (Aj1Aj2).
14
2 CONSIDERAÇÕES FINAIS
No entanto, o nosso trabalho foi demonstrar a desigualdade de Bonferroni, onde
de inicio utilizamos e mostramos o prinćıpio de inclusão-exclusão que é uma conhecida
aplicação do problema de contar o número de desarranjos de um conjunto finito. Logo
em seguida provemos por indução que é um método de demonstração matemática para
provar a verdade de um número infinito de proposições. Lembrando que a demonstração
por indução segue dois passos, o primeiro é verificar se a paridade é valida para n = 1 (ou
n igual a outro inteiro) e o segundo é mostrar que, se o enunciado vale para n = k, então
o mesmo enunciado vale para n = k + 1. Também usamos a desigualdade de Boole da
qual a de Bonferroni generaliza.
Referências Bibliográficas
[1] William Feller. An Introduction to Probability Theory and Its Applications, volume
1. Wiley, January 1968.
[2] Sheldon M. Ross. A First Course in Probability. Prentice Hall, Upper Saddle River,
N.J., fifth edition, 1998.
[3] A.C. Morgado. Analise combinatoria e probabilidade: com as soluções dos exerćıcios.
Coleção do professor de matematica. SBM, 2006.