Probabilidade Combinatória João Paulo Silva do Monte Lima ([email protected]) 2004, João Paulo Silva do Monte Lima

Probabilidade Combinatória

João Paulo Silva do Monte Lima([email protected])

2004, João Paulo Silva do Monte Lima.

Roteiro


•Noções Fundamentais

•Alguns Métodos de Enumeração:

Progressão Aritmética

Combinação

Noções Fundamentais


Sejam A e B subconjuntos de um espaço amostral S, valem as seguintes propriedades:

)()()()( BAPBPAPBAP (baseado no Princípio da Inclusão-Exclusão)

A e B são independentes )()()( BPAPBAP

A e B são excludentes )( BAP

Alguns Métodos de Enumeração

Listamos a seguir algumas maneiras de enumerar os elementos de um evento ou um espaço amostral


1) Progressão Aritmética (P.A.)

Dada uma P.A. de n elementos, em que a1 é seu primeiro elemento, an é seu último elemento e r é sua razão, temos:

an = a1 + (n – 1)rDesenvolvendo a igualdade acima, temos:

11

r

aan n


Problema 5.11) Escolha um inteiro uniformemente do conjunto {1, 2, 3, ..., 30}. Seja o evento A de que ele é divisível por 2; seja B o evento de que ele é divisível por 3; seja C o evento de que ele é divisível por 7.(a) Determine as probabilidades de A, B e C.

(b) Quais dos pares (A,B), (B,C) e (A,C) são independentes?

Resolução:(a) A quantidade de números do espaço amostral que são divisíveis por k será o número de elementos de uma P.A. de razão k, com primeiro elemento k.




(continuação)

1512

23011

A

AAn

r

aaA

2

1

30

15)(

S

AAP

1013

33011

B

BBn

r

aaB

3

1

30

10)(

S

BBP

417

72811

C

CCn

r

aaC

15

2

30

4)(

S

CCP


(continuação)

(b)A e B são independentes?Ser divisível por 2 e 3 é o mesmo que ser divisível

pelo mmc(2,3) = 6

51

6

63011

BA

BABAn

r

aaBA

)()(3

1

2

1

6

1

30

5)( BPAP

S

BABAP


Logo, A e B são independentes


(continuação)

A e C são independentes?Ser divisível por 2 e 7 é o mesmo que ser divisível

pelo mmc(2,7) = 14

21

14

142811

CA

CACAn

r

aaCA

)()(15

2

2

1

15

1

30

2)( CPAP

S

CACAP


Logo, A e C são independentes


(continuação)

B e C são independentes?Ser divisível por 3 e 7 é o mesmo que ser divisível

pelo mmc(3,7) = 21

11

21

212111

CB

CBCBn

r

aaCB

)()(15

2

3

1

30

1)( CPBP

S

CBCBP


Logo, B e C não são independentes



2) Combinação

A contagem dos elementos de um evento ou espaço amostral pode ser feita por combinação. Muitas vezes é interessante lançar mão de algumas identidades combinatórias, como por exemplo:

A soma das combinações “pares” de n é igual à soma das combinações

“ímpares” de n

1...31...20 2

nnnnn



Problema 5.13) Selecionamos um subconjunto X do conjunto S = {1, 2, ..., 100} aleatoriamente e uniformemente (de modo que todo subconjunto tem a mesma probabilidade de ser selecionado). Qual é a probabilidade de que:

(a) X tenha um número par de elementos.(b) Ambos 1 e 100 pertençam a X.(c) O maior elemento de X seja 50.(d) X tenha no máximo 2 elementos.



Resolução:

(a) 1002S A = { subconjuntos “pares” }

991100...2

1000100 22

A2

1

2

2)(

100

99

S

AAP

(b)

1002S B = { subconjuntos com 1 e 100 }

98...1

98098 2 B

4

1

2

2)(

100

98

S

BBP

Basta escolher os demais elementos dos subconjuntos:



(continuação)

(c) 1002S C = { subconjuntos cujo maior é 50 }

49...1

49049 2 C 51

100

49

22

2)(

S

CCP

(d)

1002S D = { subconjuntos com cardinalidade 2 }

21001100

0100

D

Basta escolher entre os elementos menores que 50:

S

DDP )(



Observando o Triângulo de Pascal e lançando mão da identidade...

knn

kn

... podemos concluir que a seguinte identidade é válida:

nn

nn

nn

nnnn

...22/12/12/...10



Em outras palavras, a identidade anterior consiste em dizer que a soma das combinações da esquerda de uma linha do Triângulo de Pascal é igual à soma das combinações da direita.

Quando n é ímpar, a soma de cada lado da igualdade é: 12 n

Quando n é par, a soma de cada lado da igualdade é:

2

2 2/nnn



Problema 5.14) Jogamos uma moeda n vezes (n 1). Para quais valores de n os seguintes pares de eventos são independentes?

(a) A primeira jogada foi Cara;O número de Caras foi par.

(b)A primeira jogada foi Cara;O número de Caras foi mais que o número de

Coroas.

(c) O número de Caras foi par;O número de Caras foi mais que o número de

Coroas.

Resolução:



(a)

Ca1 = { primeira jogada Cara }

CaP = { número de Caras par }

nS 2 ...Ca/Co Ca/Co Ca/Co

2

1

2

2)(

11

1

n

n

S

CaCaP

11 2 nCa ...

Ca/Co Ca/Co

Ca

2

1

2

2)(

1

n

nP

P S

CaCaP 1

...20 2 nnn

PCa



(continuação)Ca1 CaP= {1ª jogada Cara e n.º Caras par}

= {1ª jogada Cara e n.º Caras ímpar nas outras}

)()(2

1

2

1

4

1

2

2)(

1

21

1

P

n

nP

P

CaPCaP

S

CaCaCaCaP

2...3

111

1 2

nnnPCaCa

Logo, Ca1 e CaP são independentes para

qualquer valor válido de n

(continuação)



(b) Vamos testar duas situações:

B = { n.° Caras > n.° Coroas }

nS 2 ...Ca/Co Ca/Co Ca/Co

• n ímpar:

1...12/ 2

nnn

nnB

2

1

2

2)(

1

n

n

S

BBP

Ca1 B= {1ª jog. Cara e n.º Caras > n.º Coroas }

= {1ª jog. Cara e n.º Caras n.º Coroas nas outras}

2

1)( 1 CaP

(continuação)



)()(2

1

2

1

24

1

2)(

1

1

2/)1(1

2

2/)1(12

11

1

BPCaP

S

BCaBCaP

n

nn

n

nnn

2

2/)1(12

2

2/)1(12

2/)1(1

11

...12/)1(1

2/)1(1

1

11

nn

nn

nn

nn

nn

nn

nn

BCa

Logo, Ca1 e B não são independentes para n

ímpar

(continuação)



• n par:

2

2 2/

...22/12/

nnn

nn

nn

nnB

1

2/

2/

22

1

22

2

)(

n

nn

n

nnn

S

BBP

211

...22/)1(1

12/)1(1

1 2

n

nn

nn

nnBCa

)()(

22

1

2

1

4

1

2

2)( 11

2/2

11 BPCaP

S

BCaBCaP

n

nn

n

n

Logo, Ca1 e B não são independentes para n par, e portanto não são independentes, qualquer que

seja n

nS 22

1)( 1 CaP

(continuação)



(c) Vamos testar duas situações: • n par: nS 2

CaP B= { n.º Caras par e n.º Caras > n.º Coroas }

2

1)( PCaP

1

2/

22

1)(

n

nn

BP

6656

46

36

26

16

06

44

34

24

14

04

22

12

02

Observando as linhas “pares” do Triângulo de Pascal, notamos que, quando a combinação central é “ímpar”, a quantidade de combinações “pares” à esquerda é a metade das combinações pares da linha

(continuação)



Se o n que estivermos considerando tiver combinação central “ímpar”, então temos: 22 n

P BCa

)()(

22

1

2

1

4

1

2

2)(

1

2/2

BPCaPS

BCaBCaP Pn

nn

n

nP

P

Se o n que estivermos considerando tiver combinação central “par”, então temos:

2

2 2/1

nnn

P BCa

)()(

22

1

2

1

24

1

22

2

)(

1

2/

1

2/

2/1

BPCaP

S

BCaBCaP

Pn

nn

n

nn

n

nnn

PP

(continuação)



Logo, CaP e B não são independentes para n par• n ímpar: nS 2

2

1)( PCaP

2

1)( BP

776

757

47

37

27

17

07

55

45

35

25

15

05

33

23

13

03

11

01 Observando as linhas

“ímpares” do Triângulo de Pascal, notamos que, quando n = 4x + 3, x natural (em outras palavras, linha não, linha sim), a quantidade de combinações “pares” à esquerda é a metade das combinações pares da linha

(continuação)



(continuação)Se o n que estivermos considerando não for igual a 4x + 3, x natural, então temos:

)()(2

1

2

1

4

1

2

2)(

2

BPCaPS

BCaBCaP Pn

nP

P

Se o n que estivermos considerando for igual a 4x + 3, x natural, então temos:

22 nP BCa

)()(2

1

2

1

4

1

2

2)(

2

BPCaPS

BCaBCaP Pn

nP

P

22 nP BCa

Logo, CaP e B são independentes para todo n = 4x + 3, x natural

* Todas as questões contidas neste material foram retiradas do livro:

“Discrete Mathematics: Elementary and Beyond”, L. Lovász, J. Pelikán & K. Vesztergombi. Springer, January 2003, ISBN 0387955852. Tradução parcial datada de 20/09/2003 por Ruy J. Guerra B. de Queiroz disponível em:http://www.cin.ufpe.br/~if670


Probabilidade Combinatória

João Paulo Silva do Monte Lima([email protected])


Documents

Probabilidade Combinatória João Paulo Silva do Monte Lima ([email protected]) 2004, João Paulo Silva do Monte Lima