Don't take life too seriously: it's just a temporary situation

Supponiamo di prendere a caso due numeri reali, compresi tra 0 e 1: come si può determinare quale sia il maggiore?

Se i due numeri sono scritti nella consueta notazione in base b, basta scorrere le cifre, fino a trovarne una diversa, che ci consente di determinare il maggiore; se disponiamo di algoritmi capaci di generare i due numeri una cifra alla volta, è utile sapere quante cifre in media siano necessarie.

La probabilità pn che non basti esaminare n cifre è uguale alla probabilità che queste siano uguali, cioè 1 / b^n, quindi Limite per n tendente a infinito di p(n)^(1 / n) = 1 / b e il valore medio atteso del numero di cifre da esaminare è b / (b – 1).

 

Supponiamo ora che i due numeri siano scritti (o generabili) sotto forma di frazione continua semplice: anche in questo caso per determinare il maggiore basta trovare il primo termine differente, ma quanti termini bisogna esaminare in media?

L’analisi in questo caso è molto complessa; H. Daudé, P. Flajolet e B. Vallée analizzarono la probabilità pn che non basti esaminare n termini e dimostrarono sul finire del XX secolo che:

  • Formula per p(1);

  • Formula per p(2);

  • Formula per p(3);

  • il valore medio atteso del numero di termini da esaminare è Valore medio atteso del numero di termini da esaminare;

  • Limite per n tendente a infinito di p(n)^(1 / n) è uguale a una costante, detta “costante di Vallée”, che vale circa 0.1994588183.

Il valore medio atteso del numero di termini da esaminare si può anche calcolare come Formula per il valore medio atteso del numero di termini da esaminare o come Formula per il valore medio atteso del numero di termini da esaminare.

Qui trovate le prime 101 cifre decimali del valore medio atteso del numero di termini da esaminare.

 

Se invece di frazioni continue semplici si utilizzano frazioni continue centrate, il valore medio atteso del numero di termini da esaminare è Valore medio atteso del numero di termini da esaminare; e Valore del limite per n tendente a infinito di p(n)^(1 / n).

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.