[Esercizio] Infiniti lanci di una moneta.

[DajeForte]

Suppose that a coin with probability p of heads is tossed repeatedly. Let $A_k$ be the event that a sequence of $k$ (or more) consecutive heads occurs amongst tosses numbered $2^k,\ 2^{k }+ 1,\ 2^{k} + 2, ... ,\ 2^{k + 1} - 1$.
Calculate $P(A_k, i.o .)$ (il limsup degli $A_k$).

Hint

Borel Cantelli

[frapippo1]

Non mi è chiarissimo il testo. Per esempio, cosa indica l'evento $A_3$?

[DajeForte]

Neanche a me...ahahah.

Diciamo che lo tradurrei così:

Si supponga che una moneta, che ha probabilità $p$ di Testa, sia lanciata ripetutamente.
Sia $A_k$ levento che "una sequenza di $k$ o più teste accada consecutivamente tra i lanci numerati $2^k,\ 2^{k }+ 1,\ 2^{k} + 2, ... ,\ 2^{k + 1} - 1$. Calcolare la probabilità del limsup degli $A_k$.

[frapippo1]

La traduzione l'avevo capita..per esempio $A_3$ è l'evento per cui si hanno almeno 3 teste tra i lanci 8 e 15?

[DajeForte]

ahahah...scusa

Direi di si, però consecutiva,
ovvero esiste $j=8,9,...13$ tale che i lanci $j,\ j+1,\ j+2$ hanno Testa (possono essere anche di più di tre)

quindi direi tra i lanci $2^k$ e $2^{k+1}-1$ esiste una sequenza consecutiva di lunghezza maggiore o uguale a k di teste.

[Andrea2976]

Aggiungo solo una precisazione al suggerimento di Daje, il lemma di B.C. (uso l'acronimo per non spoilerare il suggerimento di Daje) si applica a eventi indipendenti.

Tra gli indici $2^{k+1}-1$ e $2^k$ ci sono $2^{k+1}-1-2^k=2^k-1$ lanci. La probabilità dell'evento $A_k$ è tale che

$P(A_k)\le \sum_{n=k}^{2^k-1} ((2^k-1),(n)) (\frac{p}{1-p})^n(1-p)^{2^k-1}$

Ora entra in gioco la dipendenza\indipendenza degli eventi $A_k$ e la serie delle $P(A_k)$.

[frapippo1]

"Andrea2976":Aggiungo solo una precisazione al suggerimento di Daje, il lemma di B.C. (uso l'acronimo per non spoilerare il suggerimento di Daje) si applica a eventi indipendenti.

Il secondo BC si, per il primo non è richiesta l'indipendenza.

Molto intuitivamente io direi che la ricercata probabilità è zero, visto che è impossibile osservare "infinitamente spesso" sequenze crescenti consecutive di teste..Chiaramente intuito non vuol dire "dimostrazione"..

[Andrea2976]

Provo a buttare lì un conto che mi è venuto in mente, magari aspetto smentita da Daje per aver sparato col cannone.

Inidico con $S_{2^k-1}$ la somma di v.a. bernoulliane (cioè una binomiale di parametri $2^k-1$ e $p$), ora considero l'evento $A_k={S_{2^k-1}>k}$:

$P(S_{2^k-1}-E(S_{2^k-1})>k)\leq e^{-\frac{2k^2}{2^k-1}}$ (disuguaglianza di Hoeffding), da cui

$P(S_{2^k-1}>k+(2^k-1)p)\leq e^{-\frac{2(k+(2^k-1)p)^2}{2^k-1}}$.

[DajeForte]

"Andrea2976":$A_k={S_{2^k-1}>k}$:

Questo non è vero, perchè se interpreto bene l'inglese (post di apertura) la sequenza di k deve essere consecutiva;
inoltre fai attenzione che i lanci sono tra $2^k$ e $2^{k+1}-1$ sono $2^k$.

Certo uno potrebbe dire che $A_k sube (S_{2^k} >=k)$ perchè se ho almeno $k$ successi consecutivi devo avere almeno $k$ successi in generale.
Credo dunque ci sia qualcosa che non vada...ci rifletto su e mi faccio vivo.

[Andrea2976]

Ovviamente hai ragione, però ad occhio mi sembra che come dici tu che l'evento $A_k$ sia contenuto in ${S_{2^k}>k}$ e così possa andare.

Andrea

P.S.Voi mi intrigate sempre con questi esercizi (mentre lavoro) poi mi dimentico qualcosa...e non ricordo il perché stia lavorando nel mondo della finanza invece di fare "matematica", di quella seria. Meno male che c'è matematicamente... .

[fu^2]

osserviamo che tra $2^k$ e $2^{k+1}-1$ ci sono $2^{k}-1$ numeri.

Poniamo $A_k=\{\text{ottenere k o più teste consecutive in tale intervallo}\}$, dobbiamo stimare la $\mathbb{P}(A_k)$.

Siano $X_i$ v.a. di bernulli indipendenti, con $\mathbb{P}(x_i=1)=p$.

Sia $\tau_1=\inf\{i\geq 1: X_i=0\}$ . Sappiamo che $\mathbb{P}(\tau_1=k)=(1-p)(p)^{k-1}$.

Allo stesso modo poniamo $\tau_n=\inf\{i> \tau_{n-1}: X_i=0\}$.
Allora, per Markov, posto $\tau_0=0$, si ha che $\eta_i=\tau_i-\tau_{i-1}$ è una sequenza di v.a. iid con distribuzione geometrica.

Si ha che $A_k^c=\{\text{non esiste i tc } \tau_i-tau_{i-1}\geqk\}=\bigcap_{i=1}^{2^k-1}{\tau_i-\tau_{i-1} $\prod_{i=1}^{2^k-1}(1-p)(\frac{1-p^{k-1}}{1-p})=(1-p^{k-1})^{2^k-1}$ da cui possiamo ricavare la probabilità di $A_k$.

Ora questo è uno spunto... è tardi e coi conti farei solo casino... rimane da discutere la convergenza della serie $\sum \mathbb{P}(A_k)$ per applicare B.C.


Spero di non aver scritto troppe cavolate e che il ragionamento sia quantomeno interessante

[DajeForte]

Ciao fu, è un po' che non ti si vedeva in giro.
Nel tuo post ci sono spunti interessanti e sopratutto quel ragionamento sui tempi d'arresto.
Però c'è un problema quando dici che:

Si ha che $A_k^c=\{\text{non esiste i tc } \tau_i-tau_{i-1}\geqk\}=\bigcap_{i=1}^{2^k-1}{\tau_i-\tau_{i-1}
non c'è bisogno di considerare tutte le differenze degli stopping time, o meglio non o sai.

Prendi k=3 e dunque i lanci da 8 a 15 (che sono $8=2^k$ e non $2^k-1$)
non c'è bisogno di considerare otto geometriche, prendi ad esempio TTHTTHTT (in numeri 11011011) hai due soli stopping time degli 0.
Bisognerebbe fare un ragionamento integrato anche con $S_{2^k}$ la binomiale che conta quanti 1 (o 0) ci sono stati nei lanci.

Però qualche spunto interessante me lo ha dato...

[fu^2]

si è vero, bisognerebbe riuscire a troncare l'intersezione all'ultimo tempo d'arresto utile, come hai mostrato nel tuo esempio.

Ci penserò su...

anche se ponendo $\t_i=\min\{\text{inf}\{i>\tau_{i-1}: X_i=0\} ,2^k-1\}$ con la convenzione $\text{inf}\emptyset=+\infty$ si ha che, nell'intersezione che mi hai contestato, si "autoeliminano" i tempi d'arresto che sono vuoti, non so se mi spiego...

Poi il ragionamento dovrebbe funzionare, comuqnue ci penso su...

[Andrea2976]

Guardando un po' in giro ho provato a chiarirmi le idee.

L'interesse sta nel capire la distribuzione delle sequenze di $k$ teste consecutive su un numero fissato di lanci per avere un'idea precisa del comportamento asintotico.

Nel teorema 2.1. in : http://www.emis.de/journals/AMI/2009/ami2009-turi.pdf
c'è la soluzione al quesito sulla distribuzione delle sequenze dellle $k$ teste. A questo punto applicando Borel-Cantelli si giunge nuovamente alla soluzione desiderata.

Cito anche questo link che contiene alcuni risultati combinatorici in merito al problema:
http://www.emis.de/journals/AUSM/C2-2/math22-9.pdf

Penso che potrebbe esserci un approccio più semplice al tutto...forse.

P.S. Ho modificato il mio post precedente in quanto avevo sbagliato misaramente l'applicazione della disuguaglianza di Hoeffding.

[DajeForte]

Riposto il quesito iniziale e lo invito a rieggere per vedere se la sua interpretazione risulta corretta.

"DajeForte":Suppose that a coin with probability p of heads is tossed repeatedly. Let $A_k$ be the event that a sequence of $k$ (or more) consecutive heads occurs amongst tosses numbered $2^k,\ 2^{k }+ 1,\ 2^{k} + 2, ... ,\ 2^{k + 1} - 1$.
Calculate $P(A_k, i.o .)$ (il limsup degli $A_k$).

Questo perchè alla fine del problema vi è scritto:

"Prove that $P(A_k,i.o .)$ is equal 0 if $p<1/2$ and 1 if $p>=1/2$.

Poi c'era questo Hint:


Hint. Let $E_j$ be the event that there are k consecutive heads beginning at
toss numbered $2^k +(i-1)k$. Now make a simple use of the inclusion-exclusion
formulae.