Tempo medio di uscita di una stringa

Definizione

Nella teoria delle probabilità il tempo medio di uscita di una stringa è il calcolo della previsione di uscita di una stringa prefissata di $k$ caratteri estraendo casualmente le lettere da un insieme finito di caratteri, dato dalla formula $𝐄[U]=\sum _{h\in H}{m}^h$, dove:

• $m$ è il numero totale di caratteri dell'alfabeto di riferimento
• $H$ è un insieme di indici che contiene i valori
  • la posizione del primo carattere, pari a $\text{1}$
  • la posizione dell'ultimo carattere, pari alla lunghezza $k$ della stringa
  • le posizioni di ogni sotto-stringa ripetuta all'interno della stringa
• $U$ è una variabile aleatoria che definisce il tempo di uscita della stringa

Per calcolare la previsione è necessario anche conoscere la probabilità di uscita di un carattere dall'insieme totale dei caratteri, dato da $P\{X_n=i\}$, dove $X_n$ è una variabile aleatoria che può assumere i valori di un carattere dell'alfabeto, mentre l'evento $\{X_n=i\}$ definisce l'uscita del carattere $i$ alla $n$-esima estrazione.

Esempio

Si calcola la previsione del tempo medio di uscita della parola ABRACADABRA utilizzando l'alfabeto inglese composto da ventisei lettere.

Utilizzando la definizione si ha che $\{\begin{array}{c}m=26\\ k=11\\ H=\{1,4,11\}\\ P\{X_n=i\}=\frac{1}{26}\end{array}$

Si osserva che $H$ contiene le posizioni del primo e dell'ultimo carattere, oltre alla posizione dell'ultimo carattere della sotto-stringa ABRA ripetuta.

Da ciò ne deriva che $𝐄[U]=26^1+26^4+26^{11}\simeq 3.67\times 10^{15}$, ossia il tempo medio di uscita della parola ABRACADABRA è dopo aver effettuato circa $3670$ miliardi di digitazioni casuali su una tastiera di $26$ caratteri.

Passaggio al limite

Si può facilmente vedere che la previsione del tempo medio di uscita di una stringa è una funzione divergente all'aumentare del numero di caratteri da estrarre. Pertanto, il limite della previsione per un numero di caratteri che tende all'infinito è pari a infinito, ossia $\underset{k\to \mathrm{\infty }}{\lim }(\sum _{h\in H}{m}^h)=\mathrm{\infty },\mathrm{\forall }m>1$.

Intuitivamente si può calcolare il limite, considerando l'ipotesi che non esistano sotto-stringhe ripetute. Se questo limite tende a infinito a maggior ragione il limite nel caso di ripetizioni tende ad infinito. Si può non tenere conto dell'indice iniziale, pari sempre a uno, in quanto nel calcolo del limite sarebbe una costante. In base a queste considerazioni si osserva che $m^k⩽\sum _{h\in H}{m}^h,\mathrm{\forall }m>1$ e se il limite di $m^k$ per $k$ che tende a infinito è pari a infinito, allora anche il limite $\sum _{h\in H}{m}^h$ sarà pari a infinito. Per ogni $m>1\in \mathbb{N}$ la funzione $m^k$ è divergente, quindi $\underset{k\to \mathrm{\infty }}{\lim }{m}^k=\mathrm{\infty }$.

Enunciato

Sia $C=\{1,2,\dots ,m\}$ un insieme di $m$ caratteri, con $m\in \mathbb{N}\setminus \{0\}$. Si può definire una stringa prefissata $(a_j{)}_{1⩽j⩽k}$ di lunghezza $k$ caratteri tale che $a_j\in C,\mathrm{\forall }j=1,\dots ,k$.

Sia $(\mathrm{\Omega },𝒜,P)$ uno spazio di probabilità, tale che $\mathrm{\Omega }=\{1,\dots ,m\}$, $𝒜$ è una $\sigma$-algebra di $\mathrm{\Omega }$ e $P$ una misura di probabilità sullo spazio $(\mathrm{\Omega },𝒜)$. Su questo spazio si può costruire una successione di variabili aleatorie $(X_n{)}_{n>0}$ tali che $P\{X_n=i\}=\frac{1}{m}=p,\mathrm{\forall }n>0,i\in C$.

Sia $T=\inf \{n:X_{n+j}=a_j,\mathrm{\forall }j=1,\dots ,k\}$ il tempo più piccolo entro il quale al tempo $n+j+k$ la successione $(X_n{)}_n$ realizza la stringa $(a_j{)}_j$. Si definisce $U=T+k$ il tempo di uscita della stringa.

Si prova che $𝐄[U]=\sum _{h\in H}{m}^h$, con $H=\{h:1⩽h⩽k,a_{k-h+j}=a_j,\mathrm{\forall }j=1,\dots ,k\}$.

Dimostrazione

Sia $F=(F_n{)}_n$ una filtrazione tale che $F_0=\{\varnothing ,\mathrm{\Omega }\}$ e $F_n=\sigma (X_1,X_2,\dots ,X_n)$, ossia la $\sigma$-algebra generata dalla successione di variabili aleatorie al tempo $n$.

Osservazione 1

$T$ e $U$ sono dei tempi di arresto rispetto a $F$

Per il paradosso di Borel $P\{X_{n+1}=a_1,X_{n+2}=a_2,\dots ,X_{n+k}=a_k\}=1$, ossia la probabilità di ottenere la sequenza $(a_j{)}_j$ digitando casualmente le lettere di una tastiera è quasi certa. Da ciò deriva che $P\{T<\mathrm{\infty }\}=1$. Anche $U$ è un tempo di arresto rispetto a $F$ in quanto, essendo $k$ una costante,$P\{T+k<\mathrm{\infty }\}=P\{U<\mathrm{\infty }\}=1$

Osservazione 2

$P\{T+k>n\}=\sum _{h\in H}\left(\prod _{j=1}^h\frac{1}{p}\right)P\{T+k=n+h\}$

Si definisce una successione di variabili aleatorie indipendenti, per ogni $n$ fissato, $(Y_j^{(n)}{)}_{j>0}$ tale che $Y_j^{(n)}=\frac{1}{p}{\mathrm{I}}_{\{X_{n+j}=a_j\}},\mathrm{\forall }j=1,\dots ,k$. La successione è indipendente in quanto è funzione della successione $(X_n{)}_n$, anch'essa indipendente.

Per ogni $j$ si osserva che la previsione di $Y_j^{(n)}$ è pari a uno. Infatti $𝐄[Y_j^{(n)}]=\frac{1}{p}p=1$

Si pone $M_j^{(n)}=\{\begin{array}{c}1\text{ se }0⩽j⩽n\\ \prod _{j=1}^h{Y}_j^{(n)}\text{ se }j=n+h,\text{ con }1⩽h⩽k\\ M_{n+k}^{(n)}\text{ se }j>n+h\end{array}$

La successione $(M_j^{(n)}{)}_j$ è una $F$-martingala.

Osservazione 2.1

$T=\inf \{n:M_{n+k}^{(n)}\ne 0\}$

Osservazione 2.2

${\mathrm{I}}_{\{T>n\}}{M}_{n+k}^{(n)}=0$

Si pone $L^{(n)}=M^{(n)|U}=(M_{U\wedge j}{)}_j$, che per la trasformazione secondo Burkholder è anch'essa una $F$-martingala.

Si trova il valore di $L_{n+k}^{(n)}$quando $T>n$.

${\mathrm{I}}_{\{T>n\}}{L}_{n+k}^{(n)}={\mathrm{I}}_{\{T>n\}}{M}_{U\wedge n+k}^{(n)}={\mathrm{I}}_{\{T>n\}}{M}_{T+k\wedge n+k}^{(n)}$

Dato che stiamo considerando il caso che $T>n$, il valore più piccolo tra $T+k$ e $n+k$ è proprio $n+k$

${\mathrm{I}}_{\{T>n\}}{M}_{T+k\wedge n+k}^{(n)}={\mathrm{I}}_{\{T>n\}}{M}_{n+k}^{(n)}={\mathrm{I}}_{\{T>n\}}\prod _{j=1}^k{Y}_j={\mathrm{I}}_{\{T>n\}}\prod _{j=1}^k\frac{1}{p}{\mathrm{I}}_{\{X_j=a_j\}}$

Per definizione di $T$, ossia il più piccolo $n$ tale che la stringa si realizzi, si ha $M_{n+k}^{(n)}=0$ in quanto esiste almeno un carattere $j$ compreso tra $1$ e $k$ dove $X_j\ne a_j$. Come conseguenza si ha che ${\mathrm{I}}_{\{X_{n+j}=a_j\}}=0$ e quindi ${\mathrm{I}}_{\{T>n\}}\prod _{j=1}^k\frac{1}{p}{\mathrm{I}}_{\{X_j=a_j\}}=0$

Osservazione 2.3

${\mathrm{I}}_{\{T+k=n+h\}}{M}_{n+h}^{(n)}=\{\begin{array}{c}{\mathrm{I}}_{\{T+k=n+h\}}(\frac{1}{p}{)}^h,\text{ se }h\in H\\ 0\text{ se }h\in ̸H\end{array}$

Si trova il valore di $M_{n+h}^{(n)}$ quando $T+k=n+h$.

${\mathrm{I}}_{\{T+k=n+h\}}{M}_{n+h}^{(n)}={\mathrm{I}}_{\{T+k=n+h\}}\prod _{j=1}^h{Y}_j^{(n)}$

${\mathrm{I}}_{\{T+k=n+h\}}\prod _{j=1}^h{Y}_j^{(n)}={\mathrm{I}}_{\{T+k=n+h\}}\prod _{j=1}^h\frac{1}{p}{\mathrm{I}}_{\{X_{n+j}=a_j\}}$

${\mathrm{I}}_{\{T+k=n+h\}}\prod _{j=1}^h\frac{1}{p}{\mathrm{I}}_{\{X_{n+j}=a_j\}}={\mathrm{I}}_{\{T+k=n+h\}}\prod _{j=1}^h\frac{1}{p}{\mathrm{I}}_{\{X_{T+k-h+j}=a_j\}}$

Ne segue che

${\mathrm{I}}_{\{T+k=n+h\}}{M}_{n+h}^{(n)}=\{\begin{array}{c}{\mathrm{I}}_{\{T+k=n+h\}}\prod _{j=1}^h\frac{1}{p}={\mathrm{I}}_{\{T+k=n+h\}}(\frac{1}{p}{)}^h,\text{ se }h\in H\\ 0\text{ se }h\in ̸H\end{array}$

In base all'osservazione 2.3 si ha che ${\mathrm{I}}_{\{T+k>n\}}{M}_n^{(n)}=\sum _{h\in H}{\mathrm{I}}_{\{T+k=n+h\}}(\frac{1}{p}{)}^h$

Considerando che $M_n^{(n)}=1$ per definizione si ha che $P\{{\mathrm{I}}_{\{T+k>n\}}1\}=P\{\begin{array}{c}\sum _{h\in H}{\mathrm{I}}_{\{T+k=n+h\}}(\frac{1}{p}{)}^h\end{array}\}$

Dato che la probabilità di una funzione indicatrice corrisponde all'evento stesso si ha che $P\{T+k>n\}=\sum _{h\in H}(\frac{1}{p}{)}^{h}P\{T+k=n+h\}$

Conclusione

$𝐄[U]=\sum _{n}P\{U>n\}=\sum _{n}P\{T+k>n\}$

Per l'osservazione 2 si ha che $\sum _{n}P\{T+k>n\}=\sum _n\sum _{h\in H}(\frac{1}{p}{)}^{h}P\{T+k=n+h\}$

Fissando $h$ e facendo variare $n$ si ottiene che$\sum _n\sum _{h\in H}(\frac{1}{p}{)}^{h}P\{T+k=n+h\}=\sum _{h\in H}(\frac{1}{p}{)}^h\sum _{n}P\{T+k=n+h\}$

La somma per ogni $n$ della probabilità che il tempo di arresto $T$ sia uguale a $n+h-k$ equivale a calcolare la probabilità che $T$ sia finito, pari a $1$ per l'osservazione 1.

Pertanto si dimostra la tesi ottenendo che $𝐄[U]=\sum _{h\in H}(\frac{1}{p}{)}^h\sum _{n}P\{T+k=n+h\}=\sum _{h\in H}(\frac{1}{p}{)}^h$

Verifiche sperimentali

Si può dimostrare sperimentalmente il tempo medio di uscita di una stringa implementando un algoritmo che simula l'estrazione casuale dei caratteri e campionando il numero di estrazioni necessarie a comporre una determinata parola. L'algoritmo può essere implementato attraverso un simulatore, oppure utilizzando un linguaggio di programmazione fornito di una libreria che implementi un generatore di numeri pseudo casuale. Di seguito si descrive un semplice algoritmo di esempio, scritto con il linguaggio ANSI C, che permette di campionare i tempi di uscita di una stringa. Successivamente si descrive come avviene il campionamento dei dati e si fa vedere che i dati tendono alla previsione matematica.

Algoritmo di campionamento

Per effettuare un campionamento del tempo di uscita di una stringa è necessario implementare un algoritmo che effettui la stessa estrazione un certo numero di volte, solitamente maggiore di trenta. L'alfabeto di riferimento è quello inglese composto da ventisei lettere.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
#include <time.h>

#define MIN_CAR 97
#define MAX_CAR 122
#define DELTA_CAR 26

#define MARKER_STR "-s"
#define MARKER_GIRI "-n"
#define MARKER_SID "-r"
#define MARKER_SAVE "-f"
#define MARKER_VERBOSE "-v"
#define VERBOSE_OFF "off"

int verbose;

unsigned long long estrai_stringa(int l, char * s){
	
	unsigned long long n;
	int k, maxk;
	char c;
	
	n = 0;
	k = 0;
	maxk = 0;
	
	while (k < l){
		
		if (n == ULLONG_MAX){
			
			if (verbose == 1){
				printf("raggiunto limite massimo di estrazioni: %llu\n", n);
				printf("numero massimo di caratteri estratti: %d su %d\n", maxk, l);
				fflush(stdout);
			}
			
			return 0;
		}
		
		c = (char) (MIN_CAR + (rand() % DELTA_CAR));
		
		if (c == s[k]){
			k++;
			
			if (maxk < k){
				maxk = k;
			}
			
		}else{
			k = 0;
		}
		
		n++;
		
	}
	
	if (verbose == 1){
		printf("stringa estratta dopo %llu step\n", n);
		fflush(stdout);
	}
	
	return n;
	
}

int main(int argc, char * argv[]){
	
	int i, l = -1, n = -1;
	time_t t;
	unsigned int sid = 0;
	unsigned long long ret;
	char * s;
	FILE * f = NULL;
	
	verbose = 1;
	
	for (i = 0; i < argc; i++){
		
		if (strcmp(argv[i], MARKER_STR) == 0){
			s = argv[i + 1];
			l = strlen(s);
		}else if (strcmp(argv[i], MARKER_GIRI) == 0){
			n = atoi(argv[i + 1]);
		}else if (strcmp(argv[i], MARKER_SID) == 0){
			sid = atoi(argv[i + 1]);
		}else if (strcmp(argv[i], MARKER_VERBOSE) == 0){
			if (strcmp(argv[i + 1], VERBOSE_OFF) == 0){
				verbose = 0;
			}
		}else if (strcmp(argv[i], MARKER_SAVE) == 0){
			
			f = fopen(argv[i + 1], "a");
			
			if (f == NULL){
				
				printf("errore nella creazione del file\n");
				fflush(stdout);
				
				return -1;
				
			}
			
		}
		
	}
	
	if (l == -1){
		if (verbose == 1){
			printf("specificare la stringa da estrarre: -s [stringa]\n");
			fflush(stdout);
		}
		return -1;
	}
	
	if (n == -1){
		if (verbose == 1){
			printf("specificare il numero di iterazioni: -n [numero iterazioni]\n");
			fflush(stdout);
		}
		return -1;
	}
	
	if (sid == 0){
		if (verbose == 1){
			printf("nessun sid specificato (opzione -r [sid]), uso sid generato automaticamente\n");
			fflush(stdout);
		}
		sid = (unsigned int) time(&t);
	}
	
	if (verbose == 1){
		printf("**** start estrazione ****\n");
		printf("sid = %du\n", sid);
		printf("stringa = %s\n", s);
		printf("lunghezza = %d\n", l);
		printf("iterazioni = %d\n\n", n);
		fflush(stdout);
	}
	
	srand(sid);
	
	for (i = 0; i < n; i++){
		
		ret = estrai_stringa(l, s);
		
		if (ret == 0){
			printf("errore nell'estrazione della stringa\n");
			fflush(stdout);
			return -1;
		}
		
		if (f != NULL){
			fprintf(f, "%llu\n", ret);
		}
		
	}
	
	if (f != NULL){
		fclose(f);
	}
	
	return 0;
	
}

Per compilare il codice è necessario salvarlo in un file (es. gen.c) e creare l'eseguibile attraverso un compilatore C. Di seguito si riporta il comando per compilare il sorgente con il compilatore gcc per il sistema operativo linux.

gcc gen.c -o gen

Verifica ipotesi mediante test di Student

Il test di verifica ipotesi di Student permette di stabilire se la media campionaria $\overline{x}$ si discosti in modo significativo alla media matematica $𝐄[U]$. Per effettuare il test si formulano le ipotesi $H_0:\overline{x}=E[U]$ e $H_1:\overline{x}\ne E[U]$. Nel caso in cui viene verificata l'ipotesi $H_0$ si stabilisce che le due previsioni sono attinenti con una certa probabilità di errore. Nel caso in cui viene verificata l'ipotesi $H_1$ si stabilisce che le due previsioni non sono attinenti con una certa probabilità di errore. Per effettuare il test di verifica è necessario ottenere i seguenti dati:

• $n\in {\mathbb{N}}_{\mathbb{+}}$ è la numerosità del campione, ossia il numero di volte in cui si è registrato il tempo di uscita della parola "ciao"
• $(x_1,x_2,\dots ,x_n)\in {\mathbb{N}}^n$ è il campione da verificare, dove $\mathrm{\forall }i=1,\dots ,n,x_i$ rappresenta il numero di estrazioni occorse prima di comporre la parola "ciao"
• $\overline{x}=\frac{1}{n}\sum _{i=1}^n{x}_i$ è la media campionaria
• ${\overline{\sigma }}^2=\frac{1}{n-1}\sum _{i=1}^n(x_i-\overline{x}{)}^2$ è la varianza campionaria
• $𝐄[U]=\sum _{h\in H}{m}^h$ è la media matematica
• $Z=\frac{(\overline{x}-𝐄\mathbf{[}𝐔\mathbf{]})}{\sqrt{{\sigma }^2}}\sqrt{n}$ è la statistica che ha legge di Student con $(n-1)$ gradi di libertà
• $\alpha \in ℝ,\text{ t.c. }0<\alpha <1$ è l'errore tollerabile nella conferma dell'ipotesi
• $q_{(n-1,\alpha )}\in {ℝ}_{\mathbb{+}}$ è il quantile della legge di Student con $(n-1)$ gradi di libertà associato alla tolleranza $\alpha$

Il test si esegue comparando il valore della statistica con il relativo quantile. Nel caso in cui $Z<q_{(n-1,\alpha )}$ si verifica l'ipotesi $H_0$ con una probabilità pari a $1-\alpha$. Nel caso in cui, invece, $Z\ge q_{(n-1,\alpha )}$ si respinge l'ipotesi $H_0$ e si conferma l'ipotesi $H_1$ con una probabilità di errore pari ad $\alpha$.

Esempio

Si procede ad un esempio concreto per verificare mediante il test di Student le ipotesi $H_0$ e $H_1$.

Per prima cosa si procede al campionamento dei dati utilizzando l'algoritmo descritto nella sezione precedente con il comando

./gen -s ciao -n 100 -f campionamento -r 1492875030

dove:

• ciao è la stringa da estrarre
• 100 è la numerosità del campionamento
• campionamento è il nome del file dove verranno salvati i risultati delle estrazioni
• 1492875030 è il seme per inizializzare il generatore pseudo casuale

Non appena il programma termina l'esecuzione è possibile procedere con il test di Student per stabilire se il numero di estrazioni necessarie per ottenere la stringa "ciao" è attinente alla previsione matematica. Si calcolano i parametri necessari a fare il test:

• $n=100$ è la numerosità del campione
• $\overline{x}=493329,65$ è la media campionaria
• ${\overline{\sigma }}^2=253288754254,291$ è la varianza campionaria
• $𝐄\mathbf{[}𝐔\mathbf{]}=456976$ è la media matematica
• $Z=0,7224$ è la statistica con legge di Student
• si pone $\alpha =0,05$ come errore tollerabile nel caso di verifica di $H_1$
• il quantile associato è $q_{(n-1,\alpha )}=1,660$

Essendo $Z<q_{(n-1,\alpha )}$ si conferma l'ipotesi $H_0$ e pertanto la media campionaria conferma la media matematica. Analizzando il grafico sottostante con l'andamento delle previsioni parziali al variare della numerosità si vede chiaramente come $\overline{x}\underset{n\to \mathrm{\infty }}{\overset{}{\to }}𝐄\mathbf{[}𝐔\mathbf{]}$.