Quesito su VA non binomiale costruita a partire da Bernoulli
Scusate per il titolo, ma non mi riusciva proprio di trovarne uno più descrittivo di quanto voglio esporvi.
Supponiamo di avere una variabile aleatoria $X$ di Bernoulli di parametro $p$. Ok, per semplicità possiamo pure assumere di fare l'ultraclassico esempio della monetina non sbilanciata e perfettamente simmetrica blablabla
Quello che sappiamo benissimo è che, a partire da queste variabili si costruiscono le binomiali, che conosciamo bene ma purtroppo non c'entrano molto col mio problema (e dico mio perché è una mia pura curiosità, ma temo di non essere in grado da solo di soddisfarla).
Dunque, arriviamo al nocciolo della questione.
Sia $N in NN$ un intero grande a piacere e sia $X$ la VA Bernoulliana di parametro $p$ presentata poco fa.
La mia curiosità è quella di conoscere la funzione di probabilità della VA $Y$ = massimo numero di volte consecutive in cui l'evento $X$ si verifica.
Il problema è appunto quel "consecutive". Se mi bastasse sapere quante volte $X$ si verifica, in qualsiasi ordine, la $Y$ sarebbe una VA binomiale di parametri $N$ e $p$ e la sua funzione di probabilità sarebbe nota. Ma dato che io voglio che l'evento accada per un certo numero di volte di fila, la $Y$ diventa per me un qualcosa su cui non ho la più pallida idea di come andare ad operare.
Dato che non sono un matematico, ma semplicemente un povero laureando in informatica molto curioso che sta seguendo un corso di statistica, vi sottopongo il quesito, sperando in qualche dritta..!
Per ora quel poco che posso fare è un ragionamento sui casi limite, ovvero:
1) CASO $P(Y=N)$:
Questo caso è piuttosto banale... ovviamente esiste un'unica sequenza di questo tipo, altrettanto ovviamente se l'evento $X$ si verifica per tutte le $N$ volte è ovvio che queste siano tutte consecutive. Pertanto in questo caso credo di poter calcolare questa probabilità usando la funzione di probabilità di una binomiale:
$P(Y=N) = ( ( N ),( N ) ) * p^N * (1-p)^(N-N) = p^N$
Ok, era abbastanza ovvio :\
2) CASO $P(Y=0)$:
Direi analogo al primo.. 0 volte di fila significa che $X$ non si è verificato nemmeno una volta in tutta la benedetta sequenza di $N$ ripetizioni.
Pertanto anche qui $P(Y=0) = ( ( N ),( 0 ) ) * p^0 * (1-p)^(N-0) = (1-p)^N$
Che poi è ovvio che, se scegliamo $p=1/2$ come nel caso della monetina, la probabilità è la stessa in entrambi i casi... ma preferisco ragionare più in generale.
3) CASO $P(Y=1)$:
...ed è qui che mi inizio a perdere.
Questo significa che $X$ non si è mai verificato due volte di seguito. Ma non solo: in tutta la sequenza lunga $N$, per come ho definito $Y$ so che $X$ si è verificato almeno una volta, al massimo una volta consecutiva, ma non necessariamente esattamente una volta in tutta la sequenza. Se così fosse, anche qui mi potrei ricondurre alla beneamata binomiale.
Allora, ho provato a vedere cosa succede in questo caso per $N$ piccolo, scoprendo che:
- per $N=2$:
Tanto semplice quanto inutile.
Delle 4 possibili configurazioni, sono 2 quelle per cui $Y=1$, ovvero $01$ e $10$, dato che con $00$ $Y=0$ e con $11$ $Y=2$.
Pertanto, per $N=2$ conosco già la funzione di probabilità di $Y$.
- per $N=3$
Sarebbe abbastanza semplice anche qui calcolare "a mano" la funzione di probabilità della $Y$, ma non è quello che mi interessa.. io vorrei tirare fuori una formula per poter valutare $P(Y=k)$ se ad esempio $N=700000$.
Quindi quello che faccio è ancora una volta analizzare i casi per cui $Y=1$.
La lista è $001,010,100,101$. Nelle prime tre sequenze, la $X$ si è verificata esattamente una volta.
In effetti è abbastanza intuitivo che, per ogni $N$, tra le sequenze per cui $Y=k$ ci saranno sempre quelle in cui l'evento $X$ si è verificato esattamente $k$ volte, dunque tali sequenze saranno sempre un numero $\geq ((N),(k))$.
Il mio problema è proprio capire QUANTE sono le sequenze aggiuntive per ogni N.
- per $N=4$
Qui le sequenze per cui $Y=1$ sono 7, ovvero $0001,0010,0100,0101,1000,1001,1010$.
Ed io sono sempre più disorientato
- per $N=5$
Se la stanchezza non mi annebbia la vista (e le facoltà mentali), ne ho contate 12, ovvero $00001,00010,00100,00101,01000,01001,01010,10000,10001,10010,10100,10101$.
Ne capisco sempre meno, ma è tempo di fare qualche riepilogo ed eventualmente trarre qualche accenno di conclusione:
Se $N=2$, allora $P(Y=0)=1/4$, $P(Y=1)=1/2$, $P(Y=2)=1/4$.
Se $N=3$, allora $P(Y=0)=1/8$, $P(Y=1)=1/2$, $P(Y=2)=1/4$, $P(Y=3)=1/8$.
Se $N=4$, allora so solo che $P(Y=1)=7/16$.
Se $N=5$ invece $P(Y=1)=3/8$.
Tutti questi numeri ovviamente dovrebbero essere in relazione con $N$ e con $p$ (rileggendo il riepilogo qui sopra mi sono accorto di aver implicitamente (ed involontariamente) assunto che $p=1/2$), ma da queste poche prove effettuate non riesco a trovare alcun legame... a parte per i due casi banali già citati sopra, $Y=0$ e $Y=N$.
Inoltre dovrei provare a ragionare sull'espansione delle sequenze per cui $Y=k$, ovvero su quali e quante siano le sequenze che arricchiscano le $((N),(k))$ sequenze sicure. In questo caso $k=1$ e mi pare che con un po' di ragionamento ci si possa arrivare (ci proverò domani), anche se temo che per $k$ maggiori le cose si complichino più di quanto io possa gestire
4) CASO $P(Y=k)$ con $ 1 < k < N$:
ahahaha!
Sì, davvero molto simpatico
Se per il caso 3 sono stato capace di scrivere tutto quell'enorme sproloquio, che cosa dovrei scrivere qui?
ahaha a dire il vero non ci ho ancora nemmeno pensato, anche perché già il caso 3 sta occupando il 97% di quel che rimane il mio cervello pensante a quest'ora. E comunque meglio fare un passo per volta... quindi qui spero di arrivarci in futuro, per me sarebbe già un grande risultato !
Scusate per il mega-papiro ovviamente.
Spero che qualcuno legga tutto e mi aiuti
Confido in qualche risposta!!
Supponiamo di avere una variabile aleatoria $X$ di Bernoulli di parametro $p$. Ok, per semplicità possiamo pure assumere di fare l'ultraclassico esempio della monetina non sbilanciata e perfettamente simmetrica blablabla
Quello che sappiamo benissimo è che, a partire da queste variabili si costruiscono le binomiali, che conosciamo bene ma purtroppo non c'entrano molto col mio problema (e dico mio perché è una mia pura curiosità, ma temo di non essere in grado da solo di soddisfarla).
Dunque, arriviamo al nocciolo della questione.
Sia $N in NN$ un intero grande a piacere e sia $X$ la VA Bernoulliana di parametro $p$ presentata poco fa.
La mia curiosità è quella di conoscere la funzione di probabilità della VA $Y$ = massimo numero di volte consecutive in cui l'evento $X$ si verifica.
Il problema è appunto quel "consecutive". Se mi bastasse sapere quante volte $X$ si verifica, in qualsiasi ordine, la $Y$ sarebbe una VA binomiale di parametri $N$ e $p$ e la sua funzione di probabilità sarebbe nota. Ma dato che io voglio che l'evento accada per un certo numero di volte di fila, la $Y$ diventa per me un qualcosa su cui non ho la più pallida idea di come andare ad operare.
Dato che non sono un matematico, ma semplicemente un povero laureando in informatica molto curioso che sta seguendo un corso di statistica, vi sottopongo il quesito, sperando in qualche dritta..!
Per ora quel poco che posso fare è un ragionamento sui casi limite, ovvero:
1) CASO $P(Y=N)$:
Questo caso è piuttosto banale... ovviamente esiste un'unica sequenza di questo tipo, altrettanto ovviamente se l'evento $X$ si verifica per tutte le $N$ volte è ovvio che queste siano tutte consecutive. Pertanto in questo caso credo di poter calcolare questa probabilità usando la funzione di probabilità di una binomiale:
$P(Y=N) = ( ( N ),( N ) ) * p^N * (1-p)^(N-N) = p^N$
Ok, era abbastanza ovvio :\
2) CASO $P(Y=0)$:
Direi analogo al primo.. 0 volte di fila significa che $X$ non si è verificato nemmeno una volta in tutta la benedetta sequenza di $N$ ripetizioni.
Pertanto anche qui $P(Y=0) = ( ( N ),( 0 ) ) * p^0 * (1-p)^(N-0) = (1-p)^N$
Che poi è ovvio che, se scegliamo $p=1/2$ come nel caso della monetina, la probabilità è la stessa in entrambi i casi... ma preferisco ragionare più in generale.
3) CASO $P(Y=1)$:
...ed è qui che mi inizio a perdere.
Questo significa che $X$ non si è mai verificato due volte di seguito. Ma non solo: in tutta la sequenza lunga $N$, per come ho definito $Y$ so che $X$ si è verificato almeno una volta, al massimo una volta consecutiva, ma non necessariamente esattamente una volta in tutta la sequenza. Se così fosse, anche qui mi potrei ricondurre alla beneamata binomiale.
Allora, ho provato a vedere cosa succede in questo caso per $N$ piccolo, scoprendo che:
- per $N=2$:
Tanto semplice quanto inutile.
Delle 4 possibili configurazioni, sono 2 quelle per cui $Y=1$, ovvero $01$ e $10$, dato che con $00$ $Y=0$ e con $11$ $Y=2$.
Pertanto, per $N=2$ conosco già la funzione di probabilità di $Y$.
- per $N=3$
Sarebbe abbastanza semplice anche qui calcolare "a mano" la funzione di probabilità della $Y$, ma non è quello che mi interessa.. io vorrei tirare fuori una formula per poter valutare $P(Y=k)$ se ad esempio $N=700000$.
Quindi quello che faccio è ancora una volta analizzare i casi per cui $Y=1$.
La lista è $001,010,100,101$. Nelle prime tre sequenze, la $X$ si è verificata esattamente una volta.
In effetti è abbastanza intuitivo che, per ogni $N$, tra le sequenze per cui $Y=k$ ci saranno sempre quelle in cui l'evento $X$ si è verificato esattamente $k$ volte, dunque tali sequenze saranno sempre un numero $\geq ((N),(k))$.
Il mio problema è proprio capire QUANTE sono le sequenze aggiuntive per ogni N.
- per $N=4$
Qui le sequenze per cui $Y=1$ sono 7, ovvero $0001,0010,0100,0101,1000,1001,1010$.
Ed io sono sempre più disorientato
- per $N=5$
Se la stanchezza non mi annebbia la vista (e le facoltà mentali), ne ho contate 12, ovvero $00001,00010,00100,00101,01000,01001,01010,10000,10001,10010,10100,10101$.
Ne capisco sempre meno, ma è tempo di fare qualche riepilogo ed eventualmente trarre qualche accenno di conclusione:
Se $N=2$, allora $P(Y=0)=1/4$, $P(Y=1)=1/2$, $P(Y=2)=1/4$.
Se $N=3$, allora $P(Y=0)=1/8$, $P(Y=1)=1/2$, $P(Y=2)=1/4$, $P(Y=3)=1/8$.
Se $N=4$, allora so solo che $P(Y=1)=7/16$.
Se $N=5$ invece $P(Y=1)=3/8$.
Tutti questi numeri ovviamente dovrebbero essere in relazione con $N$ e con $p$ (rileggendo il riepilogo qui sopra mi sono accorto di aver implicitamente (ed involontariamente) assunto che $p=1/2$), ma da queste poche prove effettuate non riesco a trovare alcun legame... a parte per i due casi banali già citati sopra, $Y=0$ e $Y=N$.
Inoltre dovrei provare a ragionare sull'espansione delle sequenze per cui $Y=k$, ovvero su quali e quante siano le sequenze che arricchiscano le $((N),(k))$ sequenze sicure. In questo caso $k=1$ e mi pare che con un po' di ragionamento ci si possa arrivare (ci proverò domani), anche se temo che per $k$ maggiori le cose si complichino più di quanto io possa gestire
4) CASO $P(Y=k)$ con $ 1 < k < N$:
ahahaha!
Sì, davvero molto simpatico
Se per il caso 3 sono stato capace di scrivere tutto quell'enorme sproloquio, che cosa dovrei scrivere qui?
ahaha a dire il vero non ci ho ancora nemmeno pensato, anche perché già il caso 3 sta occupando il 97% di quel che rimane il mio cervello pensante a quest'ora. E comunque meglio fare un passo per volta... quindi qui spero di arrivarci in futuro, per me sarebbe già un grande risultato
!Scusate per il mega-papiro ovviamente.
Spero che qualcuno legga tutto e mi aiuti
Confido in qualche risposta!!
Risposte
Quaestio interessante. Comincerei dal contare quelli che potremmo definire "pattern" di 1 in sequenza di 0. Passi che vedo necessari:
a) identificare il numero massimo di pattern possibili; esempio, con pattern '1' in una sequenza di dieci zero '0000000000', posso avere al massimo 5 pattern disposti '1010101010' oppure '0101010101' (in due modi dunque); ovviamente posso a anche avere meno pattern in una sequenza di dieci zeri, ovvero 4, 3, 2, 1 o nessun pattern; ancora, con pattern '11' vedo al massimo tre pattern '1101101100' oppure '1101100110', '0110011011'... ma ovviamente ce ne stanno anche 2, 1 o nessuno;
b) contare in quanti i modi, non ripetuti, i pattern possono essere disposti (alcuni esempi sono dati sopra) sulla base della lunghezza del pattern e della sequenza totale.
Se veniamo a capo di questo - sommatorie? un algoritmo? - abbiamo un sistema che ci determina il numero casi possibili rispetto al numero casi totali, che possiamo combinare con la p. del singolo evento.
a) identificare il numero massimo di pattern possibili; esempio, con pattern '1' in una sequenza di dieci zero '0000000000', posso avere al massimo 5 pattern disposti '1010101010' oppure '0101010101' (in due modi dunque); ovviamente posso a anche avere meno pattern in una sequenza di dieci zeri, ovvero 4, 3, 2, 1 o nessun pattern; ancora, con pattern '11' vedo al massimo tre pattern '1101101100' oppure '1101100110', '0110011011'... ma ovviamente ce ne stanno anche 2, 1 o nessuno;
b) contare in quanti i modi, non ripetuti, i pattern possono essere disposti (alcuni esempi sono dati sopra) sulla base della lunghezza del pattern e della sequenza totale.
Se veniamo a capo di questo - sommatorie? un algoritmo? - abbiamo un sistema che ci determina il numero casi possibili rispetto al numero casi totali, che possiamo combinare con la p. del singolo evento.
Pattern, dici? Potrebbe essere una cosa interessante... soprattutto per un calcolatore. Un algoritmo per la verifica ed il conteggio delle sequenze tali che $Y=k$ non dovrebbe essere neanche poi troppo complicato. Ma un algoritmo "brute force" non è esattamente quello che cerco!
Mi piacerebbe riuscire a trovare una formula, e penso che la ricorsione in tutto ciò potrebbe aiutare.
L'idea di base è quella di partire dalle sequenze piccole, e poi vedere "per espansione" se si trovano delle sequenze comuni... il che è un po' quello che ho già iniziato a fare quando ho scritto gli esempi per gli $N$ piccoli.
Dunque, prendendo in considerazione il caso $Y=1$:
Su $N=0$ il discorso non ha molto senso...
Partendo da $N=1$ abbiamo due casi possibili: $1$ e $0$, di cui solo il primo ci interessa
con $N = 2$ già notiamo che:
1. anteponendo lo $0$, riusciamo a sfruttare tutte le sequenze di $N-1$ (in questo caso solo una), quindi concatenando abbiamo $01$ che soddisfa $Y=1$
2. se come prima cifra abbiamo un $1$, riusciamo a trovare un'altra sequenza utile, cioè naturalmente $10$
La cosa interessante di questo discorso, è che se prendiamo per esempio $N=5$, possiamo verificare che il primo punto viene rispettato: infatti delle $12$ sequenze precedentemente analizzate, possiamo osservare che le prime $7$ sono esattamente identiche a quelle di $N=4$, togliendo lo $0$ più a sinistra.
..tuttavia mentre cercavo di esprimere quest'ultima frase "poco matematica", mi è venuta in mente l'idea di analizzare l'espansione verso destra e non verso sinistra, anche se credo che le due cose si equivalgono.. ma almeno questa sarebbe più intuitiva, seguendo l'ordine cronologico degli eventi.
Quindi:
a. Per ogni $N$ sarà presente la sequenza formata da $k >= 0$ zeri che precedono l'unico $1$ (ovvero l'evento si è verificato per la prima volta proprio all'$N$-esima ripetizione).
b. In più, si analizza ogni sequenza presente in $N-1$: se essa termina per $1$, si aggiunge in $N$ una sequenza uguale a cui si appone uno $0$ finale; se invece termina per $0$, si aggiungeranno due sequenze, apponendo alla fine della prima un $1$ e alla fine della seconda uno $0$.
Detto ciò, per $N=1$:
$1$ (in base a quanto detto in a. Qui $k=0$)
Per $N=2$:
$01$ (per la a.)
$10$ (per la b.)
Per $N=3$:
$001$ (per la a.)
$010$ (per la b.)
$100$ (per la b.)
$100$ (per la b.)
...e così via. Il ragionamento è analogo per gli $N$ successivi.
Ed ecco che mi sono costruito un metodo incrementale per costruire tutte le sequenze. Ma contarle? E sapere subito quali e quante sono le sequenze se $N=20$, senza stare a costruire prima tutte le altre?
Per questo dicevo che creare un algoritmo era piuttosto semplice. Il fatto ora è dedurre una formula valida per ogni $N in NN$.
...temo che tutto ciò abbia a che fare con le serie e convergenze varie, ma non so perché da qualche anno a questa parte l'analisi mi fa veramente paura...!
Mi piacerebbe riuscire a trovare una formula, e penso che la ricorsione in tutto ciò potrebbe aiutare.
L'idea di base è quella di partire dalle sequenze piccole, e poi vedere "per espansione" se si trovano delle sequenze comuni... il che è un po' quello che ho già iniziato a fare quando ho scritto gli esempi per gli $N$ piccoli.
Dunque, prendendo in considerazione il caso $Y=1$:
Su $N=0$ il discorso non ha molto senso...
Partendo da $N=1$ abbiamo due casi possibili: $1$ e $0$, di cui solo il primo ci interessa
con $N = 2$ già notiamo che:
1. anteponendo lo $0$, riusciamo a sfruttare tutte le sequenze di $N-1$ (in questo caso solo una), quindi concatenando abbiamo $01$ che soddisfa $Y=1$
2. se come prima cifra abbiamo un $1$, riusciamo a trovare un'altra sequenza utile, cioè naturalmente $10$
La cosa interessante di questo discorso, è che se prendiamo per esempio $N=5$, possiamo verificare che il primo punto viene rispettato: infatti delle $12$ sequenze precedentemente analizzate, possiamo osservare che le prime $7$ sono esattamente identiche a quelle di $N=4$, togliendo lo $0$ più a sinistra.
..tuttavia mentre cercavo di esprimere quest'ultima frase "poco matematica", mi è venuta in mente l'idea di analizzare l'espansione verso destra e non verso sinistra, anche se credo che le due cose si equivalgono.. ma almeno questa sarebbe più intuitiva, seguendo l'ordine cronologico degli eventi.
Quindi:
a. Per ogni $N$ sarà presente la sequenza formata da $k >= 0$ zeri che precedono l'unico $1$ (ovvero l'evento si è verificato per la prima volta proprio all'$N$-esima ripetizione).
b. In più, si analizza ogni sequenza presente in $N-1$: se essa termina per $1$, si aggiunge in $N$ una sequenza uguale a cui si appone uno $0$ finale; se invece termina per $0$, si aggiungeranno due sequenze, apponendo alla fine della prima un $1$ e alla fine della seconda uno $0$.
Detto ciò, per $N=1$:
$1$ (in base a quanto detto in a. Qui $k=0$)
Per $N=2$:
$01$ (per la a.)
$10$ (per la b.)
Per $N=3$:
$001$ (per la a.)
$010$ (per la b.)
$100$ (per la b.)
$100$ (per la b.)
...e così via. Il ragionamento è analogo per gli $N$ successivi.
Ed ecco che mi sono costruito un metodo incrementale per costruire tutte le sequenze. Ma contarle? E sapere subito quali e quante sono le sequenze se $N=20$, senza stare a costruire prima tutte le altre?
Per questo dicevo che creare un algoritmo era piuttosto semplice. Il fatto ora è dedurre una formula valida per ogni $N in NN$.
...temo che tutto ciò abbia a che fare con le serie e convergenze varie, ma non so perché da qualche anno a questa parte l'analisi mi fa veramente paura...!
Ieri sera, continuando a ragionare sull'argomento riguardo al caso $Y=1$, ho "scoperto" una cosa che devo dire mi ha lasciato un po' di stucco.
Ovvero ho trovato una strana relazione tra $N$ e la lunghezza delle sequenze (che chiamerò $S_N$) tali che $Y=1$.
Sono partito contando le cardinalità di $S_0,S_1,S_2,S_3,S_4$ e $S_5$ che avevo già trovato con il metodo esposto prima, con l'intenzione di trovare una qualche relazione tra di esse che fosse valida per ogni $N in NN$.
Dunque, si ha:
$S_0 = 0$
$S_1 = 1$
$S_2 = 2$
$S_3 = 4$
$S_4 = 7$
$S_5 = 12$
Forse sarà stato che non sapevo proprio da dove partire, ma ho provato per prima cosa a calcolare semplicemente le differenze tra i vari $S_k$ e $S_(k-1)$, trovando una cosa molto strana: queste differenze ricordano in modo spaventoso una famosa successione: quella di fibonacci!
Infatti si ha che $S_1 - S_0 = 1, S_2 - S_1 = 1, S_3 - S_2 = 2, S_4 - S_3 = 3, S_5 - S_4 = 5$
Generalizzando, se ${ (fib(0)=0 ),( fib(1)=1 ),( fib(n) = fib(n-1) + fib(n-2) : n>=2):}$
si ha:
$S_N = fib(N+2) - 1$
Pensando che potesse essere solo un caso, ho provato ad estendere il ragionamento. L'ho fatto solo fino a $S_7$ ed ovviamente questa non è una prova che ciò valga per tutti i numeri naturali, ma fin qui vale e non vedo perché non dovrebbe anche per gli altri.. ma qui chiedo l'aiuto di voi matematici!
Vado ad informarmi un po' sulla successione di fibonacci per vedere se qualcuno sia riuscito ad estrapolare una formula per calcolare l'n-esimo numero della successione mediante una formula o se ciò è impossibile (spero di no! non sarebbe molto comodo calcolare fib(100)... e deve essere un numero a parecchie cifre)
Ad ogni modo, anche se questa formula dovesse valere, ciò continuerebbe a sembrarmi strano, in quanto sarebbe valida solo per quanto riguarda $Y=1$ (mmm... rimane da verificare però poi il comportamento per $Y=2,Y=3,...$) e mi sembra poco probabile il dover trovare una soluzione ad hoc per ogni $k$, dovendo considerare pure che $k$ dipende ovviamente da $N$...
....sono sempre più confuso!
EDIT: ho corretto la formula, dato che avevo sbagliato a scrivere la successione di fibonacci assumendo erroneamente che $fib(0) = 1$ anziché $fib(0) = 0$.
Ah, ed ho anche trovato qui la formula per calcolare l'n-esimo termine della successione.
Mi rimangono però i dubbi che ho esposto sopra...
Ovvero ho trovato una strana relazione tra $N$ e la lunghezza delle sequenze (che chiamerò $S_N$) tali che $Y=1$.
Sono partito contando le cardinalità di $S_0,S_1,S_2,S_3,S_4$ e $S_5$ che avevo già trovato con il metodo esposto prima, con l'intenzione di trovare una qualche relazione tra di esse che fosse valida per ogni $N in NN$.
Dunque, si ha:
$S_0 = 0$
$S_1 = 1$
$S_2 = 2$
$S_3 = 4$
$S_4 = 7$
$S_5 = 12$
Forse sarà stato che non sapevo proprio da dove partire, ma ho provato per prima cosa a calcolare semplicemente le differenze tra i vari $S_k$ e $S_(k-1)$, trovando una cosa molto strana: queste differenze ricordano in modo spaventoso una famosa successione: quella di fibonacci!
Infatti si ha che $S_1 - S_0 = 1, S_2 - S_1 = 1, S_3 - S_2 = 2, S_4 - S_3 = 3, S_5 - S_4 = 5$
Generalizzando, se ${ (fib(0)=0 ),( fib(1)=1 ),( fib(n) = fib(n-1) + fib(n-2) : n>=2):}$
si ha:
$S_N = fib(N+2) - 1$
Pensando che potesse essere solo un caso, ho provato ad estendere il ragionamento. L'ho fatto solo fino a $S_7$ ed ovviamente questa non è una prova che ciò valga per tutti i numeri naturali, ma fin qui vale e non vedo perché non dovrebbe anche per gli altri..
ma qui chiedo l'aiuto di voi matematici!Vado ad informarmi un po' sulla successione di fibonacci per vedere se qualcuno sia riuscito ad estrapolare una formula per calcolare l'n-esimo numero della successione mediante una formula o se ciò è impossibile (spero di no! non sarebbe molto comodo calcolare fib(100)... e deve essere un numero a parecchie cifre
)Ad ogni modo, anche se questa formula dovesse valere, ciò continuerebbe a sembrarmi strano, in quanto sarebbe valida solo per quanto riguarda $Y=1$ (mmm... rimane da verificare però poi il comportamento per $Y=2,Y=3,...$) e mi sembra poco probabile il dover trovare una soluzione ad hoc per ogni $k$, dovendo considerare pure che $k$ dipende ovviamente da $N$...
....sono sempre più confuso!
EDIT: ho corretto la formula, dato che avevo sbagliato a scrivere la successione di fibonacci assumendo erroneamente che $fib(0) = 1$ anziché $fib(0) = 0$.
Ah, ed ho anche trovato qui la formula per calcolare l'n-esimo termine della successione.
Mi rimangono però i dubbi che ho esposto sopra...
Hai fatto già metà lavoro. 
Io estenderei il problema nel trovare non solo le sequenze di una consecutività, ma anche quelle di 2, 3, fino al massimo di N.
Nell'esempio con N=5 abbiamo $2^5$ disposizioni e quindi 6 consecutività diverse ( da 0 a 5 ). I due estremi, avranno sempre una sola frequenza [00000] [11111].
Si potrebbe costruire una sorta di Triangolo, cosi' da verificare in che modo le frequenze cambiano, ed eventualmente cercare un algoritmo per calcolarle.
Io estenderei il problema nel trovare non solo le sequenze di una consecutività, ma anche quelle di 2, 3, fino al massimo di N.
Nell'esempio con N=5 abbiamo $2^5$ disposizioni e quindi 6 consecutività diverse ( da 0 a 5 ). I due estremi, avranno sempre una sola frequenza [00000] [11111].
Si potrebbe costruire una sorta di Triangolo, cosi' da verificare in che modo le frequenze cambiano, ed eventualmente cercare un algoritmo per calcolarle.
Intendevo qualcosa di simile, in blu ho messo la serie che hai già calcolato [Fibonacci - 1]
Secondo me sei sulla strada giusta. Vedi che avevo ragione? Contare!
Innanzi tutto grazie per le risposte!
In effetti questo era quello che avevo intenzione di fare, solo che avevo pensato di farlo suddividendo i vari casi... anche se in effetti probabilmente ha molto più senso considerare tutto insieme come nell'immagine e costruire qualche livello del triangolo ed analizzarlo.
C'è da considerare però che quel che ne uscirà sarà valido solo per il caso $p=1/2$ (dove $p$ è il parametro della bernoulliana $X$ del primo post).
Beh, ad ogni modo sarebbe già un qualcosa di non poco conto!
Vedo che hai già costruito i livelli da $0$ a $8$... ma per il conteggio delle sequenze come hai fatto? Hai delegato un programmino? Non dev'essere proprio il massimo considerare uno ad uno tutti i $2^8$ sequenze.. anche perché si perderebbe un po' di tempo (oltre che la testa), specie per $N$ maggiori
Io inizialmente avevo pensato per varie ragioni di escludere il supporto della programmazione per questo quesito... anche perché pensavo che sarebbe stato magari un pochino più semplice! Ma a questo punto non mi rimane che rimboccarmi le maniche ed iniziare a scrivere qualche riga di codice per creare ed analizzare questo benedetto triangolo... ed infine ovviamente fare test empirici a manetta sfruttando la random!
A tal proposito vi chiedo: secondo voi potrebbe avere qualche implicazione il fatto di eseguire dei test con dei numeri pseudo-casuali? Ai miei fini (ovvero quelli di verifica), posso considerarli casuali a tutti gli effetti?
Secondo me sì... cmq farò qualche test anche sulla distribuzione...
Vi terrò aggiornati!
"Umby":
Hai fatto già metà lavoro.
Io estenderei il problema nel trovare non solo le sequenze di una consecutività, ma anche quelle di 2, 3, fino al massimo di N.
In effetti questo era quello che avevo intenzione di fare, solo che avevo pensato di farlo suddividendo i vari casi... anche se in effetti probabilmente ha molto più senso considerare tutto insieme come nell'immagine e costruire qualche livello del triangolo ed analizzarlo.
C'è da considerare però che quel che ne uscirà sarà valido solo per il caso $p=1/2$ (dove $p$ è il parametro della bernoulliana $X$ del primo post).
Beh, ad ogni modo sarebbe già un qualcosa di non poco conto!
Vedo che hai già costruito i livelli da $0$ a $8$... ma per il conteggio delle sequenze come hai fatto? Hai delegato un programmino? Non dev'essere proprio il massimo considerare uno ad uno tutti i $2^8$ sequenze.. anche perché si perderebbe un po' di tempo (oltre che la testa
), specie per $N$ maggioriIo inizialmente avevo pensato per varie ragioni di escludere il supporto della programmazione per questo quesito... anche perché pensavo che sarebbe stato magari un pochino più semplice! Ma a questo punto non mi rimane che rimboccarmi le maniche ed iniziare a scrivere qualche riga di codice per creare ed analizzare questo benedetto triangolo... ed infine ovviamente fare test empirici a manetta sfruttando la random!
A tal proposito vi chiedo: secondo voi potrebbe avere qualche implicazione il fatto di eseguire dei test con dei numeri pseudo-casuali? Ai miei fini (ovvero quelli di verifica), posso considerarli casuali a tutti gli effetti?
Secondo me sì... cmq farò qualche test anche sulla distribuzione...
Vi terrò aggiornati!
"The_Mad_Hatter":
Vedo che hai già costruito i livelli da $0$ a $8$... ma per il conteggio delle sequenze come hai fatto? Hai delegato un programmino? Non dev'essere proprio il massimo considerare uno ad uno tutti i $2^8$ sequenze.. anche perché si perderebbe un po' di tempo (oltre che la testa
Io inizialmente avevo pensato per varie ragioni di escludere il supporto della programmazione per questo quesito... anche perché pensavo che sarebbe stato magari un pochino più semplice! Ma a questo punto non mi rimane che rimboccarmi le maniche ed iniziare a scrivere qualche riga di codice per creare ed analizzare questo benedetto triangolo... ed infine ovviamente fare test empirici a manetta sfruttando la random!
Certo. Ho scritto 4 righe di codice per generare le varie serie. Fare i conteggi a mano è da manicomio.
Il mio obiettivo era quello di scoprire altri algoritmi (un po come hai fatto per la riga in BLU), pur immaginando che non necessariamente debba esistere un algoritmo.
"The_Mad_Hatter":
A tal proposito vi chiedo: secondo voi potrebbe avere qualche implicazione il fatto di eseguire dei test con dei numeri pseudo-casuali? Ai miei fini (ovvero quelli di verifica), posso considerarli casuali a tutti gli effetti?
Secondo me sì... cmq farò qualche test anche sulla distribuzione...
Non ho ben capito, cosa intendi fare con i numeri random.
Trascurando la "lentezza" del nostri pc, si potrebbe generare un triangolo di qualsiasi dimensione.
"Umby":
Certo. Ho scritto 4 righe di codice per generare le varie serie. Fare i conteggi a mano è da manicomio.
ahaha ottimo allora
Il mio obiettivo era quello di scoprire altri algoritmi (un po come hai fatto per la riga in BLU), pur immaginando che non necessariamente debba esistere un algoritmo
Già infatti. Ma d'altronde pensandoci quello non era nemmeno un buon modo di procedere.. il triangolo mi ha messo chiaramente di fronte all'errore che stavo facendo: non ha molto senso cercare le relazioni per le sequenze tali che $Y=k$ al variare di $N$, per quanto curioso possa essere scoprire che ce ne possano essere di così strane (e chi s'immaginava di ritrovare fibonacci!
), perché trovare $P(Y=k)$ significa trovare le relazioni tra le righe del triangolo e non tra le varie "trasversali".. non so se mi sono spiegato.Ad ogni modo, ho parlato di questo problema con il mio prof di statistica, che mi ha fatto capire che il difficile del trovare una funzione di probabilità esplicita risiede principalmente nel fatto che vi sia una unione di eventi non disgiunti... ora non ne ho il tempo, ma un po' anche per 'dovere di cronaca' ritornerò la prossima volta su questo argomento!
Non ho ben capito, cosa intendi fare con i numeri random.
Trascurando la "lentezza" del nostri pc, si potrebbe generare un triangolo di qualsiasi dimensione.
Sì sì certo questo è ovvio!
Per quanto riguarda il random, volevo semplicemente testarlo un po' facendo un ciclo di qualche migliaio di iterazioni per poi verificare le frequenze dei vari numeri generati... insomma dato che il random genera numeri pseudo-casuali non vorrei che questo possa in un certo qual modo viziare i risultati dei test. Si tratta semplicemente di una mia fissazione, anche per la curiosità di capire se gli pseudo-casuali possano essere considerati random a tutti gli effetti (ed entro un certo margine, credo di sì).
Scusate se non sono stato molto chiaro ma sono un po' stanco! Non sono riuscito ancora a trovare tempo per andare avanti, comunque il prossimo passo sarà fare il programmino per generare il triangolo e, stavolta, analizzarne le righe, anche solo per avere un'idea un po' meno approssimativa di come si sviluppa graficamente $F_Y$ (anche se l'idea già ce l'ho). Anche perché, di trovare una relazione esplicità solo osservando qualche riga del triangolo.....
Buona notte a tutti
"The_Mad_Hatter":
Già infatti. Ma d'altronde pensandoci quello non era nemmeno un buon modo di procedere.. il triangolo mi ha messo chiaramente di fronte all'errore che stavo facendo: non ha molto senso cercare le relazioni per le sequenze tali che $Y=k$ al variare di $N$, per quanto curioso possa essere scoprire che ce ne possano essere di così strane (e chi s'immaginava di ritrovare fibonacci!
Chiarissimo.
Ho disegnato il tringolo proprio per capire in che modo le righe, le colonne, le trasversali, in generale come si componevano le varie "serie".
Un esempio:
Se guardi bene il triangolo ti accorgi che il valore centrale, si ripete trasversalmente verso destra. Guarda ad esempio il 5 centrale, te lo ritrovi anche sull'ultima riga.
E' facile trovare un algoritmo per la determinazione di questa colonna centrale:
$X = (n+3) * 2^(n-2)$
A questo punto, trovando questa colonna (disegnata in nero), possiamo dire che è la stessa mezza riga (la parte destra) (disegnata in verde).
Quindi metà triangolo è stato già risolto.
P.s. Tutti i dati andrebbero verificati ampliando la base del triangolo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo