Re: [obm-l] Probabilidade - Ataque

[Leonardo Paulo Maia <lpmaia@xxxxxxxxxxx>]

Cláudio, qualquer problema de probabilidade em espaços amostrais finitos e com
amostragem aleatória pode ser visto como um problema de análise combinatória.
Se você quer determinar a probabilidade de um evento A, é preciso determinar de
quantas formas o evento A pode ocorrer e dividir esse número pelo número de
formas de ocorrência de qualquer evento.

Seja C(a,b) = a!/[b!(a-b)!]. De quantas formas podemos escolher n chips entre
m+n? A resposta é C(m+n,n) ou C(m+n,m), certo? Isso é trivial, mas também pode
ser visto de uma forma alternativa que sugere um caminho para a solução.
Imagine que m=7 e n=4, havendo um total de 11 chips. O caso em que os chips 1,
3, 4 e 10 são amostrados pode ser representado como (+ - + + - - - - - + -). O
número total de possíveis amostragens é igual ao número de permutações desses
11 símbolos, 11!/[4!7!]. Em geral, temos m sinais -, n sinais +, e recuperamos
a resposta C(m+n,m).

De quantas formas nenhum chip na amostra supera todos os chips não amostrados?
Isso ocorre se e somente se temos uma amostragem do tipo (...-), que acaba com
um sinal -. O que acontece antes desse sinal é irrelevante. Podemos permutar os
m-1 sinais - restantes e os n sinais + como quisermos. Há C(m+n-1,m-1)
possibilidades.

De quantas formas exatamente um chip na amostra supera todos os chips não
amostrados? Isso ocorre se e somente se temos uma amostragem do tipo (...-+).
Podemos permutar os m-1 sinais - e os n-1 sinais + restantes como quisermos. Há
C(m+n-2,m-1) possibilidades.

De quantas formas exatamente i chips na amostra superam todos os chips não
amostrados? Isso ocorre se e somente se temos uma amostragem do tipo
(...-+++...+++), com i sinais + fechando a seqüência. Podemos permutar os m-1
sinais - e os n-i sinais + restantes como quisermos. Há C(m+n-i-1,m-1)
possibilidades.

Logo, Prob(X=i) = C(m+n-i-1,m-1)/C(m+n,m).

Leo





Quoting Claudio Freitas <claudio_exatas@terra.com.br>:

> Olá, estou tendo dificuldades em como atacar este problema de 
> probabilidade. Não tenho idéias de por onde começar. Qual tipo de 
> posicionamento e que tipo de lógica vocês propõem para que eu siga nao 
> apenas neste problema em específico, mas em problemas semelhantes a esse:
> 
> 
> "A jar contains m + n chips, numbered 1, 2, ..., n+m. A set of size n is 
> drawn. If we let X denote the number of chips drawn having numbers that 
> exceed all of the numbers of those remaining, compute the probability 
> mass function."
> 
> []s, Claudio Freitas
> 
> =========================================================================
> Instruções para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =========================================================================
> 


=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================