Một số kiến thức cơ sở của phương pháp Monte Carlo | PDF

Đ



n

g

N

g

u

y

ê

n

P

h

ư

ơ

n

g

T

à

i

l

i



u

n



i

b



N

M

T

P

Hình 1: So sánh thi gian gii quyt bài toán ca 2 phương pháp Monte Carlo và tt đnh

2

Lc

h s hì

nh th

àn

h phư

ơn

g phá

p Mon

te Ca

rl

o

Tên gi ca phương pháp này đưc đt theo tên ca mt thành ph  Monaco, nơi ni ting vi

các sòng bc, có l là do phương pháp này da vào vic gieo các s ngu nhiên. Tuy nhiên vic

gieo s ngu nhiên đ gii các bài toán đã xut hin t rt lâu ri.

Vào khong th k 18, ngưi ta đã thc hin các thí nghim mà trong đó h ném mt cây kim

trong mt mt cách ngu nhiên lên trên mt mt phng có k các đưng thng song song và đã

suy ra giá tr ca

 π

 t vic đm s đim giao nhau gia các cây kim và các đưng thng

2

đưc bit đn vi tên gi

 bài toán cây kim Buffon 

 

(

Buffon’s needle problem 

), trong bài toán này ngưi ta th

ngu nhiên các cây kim có chiu dài

 l

 lên trên mt mt sàn có k các đưng thng song song cách nhau mt đon

t

 (vi

 l

≤

t

) và tính xem xác sut ca cây kim ct ngang đưng thng là bao nhiêu.

Gi

 

x

 là khong cách t tâm cây kim đn đưng thng gn nht và

 

θ

 là góc to bi cây kim và đưng thng,

ta có hàm mt đ xác sut (

probability density function 

) ca

 x

 và

 θ

 như sau

0

≤

x

≤

 

t

2

 

:

 

2

t

d

x

0

≤

theta

≤

 

π

2

 

:

 

2

π

d

θ

Hàm mt đ xác sut kp hp (

 joint

prob

ability

density

function 

)

4

tπ

d

x

d

θ

Điu kin đ cây kim ct ngang đưng thng

 

x

 ≤

l

2

sin

θ

, xác sut đ cây kim ct ngang đưng thng s thu

đưc bng cách ly tích phân hàm mt đ xác sut kt hp

 

 

π/

2

0

 

 

(

l/

2)sin

θ

0

4

tπ

d

x

d

θ

 =

 

2

l

tπ

Ga s ta gieo

 N 

 kim, trong đó có

 n

 kim ct các đưng thng

n

N 

 

=

 

2

l

tπ

π

 =

 

2

lN 

tn

3