Alla fine mi è venuta una domanda che ha mandato fuori strada il generatore di Wichman-Hill. Non è così naturale come si potrebbe desiderare, ma spero che sia abbastanza spettacolare.
Ecco il problema: studia la distribuzione di $$ X = -10U_1 - 22U_2 + 38U_3 - 3U_4 + U_5 + 4U_6 - 38 U_7 $$ con l'uniforme $ U_i $ iid su $ (0,1) $.
Disegneremo solo un istogramma.
x <- c (-10, -22, 38, -3, 1, 4, -38) RNGkind (kind = "Mersenne") U <- matrice (runif (7 * 1e6), nrow = 7) hist (colSums (x * U), break = seq (-70,50, by = 0.25), col = "black")
Ora prova con Wichman-Hill:
RNGkind (kind = "Wichman") U <- matrix (runif (7 * 1e6), nrow = 7) hist (colSums (x * U), breaks = seq (-70,50, by = 0.25), col = "black")
Sì, tutti i valori generati sono interi:
> head (colonne (x * U), 20) [1] 3-9-52-21-23-14-18 8-23 12 5 4-17-16-19-44 5 4-23 [20] -15
Se alcune persone mostrano interesse, posso spiegare brevemente come ho costruito questo esempio.
Ecco uno schizzo del costruzione dell'esempio. I generatori congruenziali lineari si basano su una sequenza in $ [1, \ dots m-1] $ definita da $ x_ {n + 1} = \ alpha x_n \ [m] $ (che significa modulo $ m $), con $ \ gcd (\ alpha, m) = 1 $. I numeri pseudo casuali $ u_n = {1 \ over m} x_n $ si comportano all'incirca come numeri casuali uniformi in $ (0,1) $.
Un problema noto di questi generatori è che puoi trovare molti coefficienti $ a_0, a_1, \ dots, a_k \ in \ mathbb {Z} $ tali che $$ a_0 + a_1 \ alpha + \ cdots + a_k \ alpha ^ k = 0 \ [m]. $$ Ciò risulta in $ a_0 x_n + \ cdots + a_k x_ {n + k} = 0 \ [m] $ per tutti $ n $, che a sua volta si traduce in $ a_0 u_n + \ cdots + a_k u_ {n + k} \ in \ mathbb {Z } $. Ciò significa che tutte le $ (k + 1) $ - tuple $ (u_n, \ dots, u_ {n + k}) $ cadono in piani ortogonali a $ (a_0, \ dots, a_k) '$.
Ovviamente con $ k = 1 $, $ a_0 = \ alpha $ e $ a_1 = -1 $, hai un esempio del genere. Ma poiché $ \ alpha $ è solitamente grande, questo non darà un bell'esempio come sopra. Il punto è trovare valori "piccoli" $ a_0, \ dots, a_k $.
Siano $$ L = \ {(a_0, \ dots, a_k) \: \ a_0 + a_1 \ alpha + \ cdots + a_k \ alpha ^ k = 0 \ [m] \}. $$ Questo è un $ \ mathbb {Z} $ - reticolo.
Usando un po 'di algebra modulare, si può controllare che $ f_0 = (m, 0, \ dots, 0)' $, $ f_1 = (\ alpha, -1,0, \ dots, 0) '$, $ f_2 = (0, \ alpha, -1,0, \ dots, 0)' $, $ \ dots $, $ f_k = (0, \ dots, 0, \ alpha, -1) '$ è una base di questo reticolo (questo è il risultato chiave qui ...).
Il problema è quindi trovare un vettore breve in $ L $. Ho usato algoritmo LLL per questo scopo. L'algoritmo 2.3 di Brian Ripley Stochastic Simulation indicato (dopo la mia risposta) da kjetil b halvorsen avrebbe potuto essere usato.
Per Wichman-Hill, il Teorema cinese dei resti permette di verificare facilmente che sia equivalente a un generatore del tipo sopra, con $ \ alpha = 16555425264690 $ e $ m = 30269 \ times30307 \ times30323 = 27817185604309 $.