Z Skrypty dla studentów Ekonofizyki UPGOW

Wersja z 22:42, 4 sty 2010

Generacja liczb losowych

Generator liczb pseudolosowych to procedura, generująca deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.

Najprostrzym przykładem jest liniowy generator kongruencyjny (ang. Linear congruential generator, LCG), który jest wyznaczony przez relację rekurencyjną:

\(X_{n+1} = \left( a X_n + c \right)~~\bmod~~m\)

Jego implementacja w octave:

function y=myran(x); 
  a=1664525;
  b=1013904223;
  m=2^32;
  y=mod(a*x+b,m);
  return; 
end

przykład jego użycia do generacji pseudolosowych liczb z przedziału (0,1):

x(1)=123;
for i=2:10; 
	x(i)=myran(x(i-1));
	disp(x(i)/2^32);
end

Generator ten ma wiele mankamentów:

• okres niskich bitów jest o wiele niższy od okresu całego generatora.

x(1)=1234;
for bitn=1:10
	for i=2:30; 
		x(i)=myran(x(i-1)); 
   	printf("Bit %d: %d\n",	 bitn,bitget(x(i),bitn) ); 
	end
	a=input('cont?','s');
	if (a=='q') 
		break;
	end
end

• Jeżeli użyjemy LCG do generacji punktów w n-wymiarowej przestrzeni to punktey te będą leżały na \(m^{1/n}\) hiperpowierzchniach.

function y=myranbad(x); 
  a=65539;
  b=0;
  m=2^31;
  y=mod(a*x+b,m);
  return; 
end

x(1)=1234;
for i=2:3000; 
	x(i)=myranbad(x(i-1)); 
end
X=reshape(x,[3,length(x)/3]);
randmax=2^31*1.0
plot3(X(1,:)/randmax,X(2,:)/randmax,X(3,:)/randmax,'*')

A further problem of LCGs is that the lower-order bits of the generated sequence h

Liczby o zadanym rozkładzie

Rozkład Gaussa

Algorytm Boxa-Mullera