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
=========================================================================