MKZR/Liczby losowe

Z Skrypty dla studentów Ekonofizyki UPGOW

(Różnice między wersjami)
(Generacja liczb losowych)
(Generacja liczb losowych)
 
(Nie pokazano 10 wersji pomiędzy niniejszymi.)
Linia 1: Linia 1:
==Generacja liczb losowych==
==Generacja liczb losowych==
-
<math>\int_0^1 \displaystyle\frac{1}{(1+x^a)}dx</math>
+
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.
 +
 
 +
Najprostszym przykładem jest liniowy generator kongruencyjny (ang. Linear congruential generator, LCG), który jest wyznaczony przez relację rekurencyjną:
 +
 
 +
: <math>X_{n+1} = \left( a X_n + c \right)~~\bmod~~m</math>
 +
 
 +
Jego implementacja w octave:
<source lang="matlab">
<source lang="matlab">
Linia 13: Linia 19:
</source>
</source>
 +
przykład jego użycia do generacji pseudolosowych liczb  z przedziału (0,1):
<source lang="matlab">
<source lang="matlab">
x(1)=123;
x(1)=123;
Linia 18: Linia 25:
x(i)=myran(x(i-1));
x(i)=myran(x(i-1));
disp(x(i)/2^32);
disp(x(i)/2^32);
 +
end
 +
</source>
 +
 +
 +
Generator ten ma wiele mankamentów:
 +
 +
* okres niskich bitów jest o wiele niższy od okresu całego generatora.
 +
 +
<source lang="matlab">
 +
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
end
</source>
</source>
 +
 +
* Jeżeli użyjemy LCG do generacji punktów w  n-wymiarowej przestrzeni to punkty te będą leżały na  <math>m^{1/n}</math> hiperpowierzchniach.
 +
 +
<source lang="matlab">
 +
function y=myranbad(x);
 +
  a=65539;
 +
  b=0;
 +
  m=2^31;
 +
  y=mod(a*x+b,m);
 +
  return;
 +
end
 +
</source>
 +
 +
<source lang="matlab">
 +
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,'*')
 +
</source>
 +
 +
 +
"Jedynym słusznym" generatorem używanym obecnie jest [http://pl.wikipedia.org/wiki/Mersenne_Twister Mersenne Twister]. Jest on szybki i zapewnia dobre własności statystyczne generowanego ciągu liczb. W systemie GNU Octave funkcja rand używa
 +
Mersenne Twister-a.
==Liczby o zadanym rozkładzie==
==Liczby o zadanym rozkładzie==

Aktualna wersja na dzień 20:54, 15 mar 2010

Spis treści

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.

Najprostszym 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 punkty 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,'*')


"Jedynym słusznym" generatorem używanym obecnie jest Mersenne Twister. Jest on szybki i zapewnia dobre własności statystyczne generowanego ciągu liczb. W systemie GNU Octave funkcja rand używa Mersenne Twister-a.

Liczby o zadanym rozkładzie

Rozkład Gaussa

Algorytm Boxa-Mullera