Equazioni alle ricorrenze e numeri casuali

Tempo addietro abbiamo parlato del paradosso di Achille e della Tartaruga e delle serie di Fibonacci. Per calcolare il valore generico della successione, in entrambe i casi, abbiamo usato una notazione molto particolare, ricorsiva:

Fib(0) = 0
Fib(1) = 1

Fib(N) = Fib(N-1) + Fib(N-2)

Equazioni di questo tipo sono dette alle ricorrenze ed hanno la caratteristica peculiare di essere definite in termini di sé stesse. In alcuni casi è possibile convertire le equazioni alle ricorrenze in funzioni analitiche vere e proprie, esplicitando quindi il termine n-esimo della successione.

Nel caso della serie di Fibonacci questo processo di conversione da equazione alle ricorrenze è esplicitabile, precisamente

ove Φ è il rapporto aureo:

Il processo di calcolo esplicito della funzione analitica che restituisce l’ennesimo valore di una equazione alle ricorrenze richiede operazioni di calcolo matriciale, su cui torneremo più in là. Nel caso generico, le equazioni alle ricorrenze non sono esplicitabili e devono necessariamente essere corredate da una condizione detta iniziale , che consente di arrestare il continuo richiamo della funzione stessa, in modo ricorsivo.

Ne vediamo una interessante applicazione nel Generatore Lineare Congruente:

GLC(0) = 1

GLC(n+1) = (aGLC(n) + b) MOD m

è una successione di numeri pseudocasuali che prende come parametri di ingresso i numeri a e b e restituisce un numero casuale minore di m. MOD è la funzione modulo, pari al resto della divisione intera tra a e b (ad esempio il resto della divisione tra 9 e 10 è 1). Scegliendo accuratamente a, b ed m si ottiene una serie di numeri pseudocasuale che varia tra 1 ed m. I valori di a e b sono detti semi del generatore e devono essere minori di m. Ecco un esempio di valori del GLC per a = 31, b = 77 e m = 99:

n    GLC(n)
 1    1
 2    9
 3    59
 4    25
 5    60
 6    56
 7    31
 8    48
 9    80
 10    82
 11    45
 12    86
 13    70
 14    69
 15    38
 16    67

la sequenza di GLC(n) è detta pseudocasuale perché si ripete con periodo variabile a seconda dei parametri iniziali.