[logica] stringa di 20 lettere...

[wisher]

Non verrebbe più comodo calcolare quante stringhe possono essere composte con 4 vocali e 16 consonanti senza tenere conto dell'ordine e poi considerare lo spostamento delle vocali?
(5^4*16^16)*16

[Banus]

Originariamente inviato da mamo139

si sono messo come te... ho capito la logica con cui procedere... ma le combinazioni mi vengono troppe e mi perdo nei calcoli...

Facendo un po' di prove per allenare l'intuizione ho trovato questa formula per stringhe di lunghezza 9



dove p=16/21, e si ottiene 0.765181188. Le stringhe che hanno 4 consonanti consecutive nelle prime nove lettere sono un sottoinsieme delle soluzioni del problema, e quindi questo valore si può considerare un minorante della probabilità reale. A partire da 10 lettere ci possono essere combinazioni di tre o più gruppi con "buchi" (esempio: 4 consonanti, vocale, 5 consonanti) che rendono più difficile classificare i casi.
Ragionando sul problema tra l'altro ho ottenuto questa inaspettata uguaglianza (notando cancellazioni "magiche"):



Probabilmente spezzando ulteriormente le combinazioni al primo membro dovrei riuscire a trovare la formula corretta (quella riportata sopra è evidentemente sbagliata, visto che per N = n + l -1 = 20 e l = 4 supera 1 ). Se avrò voglia proverò ad attaccare ancora il problema

[checo]

Originariamente inviato da wisher

Non verrebbe più comodo calcolare quante stringhe possono essere composte con 4 vocali e 16 consonanti senza tenere conto dell'ordine e poi considerare lo spostamento delle vocali?
(5^4*16^16)*16

la probabilita va da 0 a 1 estremi compresi ti ricordo

[wisher]

Originariamente inviato da checo

la probabilita va da 0 a 1 estremi compresi ti ricordo

basta dividere per il numero totale di stringhe allora:-)

[mamo139]

Originariamente inviato da wisher

basta dividere per il numero totale di stringhe allora:-)

no non viene il risultato giusto...





la difficoltà del problema sta nel fatto che la stringa deve avere ALMENO 4 consonanti consecutive, ma ne puo avere anche di piu... ad esempio 5,6... 20... e il tutto va considerato per qualsiasi posizione!

in piu bisogna poi considerare che se come molti di voi hanno provato a fare si addotta il metodo di analizzare 4 blocchi alla volta ( ovvero:
primo blocco: (16/21)^4*(21/21)^16
secondo blocco: (21/21)*(16/21)^4*(21/21)^15
ecc.ecc...
..... che alla fine dà come risultato finale 17*(16/21)^4 )
si trascura il fatto che non si considerano molti casi, ovvero tutti quelli in cui la stringa è piu lunga di 4...


se vi consola fin ora ho trovato solo una persona in grado di risolverlo, e me l'ha risolto in un modo che non si capisce se non si ha studiato statistica (quindi neanche io l'ho capito perche si basa su teoremi e metodi gia definiti)... è per questo che sono alla ricerca di un metodo piu intuitivo

[checo]

Originariamente inviato da wisher

basta dividere per il numero totale di stringhe allora:-)

capisco andare a tentativi ragionando, ma sparar a caso mi sa che non ci si imbrocca

[checo]

Originariamente inviato da mamo139

no non viene il risultato giusto...





la difficoltà del problema sta nel fatto che la stringa deve avere ALMENO 4 consonanti consecutive, ma ne puo avere anche di piu... ad esempio 5,6... 20... e il tutto va considerato per qualsiasi posizione!

in piu bisogna poi considerare che se come molti di voi hanno provato a fare si addotta il metodo di analizzare 4 blocchi alla volta ( ovvero:
primo blocco: (16/21)^4*(21/21)^16
secondo blocco: (21/21)*(16/21)^4*(21/21)^15
ecc.ecc...
..... che alla fine dà come risultato finale 17*(16/21)^4 )
si trascura il fatto che non si considerano molti casi, ovvero tutti quelli in cui la stringa è piu lunga di 4...


se vi consola fin ora ho trovato solo una persona in grado di risolverlo, e me l'ha risolto in un modo che non si capisce se non si ha studiato statistica (quindi neanche io l'ho capito perche si basa su teoremi e metodi gia definiti)... è per questo che sono alla ricerca di un metodo piu intuitivo

io ho studiato statistica 3 anni all'itis + un esame a ing ma de ste cose proprio non ci ho mai capito un kaiser

[Banus]

Originariamente inviato da mamo139

se vi consola fin ora ho trovato solo una persona in grado di risolverlo, e me l'ha risolto in un modo che non si capisce se non si ha studiato statistica

Catene di Markov magari? Grazie per l'indizio, mi ha indirizzato verso la soluzione.
La strada dell'inclusione/esclusione è troppo complicata, sia dal punto di vista concettuale, sia dal punto di vista matematico. E' più semplice impostare il problema con questa procedura:
scorro la stringa e tutte le volte che incontro una consonante inizio a contare le consonanti adiacenti; se trovo una vocale azzero, se trovo 4 consonanti consecutive segno "successo".

Questa procedura può essere espressa come una catena di Markov. Se con "0" indichiamo "vocale" e "1" consonante gli stati possibili sono 0, 1, 11, 111, 1111. La matrice di transizione è questa (click sul link per vedere l'immagine):

http://operaez.net/mimetex/P=%5Cleft...%7D%5Cright%29

L'elemento in posizione i,j indica la probabilità di passare dallo stato i allo stato j, ad esempio a(1,2) è la probabilità di trovare una consonante dopo una vocale (=p). Le probabilità della matrice esprimono essenzialmente questo: la probabilità di trovare una vocale è 1-p, e se e hai meno di quattro consonanti azzeri il contatore; se trovi una consonante (con probabilità p) incrementa, e se hai quattro consonanti resta fermo (con probabilità 1).

Una catena di Markov ha bisogno di uno stato iniziale. Per semplicità prendiamo 0 (una vocale) perché non altera il numero di consonanti consecutive e perchè in questo modo il problema ha una formulazione più semplice: dopo una iterazione abbiamo il primo carattere della stringa, dopo due il secondo e così via. La probabilità di avere 4 consonanti consecutive in una stringa di 20 caratteri è quindi la probabilità di trovarsi nello stato 5 (1111) dopo 20 iterazioni.
Una proprietà molto comoda delle catene di Markov è che la matrice di transizione dalla posizione 0 alla posizione k è dato da P^k. Se la distribuzione degli stati iniziali è il vettore p, la probabilità degli stati finali è pP^k. La distribuzione iniziale in questo caso è (1,0,0,0,0) (vocale con probabilità 1) e ci interessa la probabilità finale di 1111. Quindi in pratica ci interessa l'elemento (1,5) di P^20. P^20 può essere calcolata facilmente (ad esempio usando questo sito) e si ottiene il risultato finale p=0,960325735.

Con questo metodo ho scoperto un errore (segno invertito) nella formula per le stringhe di lunghezza 9 che ho riportato sopra. La formula corretta è questa:

[mamo139]

Originariamente inviato da Banus

Catene di Markov magari?

esattamente, complimenti per la soluzione