Random numbers,general distribution 3. Acceptance-Rejection Methods: The functional form of some distributions makes it difficult or time- consuming to generate random numbers using direct or inversion methods.Acceptance-rejection methods provide an alternative in these cases. Acceptance-rejection methods begin with uniform random numbers,but require an additional random number generator.If your goal is to generate a random number from a continuous distribution with PDF F,acceptance-rejection r methods first generate a random number from a continuous distribution with PDF G satisfying for F(x)s cG(x),some c and all x
3. Acceptance-Rejection Methods： The functional form of some distributions makes it difficult or timeconsuming to generate random numbers using direct or inversion methods. Acceptance-rejection methods provide an alternative in these cases. Acceptance-rejection methods begin with uniform random numbers, but require an additional random number generator. If your goal is to generate a random number from a continuous distribution with PDF F, acceptance-rejection methods first generate a random number from a continuous distribution with PDF G satisfying for F(x) ≤ cG(x), some c and all x
Random numbers,general distribution 3. Acceptance-Rejection Methods: A continuous acceptance-rejection RNG proceeds as follows: 1.Chooses a PDF G 2.Finds a constant c such that F(x)/G(s)s c for all x 3. Generates a uniform random number u 4. Generates a random number v from G 5. If cu s F(v)/G(v),accepts and returns v.Otherwise,rejects v 2.5 and goes to step 3. f(x) g(x 2 c*g() 1.5 0.5
3. Acceptance-Rejection Methods： A continuous acceptance-rejection RNG proceeds as follows: 1. Chooses a PDF G 2. Finds a constant c such that F(x)/G(s) ≤ c for all x 3. Generates a uniform random number u 4. Generates a random number v from G 5. If cu ≤ F(v)/G(v), accepts and returns v. Otherwise, rejects v and goes to step 3
Random numbers,general distribution 3. Acceptance-Rejection Methods: For efficiency,a "cheap"method is necessary for generating random numbers from G,and the scalar c should be small.The expected number of iterations to produce a single random number is c. It is hard to find G and c
3. Acceptance-Rejection Methods： For efficiency, a "cheap" method is necessary for generating random numbers from G, and the scalar c should be small. The expected number of iterations to produce a single random number is c. It is hard to find G and c
Random numbers,general distribution 3. Acceptance-Rejection Methods: The following function implements an acceptance-rejection method for generating random numbers from PDF F given F,G,the RNG grnd for G,and the constant c: function X accrejrnd(f,g,grnd,c,m,n) X zeros(m,n);Preallocate memory for i =1:m*n accept false; while accept =false u rand(); v grnd(); ifc*u<=fV)/g(N)） X(①=V; accept true; end end end end
3. Acceptance-Rejection Methods： The following function implements an acceptance-rejection method for generating random numbers from PDF F given F, G, the RNG grnd for G, and the constant c: function X = accrejrnd(f,g,grnd,c,m,n) X = zeros(m,n); % Preallocate memory for i = 1:m*n accept = false; while accept == false u = rand(); v = grnd(); if c*u <= f(v)/g(v) X(i) = v; accept = true; end end end end
Where to use random numbers? In the practice,we can generate uniform random numbers in [0,1]. But we need random numbers that obey the PDF of the physical process we want to simulate.These numbers are not uniform! Sampling techniques allow to recover such numbers from: Analytical distribution:theoretical models Tabulated distribution:experimental data
Where to use random numbers? • In the practice, we can generate uniform random numbers in [0, 1]. • But we need random numbers that obey the PDF of the physical process we want to simulate. These numbers are not uniform! • Sampling techniques allow to recover such numbers from: – Analytical distribution: theoretical models – Tabulated distribution: experimental data