Una variante dell'urna di Polya

[Andrea2976]

Consideriamo il seguente processo d'urna:

L'urna contiene una (ed una sola) pallina bianca e un numero aleatorio di palline rosse.
Si procede ad una successione di estrazioni con reinserimento secondo lo schema seguente:
se si estrae la pallina bianca se ne aggiunge una rossa (e si reinserisce la pallina bianca estratta);
se si estrae una pallina rossa non si aggiunge nessuna pallina (si reinserisce la pallina rossa estratta).

Supponiamo che l'urna contenga inizialmente solamente l'unica pallina bianca.
Calcolare la media e la varianza del numero di palline rosse dopo $n$ estrazioni.

Buon divertimento!

[fu^2]

a me è venuto $n/2$ per ora la media, ma mi puzza... (per la varianza non c'ho ancora pensato) diciamo che mi aspetterei una crescita più lenta o quantomeno non lineare... infatti il loro numero dovrebbe diventare stazionario con grandissima probabilità (in quanto la probabilità di inserirne una nuova è di 1/N) e quindi crearsi un gap crescente tra il numero dell'estrazione e il numero di palline rosse presenti... nei prossimi giorni posto magari qualche calcolo

[Andrea2976]

Ciao a tutti, son contento di vedere che il problema abbia riscontrato interesse in breve tempo.
Per inciso: il problema della determinazione della media e della varianza si può affrontare tramite ragionamenti elementari (ma ogni matematico sa che "elementare" non implica "semplice"). Comunque sia consiglio di provare a formalizzare il problema in termini di una successione di v.a. (lascio a voi scoprire il tipo) dipendenti.

Ulteriore consiglio, per la media e la varianza consiglio di lavorare con le medie condizionate.

Andrea

P.S. Per TeM rispondo alla domanda: "Tu hai una soluzione "ufficiale" del problema?"
Sì, è possibile calcolare anche una formula chiusa per la distribuzione di probabilità in funzione di $n$, ma richiede un po' di lavoro. A conclusione della discussione posterò il link con tutto il procedimento.

P.S. Per Fu: sei sulla strada giusta, inoltre in questo caso sussistono risultati di "concentrazione" (la tua affermazione sul "gap")

[fu^2]

Il problema l'ho affrontato con un po' di martingalità inizialmente avevo optato per metodi elementari, che si erano rivelati un po' troppo calcolotici. Purtroppo (o per fortuna) il calcolo che avevo fatto precedentemente era sbagliato (ho commentato dove avevo sbagliato), ma ora ho tirato fuori sono due stime. Inizio a postarle, magari qualcuno ne prende ispirazione

Sia $X_n$ il numero di palline rosse dopo l' $n$-esima estrazione, allora si ha che
$X_0=0$,
$X_n=X_{n-1}+Y_n$,

dove $Y_{n}\in \{0,1\}$ è definita attraverso la sua speranza condizionata nel seguente modo $E(Y_n|X_{n-1})=P(Y_n=1|X_{n-1})=1/(X_{n-1}+1)$ (il +1 è dovuto al fatto che c'è anche una pallina bianca, $Y_n$ rappresenta cosa ho pescato all'$n$-esima estrazione: euristicamente $P(Y_k=1)=P(\text{ho pescato la bianca all'n-esima estrazione})$).
Ovviamente $E(Y_n|X_{n-1})=E(Y_n|X_{n-1},...,X_1,X_0)$.

A questo punto
$E(X_n|X_{n-1})=E(X_n|X_{n-1},...,X_1,X_0)=X_{n-1}+1/{X_{n-1}+1}\geq X_{n-1}$
siamo dunque ad un'urna di polia modificata per essere una bella submartingala!

Dunque utilizzando la decomposizione di Doob per submartingale discrete abbiamo che $X_n=Z_n+A_n$ dove $Z_n$ è una martingala e $A_n$ è un processo prevedibile e crescente. Vogliamo trovare il processo prevedibile (ovvero $\mathcal{F}_{n-1}=\sigma(X_0,...,X_{n-1})$-misurabile). Utilizzando questa espressione otteniamo che

$E(X_n|X_{n-1})=Z_{n-1}+A_n=X_{n-1}+1/{X_{n-1}+1}=Z_{n-1}+A_{n-1}+1/{X_{n-1}+1}$ da cui $A_n-A_{n-1}=1/{X_{n-1}+1}$ e tenuto conto che $A_0=0$ otteniamo che

$A_n=\sum_{j=0}^{n-1} 1/(X_{n-j}+1)$.

Dunque, tenuto conto che $Z_0=0$ abbiamo che

$E(X_n)=\sum_{j=1}^n E(1/(1+X_{n-j}))=\sum_{j=1}^n E(E(Y_{n-j}|X_{n-j-1}))=\sum_{j=1}^{n} E(Y_{n-j})=\sum_{j=1}^{n} E(Y_{j})=\sum_{j=1}^{n} P(Y_j=1)$.

Dobbiamo quindi calcolare $P(Y_k=1)$. Questo calcolo è quello che mi puzzava, ovviamente non può essere costante nel tempo, basta calcolare il caso $k=1$ ed $k=2$ per rendersene conto (sarà una funzione di $n$) Procediamo con una stima dal basso e una dall'alto.

La probabilità è minima se $X_{k-1}=k-1$ (utilizzando la speranza condizionata) si ha che $P(Y_k=1)\geq 1/k$ (se si vuole si può "pensare all'entropia") da cui ricaviamo $\sum_{j=1}^n 1/(j)\leq\sum_{j=1}^{n} P(Y_j=1)$.
Viceversa $P(Y_k=1)=\sum_{j=1}^{k-1}P(Y_k=1|X_{k-1}=j)P(X_{k-1}=j)=\sum_{j=1}^{k-1}1/(j+1)P(X_{k-1}=j)\leq \sum_{j=1}^{k-1}1/(j+1)$, da cui ricaviamo che $E(X_n)\leq \sum_{k=1}^n\sum_{j=2}^k 1/j$.

Dunque per $n\to \infty$ otteniamo che (la stima è fatta via approssimazione integrale della serie)

$c\logn \leq E(X_n)\leq Cn\log n$,

dove $c,C$ sono due opportune costanti .
Qualche considerazione: la cosa negativa è che esso è superozzo! in quanto la stima dal basso e dall'alto "divergono", dando stime molto grossolane per $n\to \infty$.
Inoltre la stima dal basso ci dice comunque che la media diverge nel limite per $n\to \infty$.

per la varianza ci penserò su prossimamente

[Andrea2976]

Ciao Fu,

la formalizzazione è la stessa che ho usato io per risolverlo, con qualche variante finale per recuperare la media.
Dato che ti stai divertendo, non spoilerò nulla per ora, ma aggiungo solo qualche consiglio.

Per la media conviene conviene pensare al processo d'urna come a un processo di rinnovo.
Calcolata la media, la varianza viene più facilmente.

Questa urna ha una sua controparte "continua", io inizalmente avevo lavorato sul problema continuo e poi l'ho riportato al caso discreto.

Per la media confermo la divergenza, il primo indizio è notare che il processo sia una submartingala, poi usando Borel- Cantelli si ottine il risultato se si pensa a tale processo come successione v.a. b... dipendenti

[Andrea2976]

Ciao TeM, il tuo ragionamento non mi sembra molto lineare.
Non capisco come fai a dedurre che la v.a. $r$ sia uniforme, inoltre il calcolo a mano che proponi all'inizio e quello al limite che fai alla fine mi sembrano discordanti.

Se hai voglia ti propongo di seguire la formalizzazione di Fu che agevola di molto i calcoli e i ragionamenti.

[Andrea2976]

Ciao TeM,

rileggendo il mio post iniziale ho capito il tuo dubbio.
Il termine aleatorio era riferito alla sola aleatorietà del numero sole palline rosse, rispetto all'unica bianca.
Ovviamente come hai fatto tu si può assumere una distribuzione di probabilità a priori del numero delle palline rosse, tuttavia dato che il processo sottostante non ammette una distribuzione stazionaria (dato che in ogni caso il numero delle palline rosse divergerà) è più comodo partire dalla assunzione: "Supponiamo che l'urna contenga inizialmente solamente l'unica pallina bianca."

L'interesse è capire l'andamento nel tempo e l'eventuale distribuzione limite delle palline rosse, anticipo che la cosa interessante è che nonostante una struttura di dipendenza si riottengono alcuni risultati classici come nel caso i.i.d.

Andrea

[Covenant]

Premetto che ho iniziato da poco a studiare i processi stocastici. Mi chiedevo, è possibile modellizzare il processo di estrazione come una catena di Markov? la mia idea era di partire dal "difficile" e trovarmi la distribuzione esplicita delle palline rosse nell'urna utilizzando la matrice di transizione. Non so neppure se la cosa sia fattibile all'atto pratico visto che i calcoli sembrano tanti e tutt'altro che semplici...

[Andrea2976]

Ciao Covenenant,

è possibile modellizzare il processo d'urna come una processo di markov, tuttavia in questo caso lavorare sulla matrice di transizione non è agevole.

La domanda si referiva al calcolo della media e della varianza perchè è possibile ottenerle con tecniche elementari, una volta formalizzato il problema in un certo modo (vedi post di "Fu").

Per inciso, il problema io lo ho affronatato in toto in un parte della mia tesi di dottorato (in matematica ovviamente), ma la parte di media e varianza è affrontabile avendo una certa dimestichezza dei concetti base del calcolo delle probabilità.

Alla fine posterò il link con tutti i calcoli e le dimostrazioni se siete interessati.

Andrea

[fu^2]

se la frebbe non porta cattivi consigli mi sa che devo rimangiarmi alcune credenze su questo problema

"Andrea2976":Ciao Fu,

la formalizzazione è la stessa che ho usato io per risolverlo, con qualche variante finale per recuperare la media.
Dato che ti stai divertendo, non spoilerò nulla per ora, ma aggiungo solo qualche consiglio.

Per la media conviene conviene pensare al processo d'urna come a un processo di rinnovo.
Calcolata la media, la varianza viene più facilmente.

Effettivamente...
Introduciamo le seguenti variabili aleatorie
$S_1=\text{inf}\{k>0 : Y_k=1\}$, $S_1$ è distribuita come una geometrica di parametro $1/2$ ($G(1/2)$),

$S_m=\text{inf}\{k> S_{m-1}: Y_k=1\} $ e questa ha distribuzione geometrica $G(1/(m+1))$.

Dunque, riusando le notazioni introdotte precedentemente possiamo notare che $\{S_{j-1}=j-1\}\cap \{Y_j=1\}=\{S_{j-1}=j-1\}\cap \{S_j=j\}$ e dunque $P(Y_j=1)=P(S_j=j|S_{j-1}=j-1)=1/(j+1)$ dalla definizione. Concludendo

$X_n=\sum_{k=1}^n Y_k=\sum_{k=1}^n 1_{Y_k=1}=\sum_{k=1}^n 1_{S_k=k|S_{k-1}=k-1}$ da cui ricaviamo che

$E(X_n)=\sum_{k=2}^{n+1}1/k$, che soddisfa le stime date in precedenza (in particolare cresce in maniera logaritmica).

Per la varianza penso si possano fare calcoli analoghi, utilizzando la scrittura $X_n=\sum_{k=1}^n 1_{Y_k=1}$ (devo ancora fare in dettaglio ), da cui si ricava che, tenendo conto che le v.a. $Y_k$ sono scorrelate (questo è il punto che devo ancora sistemare, questa affermazione è detta più o meno senza prova...)

$Var(X_n)=\sum_{k=1}^{ n}\frac{1}{k+1}( 1-\frac{1}{k+1})$.

Spero di non aver detto troppe sciocchezza

"Andrea2976":

Questa urna ha una sua controparte "continua", io inizalmente avevo lavorato sul problema continuo e poi l'ho riportato al caso discreto.

Per la media confermo la divergenza, il primo indizio è notare che il processo sia una submartingala, poi usando Borel- Cantelli si ottine il risultato se si pensa a tale processo come successione v.a. b... dipendenti

finito questo problema sono curioso di sapere da dove viene fuori questo problema che hai proposto e il problema continuo

[Andrea2976]

Ciao,

lascio il link così spero di fugare i vostri dubbi: http://arxiv.org/abs/1109.0180
Paragrafo 2: Urna


Per "Fu": L'approccio con le v.a. geometriche è lo stesso che usai io, tuttavia ti stai perdendo qualcosa.
La media della geometrica è data da $\frac{1}{p}$, dove $p$ è la probabilità di successo (probabilmente hai avuto una piccola svista quando hai calcolato la media).

La media che tu calcoli tramite le geometriche è uguale al numero di lanci necessari perché l'urna contenga $k$ palline rosse, quindi devi trovare la relazione tra $n$ e $k$ per avere la media al passo $n$.

Il bound logaritmico che trovate (in maniera non corretta) tu e TeM è un bound dal basso. Lo si può vedere pensando che il processo d'urna domina (stocasticamente) la successione di v.a. $\sum_{i=0}^{n} X_i$ con $X_i \sim Ber(\frac{1}{1+i}) $ indipendenti.

[fu^2]

esatto, il bound logaritmico, se leggi nel mio primo post, è trovato come hai detto te.
Effettivamente sbirciando il tuo (penso tuo) articolo ho capito il mio errore (avevo messo la media spostata a dopo l'estrazione ...).

Interessante l'articolo, forse mi è sfuggito, ma da qual'è, giusto per curiosità, il problema continuo da cui sei partito nello studio? (qualche post fa dicevi che questa è una discretizzazione venuta fuori dallo studio di un problema continuo).

[Andrea2976]

Più che un articolo è un preprint che ho messo su arxiv, dato che è estratto dalla mia tesi di dottorato (che ho pubblicato).

La controparte continua dell'urna è il processo di pura nascita che trovi nel paragrafo 1. Dato che nella forma continua era risultato più difficile (di solito è il contrario) ricavare media, varianza, disugualginze di concentrazione etc. l'urna è venuta fuori dallo studio della catena subordinata.

Giusto per farmi un po' di pubblicità (anche se non lavoro più in università) ti lascio questo link dove è trattata la forma più generale per il caso nascita e morte: http://arxiv.org/pdf/1204.6618.pdf

Qui: http://probability.altervista.org/wp-co ... ya_urn.pdf ho inserito due conti su come approcciare il problema tramite la funzione generatrice dei momenti, ma purtroppo in questo modo (che è più elegante di quello proposto nell'altro link) non si riesce a risolvere l'equazione integrale se non calcolandola passo passo.