Newsgroup: it.hobby.enigmi
Titolo: Probabilità II

Si effettuano 2N lanci di una moneta equilibrata e si osserva che si sono 
presentate N croci e N teste.Qual è la probabilità che per K 
(=0,2,4,..,N) lanci(non necessariamente consecutivi) il numero di teste 
sia stato >= al numero di croci?
On-Oƒƒ

 wrote in message
MPG.159161a98...@news.inwind.it...

50% ?...
Troppo facile ?...
--
Er Roscio.

 sia stato >= al numero di croci?
Non vorrei aver capito male, ma direi che il dominio dei K e' 1..2N
Per evitare fraintendimenti faccio un esempio, se con 2N=4 indico con O la testa e X la croce :
con Bin(4,2)=6 stringhe possibili (ed equiprobabili),
OOXX in 4 lanci le teste sono sempre in vantaggio o in parità, K=4
OXXO al terzo lancio le teste vanno in svantggio, K=3
XOXO K=2
XXOO K=1
...
E' questo che intendevi ?
Detto questo, credo di avere una congettura per le teste sempre in vantaggio (K=2N) :
S
P
O
I
L
E
R
!
!
!
p=1/(N+1)

, 
Cr...@cclinf.polito.it
 
says...
p=1/(N+1) OK!!!
N.B.:ci rientrano anche i numeri di Catalan.
Ciao Onoff

Onoff chiede

Ho trovato alcuni risultati davvero notevoli, c'è solo bisogno di sistemarli
un po'. Ecco in breve il frutto dell'ultima nottata.
Chiediamoci innanzitutto quanti sono i casi possibili, ovvero quante
sequenze esistono con N teste ed N corci. E' facile rispondere: dobbiamo
disporre in tutti i modi possibili, le N teste all'interno dei 2N lanci,
quindi il numero cercto vale C(2n,n)=(2N)!/(N!N!).
Se associamo le teste a tratti ascendenti / e le croci a tratti discendenti
\ possiamo rappresentare ogni sequenza di lanci con un grafico. Ad esempio,
per N=2:
 /\
/__\ ; /\/\ ; /\__ ; ____ ; ____ ; ____ ;
                \/   \  /   \/\/   \  /
                      \/            \/
così possiamo facilmente contare per quanti lanci le teste sono state almeno
quante le croc (grafico non negativo)
Se ci chiediamo quanti di questi grafici non scendono mai sotto lo zero, la
risposta è data da un numero di cui Onoff pare subire il fascino
irresistibile: i numeri Catalani.
Nel nostro caso solo 1/3 dei grafici (2 su 6) sono sempre sopra il livello
0, nel caso generico 1/(N+1) dei possibili C(2N,N) lo sono (e con questo
l'ipotesi di Crios risulta confermata). Questi numeri, 1/(N+1)*C(2N,N) sono
appunto i numeri Catalani, la cui sequenza, a partire da 0, vale
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
Altro risultato facile è il caso limite opposto: k=1
questo avviene se solo all'ultimo lancio le croci raggiungono le teste, e
succede solo se si comincia con una testa e nei 2(N-1) lanci successivi mai
le teste risultano meno delle croci. Ora sappiamo che questo avviene in
Cat(N-1) modi diversi, per cui possiamo calcolare la probabilità P(N,1) =
Cat(N-1)/C(2N,N)
Oltre questo non andavo, quindi ho acceso il fido Excel e in VB ho scritto
una funzione (poche righe davvero, magia della ricorsione!) che mi calcolava
i valori e me li metteva nel foglio sotto forma di tabella. E lì ho visto
che la prima colonne era uguale alla seconda, la terza alla quarta ecc, che
la terza colonna era somma di due celle consecutive della seconda, che la
quinta... ma salto a piè pari i passaggi intermedi che mi hanno portato al
risultato, e arrivo al sodo.
Con 2N lanci, le probabilità con k=2h-1 o k=2h si equivalgono. Cioè: essere
in vantaggio per 5 volte o 6 è ugualmente frequente. Con k=1 e 2 me lo
spiegherei pure, nel caso generico ho qualche difficoltà, ma è così.
Chiamerò P(N,k) la probabilità che, lanciando 2N monete (in realtà, visto
che sappiamo che le monete saranno N teste ed N croci, più che di lanci si
tratta di estrazioni da un urna), le croci siano non di meno delle teste
esattamente per k volte (k=1,..,2N). Ed ecco la tabella ed i risultati che
ne ho dedotto (ogni colonna rappresenta due valori consecutivi di k, le
righe sono gli N. Si vede subito che la prima colonna e la diagonale
presentano in bella vista i catalani)
1
1    2
2    3    5
5    7    9    14
14   19   23   28   42
42   56   66   76   90   132
132  174  202  227  255  297  429
429  561  645  715  785  869  1001 1430
1430 1859 2123 2333 2529 2739 3003 3432  4862
Ecco la formula:
P(N,2h-1) = P(N,2h) =
1/C(2N,N)* Sum(Cat(i)*Cat(N-i-1), i=0,..,h-1)
Per esempio, nella sesta riga, il 56 è somma di 42 e 14, il 66 di (42,14,5)
moltiplicati per (1,1,2), il 76 di (42,14,5,2) per (1,1,2,5) e così via
Vediamo per esempio N=3
h=1
P(3,1)=P(3,2)= 1/20 * (1*2) = 2/20
k=1 ______ , ______ ; k=2 ______ , ______ .
    \    /   \    /       \  /\/   \/\  /
     \/\/     \  /         \/         \/
               \/
h=2
P(3,3)=P(3,4)= 1/20 * (1*2+1*1) = 3/20
k=3 ______ , ____/\ , /\____ ;
    \/\/\/   \  /       \  /
              \/         \/
k=4 __/\__ , /\____ , ____/\ .
    \/  \/     \/\/   \/\/
h=3
P(3,5)=P(3,6)= 1/6 * (1*2+1*1+2*1) = 5/20
       /\                                /\
k=5 __/__\ , __/\/\ , /\__/\ , /\/\__ , /__\__ ;
    \/       \/         \/         \/       \/
      /\
     /  \     /\/\     /\         /\
k=6 /____\ , /____\ , /__\/\ , /\/__\ , /\/\/\ .
Altra conferma: P(N,1) = Cat(N-1)/C(2N,N) = 1/(2(N-1))
Per l'altro caso limite, h=2N, che pure lui era un Catalano, risulta che
se moltiplichiamo tutti i catalani da 0 a n per complementari
(Cat(0)*Cat(n)+Cat(1)*Cat(n-1)+...+Cat(n*Cat(0)) otteniamo ... Cat(n+1). Ho
scoperto una proprietà dei catalani. Magari era stranota, chissà.
Ciao, Silv:o)

 irresistibile: i numeri Catalani.
Hai ragione(so' monocorde:) Però chissà perché ha così tante 
interpretazioni combinatorie?Boh!?
Ciao,Onoff 

 interpretazioni combinatorie?Boh!?
Secondo me perché molti problemi combinatori si risolvono con il ricorso ad
una pila (stack, struttura FIFO), ed i numeri di Catalan contano in quanti
modi diversi possiamo riempire e svuotare la pila usando N elementi (N
pastiglie in un tubetto, visita di un albero con N nodi, N coppie di
parentesi aperte e poi chiuse). Questo spiega perché è così naturale
l'utilizzo di algoritmi ricorsivo per questa classe di problemi.
Ciao, Silv:o)