Giovanni Bricconi

Ciao,

Il problema di trovare una picola sequenza particolare in più lunghe sequenze di eventi casuali di una certa lunghezza mi è venuto in mente qualche anno fa. Volevo farmi un’idea di quanto le parole di un testo sono anomale rispetto a sequenze di caratteri casuali: le parole appaiono spesso identiche nel testo mentre sequenze casuali (errori di battitura) sono molto rare. Allora per semplificare ho fatto l’ipotesi che le lettere dell’alfabeto avessero ciascuna una propria probabilità di apparire, e non fossero dipendenti tra loro (volevo semplificare al massimo).

Dopo un po’ di tempo ho scoperto che il problema era decisamente più difficile di quanto mi aspettassi; dopo molto tempo sono riuscito a risolverlo però in modo ricorsivo e piuttosto macchinoso. Ho deciso di provare a diffondere il problema per vedere se la mia soluzione è corretta e se qualcuno riesce a trovare una soluzione più furba che non richieda la ricorsione. Penso che per una particolare sequenza si possano comunque ottenere delle soluzioni in forma chiusa usando la “trasformata z”, ma non ho più avuto voglia di approfondire il problema.

Nei documenti dove spiego quello che ho trovato indico la piccola sequenza da cercare con il simbolo ρ mentre uso s per indicare la sequenza più lunga in cui cercare.

Ho definito diversi problemi, quello più chiaro da spiegare è la ricerca di esatamente i apparizioni di ρ nelle stringhe lunghe x caratteri: Ai(x). Dal quale si può anche facilmente ricavare la probabilità che ρ appaia al più i volte (Ni(x))

Per tornare alle soluzioni del problema che ho inviato: la sequenza abc semplifica molto il problema, le sequenze abcab o aaa sono molto più problematiche perchè si prestano a essere composte sovrapponendole: aaa si può comporre in aaaaaaaa e abcab in abcabcabcab. Con queste complicazioni trovare soluzioni con il calcolo combinatorio mi è stato impossibile.

Per trovare le soluzioni sono passato da questa idea: posso avere  i apparizioni in x caratteri se esattamente a x caratteri ho l’iesima apparizione oppure se prima avevo già i apparizioni e non estraggo la i+1 esima proprio in x.

Per tener conto delle sovrapposizioni possibili ho dovuto introdurre dei coefficienti che dipendono dalla forma della ρ che si sta cercando. Qui la soluzione si trova considerando che se ρ si può comporre allora un suo pezzettino di testa si deve ripetere. Fatta questa considerazione bisogna introdurre un nuovo problema ausiliario, la probabilità di avere Ai(x) che non terminano proprio con quel pezzettino.

Per venire all’ultima domanda del quiz, se si vanno a cercare la o una delle sequenza ρ più probabile (ripetizione del carattere più probabile) e la o una delle più improbabili si possono costruire due funzioni che indicano la probabilità minima e massima che si presentino quelle apparizioni al variare di x.

Per chi avesse ancora la pazienza di giocare con il problema propongo la lettura di questo articolo