Tiểu luận Mô phỏng ngẩu nhiên

PhÇn 1. Më ®Çu Trong ho¹t ®éng cuéc sèng, nghiªn cøu vµ häc tËp, chóng ta rÊt cÇn ®Õn sù ngÉu nhiªn cña c¸c ®¹i l­îng. Nh­ chóng ta ®· biÕt, cã nhiÒu øng dông ph¶i sö dông sè ngÉu nhiªn. Mét trong sè ®ã lµ trong thuËt to¸n mËt m·, víi môc ®Ých chÝnh lµ m· hãa mét th«ng ®iÖp ®Ó chØ cã ng­êi nhËn míi ®­îc dïng chóng. Muèn vËy chóng ta ph¶i lµm cho th«ng ®iÖp cã vÎ nh­ ngÉu nhiªn b»ng c¸ch dïng mét chuçi gi¶ ngÉu nhiªn ®Ó m· hãa vµ còng víi chuçi ®ã ng­êi nhËn cã thÓ gi¶i m· ®­îc. Mét lÜnh vùc kh¸c còng ®­îc sö dông réng r·i c¸c sè ngÉu nhiªn lµ m« pháng. Mét m« pháng ®Æc tr­ng bao gåm mét ch­¬ng tr×nh m« t¶ mét sè khÝa c¹nh cña thÕ giíi thùc. C¸c sè ngÉu nhiªn l¹i thÝch hîp lµm d÷ liÖu nhËp cho c¸c ch­¬ng tr×nh nh­ vËy. Ngay c¶ khi kh«ng cÇn c¸c sè ngÉu nhiªn, m« pháng vÉn cÇn c¸c sè tïy ý dïng lµm d÷ liÖu nhËp. NhiÒu øng dông khi ph©n tÝch mét sè l­îng lín d÷ liÖu, ®«i khi chØ cÇn xö lý trªn mét tËp con nhá cña nã, khi ®ã chØ cÇn lùa chän theo kiÓu thö ngÉu nhiªn. Cã nhiÒu ph­¬ng ph¸p ®Ó sinh sè ngÉu nhiªn. TiÓu luËn nµy sÏ ®­a ra hai ph­¬ng ph¸p cã b¶n ®ã lµ ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh vµ ®ång d­ céng. Kh«ng thÓ dïng m¸y vi tÝnh ®Ó sinh ®­îc chuçi sè ngÉu nhiªn thùc sù, chóng ta chØ hy väng t¹o ra c¸c chuçi cã nhiÒu thuéc tÝnh gièng nh­ chuçi sè ngÉu nhiªn. C¸c sè nµy ®­îc gäi lµ c¸c sè gi¶ ngÉu nhiªn. Cã nhiÒu ph­¬ng ph¸p ®Ó kiÓm tra xem mét chuçi gi¶ ngÉu nhiªn cã mét sè thuéc tÝnh cña chuçi ngÉu nhiªn hay kh«ng. TiÓu luËn sÏ tr×nh bµy mét ph­¬ng ph¸p kiÓm tra c¬ b¶n ®ã lµ ph­¬ng ph¸p khi b×nh ph­¬ng. Néi dung tiÓu luËn gåm ba phÇn: PhÇn 1: §­a ra mét sè kh¸i niÖm vÒ sè ngÉu nhiªn vµ sè gi¶ ngÉu nhiªn. PhÇn 2: Giíi thiÖu ra hai ph­¬ng ph¸p c¬ b¶n ®Ó t¹o sè ngÉu nhiªn: ®ã lµ ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh vµ ph­¬ng ph¸p ®ång d­ céng. PhÇn 3: Tr×nh bµy mét ph­¬ng ph¸p khi b×nh ph­¬ng nh»m kiÓm tra tÝnh ngÉu nhiªn cña chuçi ®­îc sinh ra. TiÓu luËn nh»m môc ®Ých lµ giíi thiÖu c¸c thuËt to¸n vµ nh÷ng kü thuËt ®Ó dïng m¸y vi tÝnh t¹o sè ngÉu nhiªn vµ kiÓm tra tÝnh ngÉu nhiªn cña sè ®­îc t¹o. §Ó cµi ®Æt cho nh÷ng thuËt to¸n trong tiÓu luËn nµy, chóng t«i sö dông ng«n ng÷ lËp tr×nh Pascal. PhÇn 2. Néi dung I/ Sè ngÉu nhiªn vµ sè gi¶ ngÉu nhiªn Th«ng th­êng ng­êi ta dïng thuËt ng÷ ngÉu nhiªn khi muèn nãi ®Õn mét sù tïy ý. Mét ng­êi yªu cÇu mét sè ngÉu nhiªn, nghÜa lµ kh«ng quan t©m ®Õn gi¸ trÞ cña sè ®ã. Tuy nhiªn, sè ngÉu nhiªn lµ mét kh¸i niÖm to¸n häc ®­îc ®Þnh nghÜa lµ mäi sè ®Òu cã kh¶ n¨ng xuÊt hiÖn t­¬ng ®­¬ng nhau. §Ó ®¸p øng ®­îc ®Þnh nghÜa sè ngÉu nhiªn trªn, chóng ta ph¶i giíi h¹n c¸c sè ®­îc dïng vµo mét ph¹m vi nhÊt ®Þnh. Kh«ng thÓ cã mét sè nguyªn ngÉu nhiªn mµ chØ cã mét sè nguyªn ngÉu nhiªn trong mét miÒn x¸c ®Þnh nµo ®ã. Trong hÇu hÕt c¸c tr­êng hîp ta kh«ng ph¶i chØ cÇn mét sè ngÉu nhiªn, mµ cÇn ®Õn d·y sè ngÉu nhiªn. Khi ®ã cÇn ph¶i chøng minh nhiÒu mÆt vÒ c¸c thuéc tÝnh cña d·y sè ngÉu nhiªn. VÝ dô trong mét chuçi dµi c¸c sè ngÉu nhiªn cña mét ph¹m vi nhá, chóng ta cã thÓ muèn biÕt sè lÇn xuÊt hiÖn cña c¸c gi¸ trÞ trong chuçi. Kh«ng cã c¸ch nµo ®Ó t¹o ra c¸c sè ngÉu nhiªn thùc sù tõ mét m¸y vi tÝnh. Bëi v× khi ta viÕt ch­¬ng tr×nh t¹o sè ngÉu nhiªn th× c¸c sè mµ ch­¬ng tr×nh t¹o ra ch¾c ch¾n cã thÓ suy luËn ®­îc. C¸ch tèt nhÊt mµ chóng ta hy väng lµ viÕt c¸c ch­¬ng tr×nh ®Ó t¹o ra c¸c chuçi sè cã ®­îc nhiÒu thuéc tÝnh gièng nh­ c¸c sè ngÉu nhiªn. C¸c sè nµy th­êng ®­îc gäi lµ c¸c sè gi¶ ngÉu nhiªn. Chóng kh«ng thËt sù ngÉu nhiªn nh­ng chóng cã thÓ h÷u dông nh­ sù xÊp xØ cña c¸c sè ngÉu nhiªn. TiÓu luËn nµy tr×nh bµy ph­¬ng ph¸p t¹o sè ngÉu nhiªn trªn m¸y vi tÝnh nªn ë mét møc ®é nµo ®ã, tõ nay ta thèng nhÊt sè gi¶ ngÉu nhiªn víi sè ngÉu nhiªn. Cã nhiÒu ph­¬ng ph¸p ®Ó sinh nh÷ng chuçi sè nh­ vËy. Ch¼ng h¹n ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh, ph­¬ng ph¸p ®ång d­ céng, ph­¬ng ph¸p ®ång d­ toµn ph­¬ng... C¸c ph­¬ng ph¸p nµy ph¶i ®¸p øng ®­îc c¸c yªu cÇu sau: -Nh÷ng sè ®­îc sinh ra ph¶i ph©n bè ®Òu vµ ®éc lËp vÒ mÆt thèng kª. Gi¸ trÞ cña mét sè trong mét chuçi ngÉu nhiªn kh«ng liªn quan ®Õn gi¸ trÞ cña sè kÕ tiÕp. Chuçi ph¶i kh«ng ®­îc lÆp l¹i ®èi víi bÊt kú ®é dµi nµo. -Tèc ®é sinh sè ngÉu nhiªn ph¶i nhanh. Bëi v× trong qu¸ tr×nh mét m« pháng thùc hiÖn th­êng yªu cÇu mét sè l­îng lín c¸c sè ngÉu nhiªn. NÕu c«ng cô sinh chËm th× chi phÝ thùc hiÖn m« pháng sÏ cao. -ThuËt to¸n ®Ó sinh sè ngÉu nhiªn sö dông cµng Ýt bé nhí cµng tèt. Bëi v× ch­¬ng tr×nh m« pháng th­êng yªu cÇu bé nhí lín nh­ng bé nhí th­êng bÞ giíi h¹n. Trong mét sè tr­êng hîp, mét sè thuéc tÝnh cña c¸c sè ngÉu nhiªn th× quan träng trong khi c¸c thuéc tÝnh cßn l¹i th× kh«ng cÇn thiÕt. Trong tr­êng hîp ®ã, cÇn t¹o ra c¸c sè gÇn ngÉu nhiªn, chóng ch¾c ch¾n cã c¸c thuéc tÝnh mong muèn nh­ng ch­a ch¾c cã c¸c thuéc tÝnh kh¸c. Trong mét sè øng dông, c¸c sè gÇn ngÉu nhiªn cã thÓ lµ thÝch hîp h¬n c¸c sè gi¶ ngÉu nhiªn. Cã nhiÒu ph­¬ng ph¸p ®Ó kiÓm tra xem mét chuçi gi¶ ngÉu nhiªn cã mét sè thuéc tÝnh cña chuçi ngÉu nhiªn hay kh«ng. Ch¼ng h¹n ph­¬ng ph¸p kiÓm tra sè ngÉu nhiªn theo luËt ph©n phèi ®Òu, ph©n phèi chuÈn, ph©n phèi mò.. Trong phÇn tiÕp theo ta sÏ xem xÐt cô thÓ hai ph­¬ng ph¸p sinh sè ngÉu nhiªn vµ mét ph­¬ng ph¸p kiÓm tra tÝnh ngÉu nhiªn cña chuçi ®­îc sinh. II/ C¸c ph­¬ng ph¸p t¹o sè ngÉu nhiªn NhiÒu c«ng tr×nh nghiªn cøu nh»m ®­a ra c¸c thuËt to¸n sinh chuçi sè gi¶ ngÉu nhiªn. ThuËt to¸n kh«ng chØ khã trong kü thuËt mµ cßn khã trong tèc ®é sinh sè ngÉu nhiªn, ®é dµi vßng lÆp, vµ tÝnh chÝnh x¸c cña ch­¬ng tr×nh. PhÇn nµy giíi thiÖu hai ph­¬ng ph¸p th«ng dông lµ ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh vµ ph­¬ng ph¸p ®ång d­ céng. 1/ Ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh. Ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh ®­îc D. Lehner ®Ò xuÊt vµo n¨m 1951. §©y lµ ph­¬ng ph¸p næi tiÕng vµ rÊt th­êng ®­îc sö dông ®Ó t¹o sè ngÉu nhiªn. Ph­¬ng ph¸p nµy ®­îc ®Æc tr­ng bëi c«ng thøc ®Ö quy sinh sè thø n+1 dùa trªn sè thø n nh­ sau: an+1=(b*an + c) mod m (n³0). Gi¸ trÞ khëi ®Çu lµ h»ng sè a0, h»ng sè b lµ mét sè nh©n, h»ng sè c lµ sè gia vµ m lµ sè chia (modulus). Sù lùa chän nh÷ng gi¸ trÞ cña nh÷ng h»ng sè nµy cã ¶nh h­ëng ®Õn ®é dµi chu kú cña chuçi sè ngÉu nhiªn ®­îc sinh ra. Ta thÊy, trong ph­¬ng ph¸p nµy nh÷ng sè kÕ tiÕp trong chuçi ®­îc sinh ra bëi mèi quan hÖ ®Ö quy. §Ó t¹o mét sè ngÉu nhiªn míi, ta dïng sè tr­íc ®ã nh©n víi b, céng thªm c, chia cho m vµ lÊy phÇn d­. Nh­ vËy sè nhËn ®­îc lu«n n»m trong ®o¹n tõ 0 ®Õn m-1 VÝ dô 1: Cho b=2, c=3, m=10 vµ a0=0 th× ta cã a0=0 a1=(2*0+3) mod 10=3 a2=(2*3+3) mod 10=9 a3=(2*9+3) mod 10=1 a4=(2*1+3) mod 10=5 a5=(2*5+3) mod 10=3 a6=(2*3+3) mod 10=9 a7=(2*9+3) mod 10=1 a8=(2*1+3) mod 10=5 VÝ dô 2: Cho b=2, c=0, m=10 vµ a0=1 th× ta cã a0=1 a1=(2*1) mod 10=2 a2=(2*2) mod 10=4 a3=(2*4) mod 10=8 a4=(2*8) mod 10=6 a5=(2*6) mod 10=2 a6=(2*2) mod 10=4 a7=(2*4) mod 10=8 a8=(2*8) mod 10=6 Trong vÝ dô 2 minh häa tr­êng hîp trong ®ã c=0. ThuËt to¸n nµy ®­îc gäi lµ ph­¬ng ph¸p ®ång d­ nh©n. NÕu c¹0 thuËt to¸n ®­îc gäi lµ ph­¬ng ph¸p ®ång d­ hçn hîp. C¶ hai vÝ dô minh häa kh¶ n¨ng lÆp l¹i cña bÊt kú cña chuçi ®­îc sinh bëi l­îc ®å nµy. ThuËt to¸n trªn rÊt thÝch hîp khi sö dông trong m¸y vi tÝnh ®Ó t¹o sè ngÉu nhiªn v× nã dÔ cµi ®Æt. D­íi ®©y lµ ®o¹n ch­¬ng tr×nh t¹o ra N sè ngÉu nhiªn cho m¶ng A. Program tao_mang_ngau_nhien; type mmc=array[1..1000] of word; Var a:mmc; c,m,i:word; Begin c:=3; m:=10 a[0]:=0; for i:=1 to 100 do a[i]:=(a[i-1]*b+c) mod m; end. §Ó cã ®­îc sè ngÉu nhiªn tèt, ph¶i cã c¸ch chän c¸c h»ng sè a0, b vµ m. NhiÒu tµi liÖu ®· cung cÊp mét sè h­íng dÉn trong viÖc chän c¸c h»ng sè nµy. Tr­íc hÕt m nªn lín, v× chu kú sÏ lu«n lu«n nhá h¬n m nªn khi m lín th× sù lÆp l¹i cña c¸c sè sÏ Ýt h¬n. m cã thÓ lµ gi¸ trÞ tèi ®a cña mét kiÓu nguyªn nh­ng còng kh«ng cÇn ph¶i hoµn toµn lín nh­ vËy nÕu kh«ng tiÖn. Th«ng th­êng, chän m lµ lòy thõa cña 10 hoÆc 2 lµ thuËn lîi trong viÖc tÝnh to¸n ®ång d­. Thø hai lµ chän b vµ c: Mét chuçi ®­îc sinh ra bëi s¬ ®å ®ång d­ tuyÕn tÝnh cã chu kú m nÕu vµ chØ nÕu: c lµ nguyªn tè cïng nhau víi m. b-1 lµ béi sè cña mäi sè nguyªn tè chia cho m. b-1 lµ béi cña 4 nÕu m lµ béi cña 4. Nh÷ng rµng buéc nµy dÉn ®Õn nh÷ng gi¸ trÞ sè nh©n cã d¹ng b=zp+1, trong ®ã z lµ c¬ sè ®­îc dïng trong biÓu diÔn sè cña m¸y tÝnh, k lµ sè l­îng bÝt tèi ®a cña kiÓu nguyªn, m=zk vµ z£p<k. Nh­ ®èi víi sù lùa chän cña c, b ph¶i tháa m·n yªu cÇu lµ nguyªn tè cïng nhau víi m. Theo tµi liÖu Algorithms, b nªn lµ mét h»ng sè tïy ý, kh«ng theo mét mÉu riªng nµo c¶, ngo¹i trõ nã nªn kÕt thóc bëi ....x21, víi x ch½n. b kh«ng nªn qu¸ lín hoÆc qu¸ nhá. Mét sù lùa chän an toµn lµ dïng mét sè Ýt h¬n m mét ch÷ sè. §iÒu nµy gióp tr¸nh ®­îc mét sè sù cè cã thÓ x¶y ra mµ c¸c ph©n tÝch to¸n häc cßn ®Ó hë. Thø ba lµ chän x0. NÕu chu kú cña chuçi lµ m, sù lùa chän x0 lµ kh«ng quan träng, v× toµn bé chuçi sÏ ®­îc sinh ra. Tuy nhiªn cÇn chó ý khi chän x0=0 vµ sö dông ph­¬ng ph¸p ®ång d­ nh©n sÏ dÉn ®Õn mét chuçi tho¸i hãa. C¸c quy luËt nªu trªn ®­îc ph¸t triÓn bëi D. E. Knuth. Knuth chøng minh r»ng c¸c sù lùa chän nµy lµm cho ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh t¹o ra c¸c sè ngÉu nhiªn tèt, tháa m·n ®­îc nhiÒu kiÓm tra thèng kª phøc t¹p. Mét t×nh huèng xÊu nhÊt lµ chuçi sè ®­îc sinh ra cã chu kú nhá so víi miÒn x¸c ®Þnh cña nã. VÝ dô nh­ víi b=19, m=381, a0=0 sÏ t¹o ra chuçi kh«ng ngÉu nhiªn 0, 1, 20, 0, 1, 20,... trong kho¶ng tõ 0 ®Õn 380. Kh«ng ph¶i dÔ ®Ó nhËn ra ®­îc c¸c t×nh huèng nh­ trªn. V× vËy tèt nhÊt nªn theo c¸c chØ dÉn cña Knuth ®­a ra ®Ó tr¸nh ®­îc nh÷ng tr­êng hîp “xÊu” mµ «ng ®· t×m ®­îc. Khi c¸c gi¸ trÞ khëi ®éng kh¸c nhau th× t¹o thµnh c¸c chuçi ngÉu nhiªn kh¸c nhau. Th­êng th× kh«ng cÇn ph¶i l­u tr÷ c¶ chuçi nh­ ch­¬ng tr×nh nªu trªn. Ng­îc l¹i, chóng ta chØ cÇn l­u l¹i trong mét biÕn toµn côc a, khëi ®éng víi mét gi¸ trÞ nµo ®ã, råi cËp nhËt b»ng phÐp tÝnh a:=(a*b+1) mod m. Trong Pascal, chóng ta cßn mét b­íc n÷a míi cã thÓ thùc hiÖn ®­îc, bëi v× chóng ta kh«ng ®­îc phÐp bá qua t×nh tr¹ng trµn sè. Trµn sè lµ mét tr­êng hîp lçi mµ cã thÓ t¹o ra c¸c kÕt qu¶ kh«ng dù ®o¸n ®­îc. Gi¶ sö m¸y tÝnh cã kiÓu nguyªn 32 bÝt vµ ta chän m=100000000, b=31415821, a=1234567. TÊt c¶ c¸c gi¸ trÞ nµy ®Òu nhá h¬n gi¸ trÞ tèi ®a cña kiÓu sè nguyªn, nh­ng phÐp to¸n nh©n ®· lµm cho nã trµn a*b+1. KÕt qu¶ ®­îc t¹o ra sÏ kh«ng cã quan hÖ víi tÝnh to¸n cña chóng ta. V× ta chØ quan t©m ®Õn 8 ký sè sau cïng nªn cã mét kü thuËt ®Ó lo¹i bá sù trµn lµ ph©n nhá phÐp nh©n ra lµm nhiÒu phÇn. §Ó nh©n p vµ q, ta viÕt p=104p1+p0 q=104q1+q0. Do ®ã phÐp nh©n ®­îc viÕt: p*q= (104p1+p0)*(104q1+q0)=104p1q1+104(p1q0+p0q1)+p0q0 Chóng ta chØ muèn 8 ký sè cho kÕt qu¶, v× thÕ cã thÓ bá qua sè h¹ng ®Çu tiªn (104p1q1) vµ bá qua bèn ký sè ®Çu tiªn cña sè h¹ng thø hai 104(p1q0+p0q1). Ta cã ch­¬ng tr×nh nh­ d­íi ®©y Procedure tao_chuoi_ngau_nhien; const m=100000000; m1=10000;b=3141581; var i,a,N:integer; Function nhan(p,q:integer):integer; var p1,p0,q1,q0:integer; Begin p1:=p div m1; p0:=p mod m1; q1:=q div m1; q0:=q mod m1; nhan:=(((p0q1+p1q0) mod m1)*m1+p0q0) mod m; End; Function randomint:integer; Begin a:=(nhan(a,b)+1) mod m; randomint:=a; End; BEGIN readln(N,a); for i:=1 to N do write(random); Readln; END. Hµm nhan() trong ch­¬ng tr×nh nµy tÝnh (p*q mod m) kh«ng bÞ trµn khi mµ m nhá h¬n 1/2 gi¸ trÞ sè nguyªn tèi ®a. Khi ch¹y ch­¬ng tr×nh víi d÷ liÖu nhËp N=10 vµ q=124567 ch­¬ng tr×nh sÏ t¹o ®­îc 10 sè nh­ sau: 35884508, 80001069, 63512650, 43635651, 1034472, 87181513, 6917174, 209855, 67115956, 59939877. Trong c¸c sè nµy, cã sù kh«ng ngÉu nhiªn: vÝ dô, c¸c ký sè hµng ®¬n vÞ xoay vßng qua c¸c ký sè tõ 0 ®Õn 9. DÔ dµng chøng minh ®­îc ®iÒu nµy lµ do tõ c«ng thøc. Nãi chung c¸c ký sè bªn ph¶i kh«ng thËt sù ngÉu nhiªn. §©y lµ h¹n chÕ c¬ b¶n cña ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh ®Ó t¹o sè ngÉu nhiªn. §Ó t¹o mét sè nguyªn ngÉu nhiªn trong giíi h¹n [0,r-1], ta cã thÓ thay hµm random() ë ch­¬ng tr×nh trªn bëi hµm d­íi ®©y: Function badrandom(r:integer):integer; begin a:=(nhan(b,a)+1) mod m badrandom:= a mod r end; Hµm nµy ®­îc ®¸nh gi¸ lµ kh«ng “tèt” v× c¸c ký sè kh«ng ngÉu nhiªn bªn ph¶i lµ c¸c ký sè ®­îc sö dông, nªn chuçi kÕt qu¶ chØ cã ®­îc Ýt thuéc tÝnh mong muèn. VÊn ®Ò nµy cã thÓ dÔ dµng kh¾c phôc b»ng c¸ch dïng c¸c ký sè bªn tr¸i thay thÕ. Hµm ®­îc viÕt l¹i lµ: Function newrandom(r:integer):integer; begin a:=(nhan(b,a)+1) mod m newrandom:= a*r div m end; Hµm trªn cho ta mét sè nguyªn ngÉu nhiªn gi÷a 0 vµ r-1. Tuy nhiªn t×nh huèng trµn vÉn cßn cã thÓ x¶y ra. Ta c¶i tiÕn l¹i hµm nµy nh­ sau: Function randomint(r:integer):integer; Begin a:=(nhan(a,b)+1) mod m; randomint:=((a div m1)*r) div m1; End; §Ó t¹o sè thùc ngÉu nhiªn gi÷a 0 vµ 1, ta xem c¸c sè t¹o nh­ trªn lµ ph©n thËp ph©n víi chÊm thËp ph©n ë bªn tr¸i. §iÒu nµy cã thÓ cµi ®­îc dÔ dµng b»ng c¸ch tr¶ vÒ gi¸ trÞ thùc a/m thay v× sè nguyªn a. Hµm t¹o sè thùc ngÉu nhiªn gi÷a 0 vµ 1 ®­îc viÕt. Function randomreal:real; Begin a:=(nhan(a,b)+1) mod m; randomreal:=a/m; End; Khi ®ã ng­êi sö dông cã thÓ nhËn ®­îc mét sè nguyªn trong giíi h¹n [0,r) b»ng c¸ch ®¬n gi¶n nh©n gi¸ trÞ nµy víi r vµ c¾t lÊy phÇn nguyªn cña kÕt qu¶. Hay cã thÓ nãi mét sè thùc ngÉu nhiªn gi÷a 0 vµ 1 míi chÝnh lµ sè cÇn thiÕt. 2/ Ph­¬ng ph¸p ®ång d­ céng. Mét ph­¬ng ph¸p kh¸c ®Ó t¹o c¸c sè ngÉu nhiªn lµ dùa trªn “c¸c thanh ghi dÞch chuyÓn håi tiÕp tuyÕn tÝnh” ®­îc sö dông trªn c¸c m¸y m· hãa tr­íc ®©y. ý t­ëng b¾t ®Çu víi mét thanh ghi chøa mét mÉu tïy ý, sau ®ã chuyÓn sang ph¶i mét b­íc, bá vµo c¸c vÞ trÝ trèng bªn tr¸i b»ng mét bÝt ®­îc x¸c ®Þnh b»ng c¸ch XOR cña hai bÝt ph¶i nhÊt cña thanh ghi ®ã. Mét thanh ghi dÞch chuyÓn håi tiÕp tuyÕn tÝnh 4 bÝt VÝ dô: NÕu thanh ghi ®­îc khëi t¹o lµ 1111 th× sau dÞch chuyÓn, néi dung lµ 0111 (1 XOR 1=0), tiÕp theo sÏ lµ 0011, 0001, 1000, 0100, 0010, 1001, 1100,0110, 1011, 0101, 1010, 1101, 1110, 1111. Khi chóng ta nhËn l¹i mÉu khëi t¹o, tiÕn tr×nh hiÓn nhiªn ®· lÆp l¹i. Chó ý r»ng tÊt c¶ c¸c mÉu bÝt cã thÓ cã ®Òu xuÊt hiÖn: gi¸ trÞ khëi ®Çu lÆp l¹i sau 15 b­íc. Tuy nhiªn, nÕu ta thay ®æi c¸c vÞ trÝ c¸c bÝt lÊy ra dïng ®Ó tÝnh gi¸ trÞ cho håi tiÕp bªn tr¸i th× sÏ ®­îc mét chuçi hoµn toµn kh¸c. VÝ dô, ta lÊy bÝt 0 vµ 2 thay v× 0 vµ 1 nh­ trªn (thø tù tÝnh tõ ph¶i sang tr¸i) th× chóng ta nhËn ®­îc chuçi 1111, 0111, 0011, 1001, 1100, 1110, 1111, kh«ng ph¶i chu kú ®Çy ®ñ nh­ tr­íc. Th«ng th­êng víi thanh ghi n bÝt, chóng ta cã thÓ s¾p xÕp ®Ó chiÒu dµi vßng lÆp lµ 2n-1. V× vËy, víi gi¸ trÞ n ®ñ lín, c¸c thanh ghi n bÝt t¹o ®­îc chuçi ngÉu nhiªn kh¸ tèt. Th«ng th­êng, chóng ta th­êng lÊy n=31 hay n=63. Còng nh­ ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh, c¸c ®Æc tÝnh to¸n häc cña c¸c thanh ghi nµy ®· ®­îc nghiªn cøu nh»m ®­a ra nhiÒu ph­¬ng ¸n lùa chän vÞ trÝ lÊy ra c¸c bÝt ®Ó tÝnh gi¸ trÞ bÝt bªn ph¶i ®Ó t¹o ®­îc tÊt c¶ c¸c mÉu. VÝ dô víi n=31, c¸c vÞ trÝ rót ra cã thÓ lµ 0 vµ mét trong c¸c vÞ trÝ: 4, 7, 8, 14, 19, 25, 26, hay 29. Mét c¸ch thùc hiÖn kh¸c lµ cã thÓ tÝnh to¸n mét lÇn mét mét sè nguyªn thay v× mçi lÇn mét bÝt víi ph­¬ng ph¸p ®Ö quy nh­ trªn. Trong vÝ dô trªn nÕu sö dông phÐp to¸n XOR bit cho hai sè kÕ tiÕp, chóng ta t¹o ®­îc mét sè sÏ xuÊt hiÖn t¹i ba vÞ trÝ sau ®ã trong danh s¸ch. §iÒu nµy gióp ta cã ®­îc mét ph­¬ng ph¸p t¹o sè ngÉu nhiªn cã thÓ dÔ dµng ¸p dông cho m¸y vi tÝnh. Dïng thanh ghi dÞch chuyÓn håi tiÕp víi hai bÝt lÊy ra tÝnh to¸n lµ bÝt thø b vµ thø c, còng gièng nh­ dïng c«ng thøc ®Ö quy sau: a[k]:=(a[k-b]+a[k-c]) mod m §Ó thÝch hîp víi ph­¬ng ph¸p thanh ghi dÞch chuyÓn, phÐp to¸n céng trong c«ng thøc nµy nªn ®­îc thay thÕ b»ng phÐp to¸n XOR trªn bÝt. Tuy nhiªn, ®iÒu nµy chøng tá r»ng cã thÓ t¹o ®­îc c¸c sè ngÉu nhiªn tèt ngay c¶ khi chØ dïng phÐp céng sè nguyªn th«ng th­êng mµ th«i. Ph­¬ng ph¸p nµy gäi lµ ®ång d­ céng (additive congruential) BÝt ph¶i nhÊt cña c¸c sè trong ph­¬ng ph¸p nµy còng gièng nh­ c¸c bÝt trong thanh ghi dÞch chuyÓn håi tiÕp t­¬ng øng. Do ®ã sè b­íc ®¹t ®­îc tr­íc khi b¾t ®Çu lÆp l¹i, Ýt nhÊt còng b»ng chiÒu dµi cña chu kú lÆp. Víi ph­¬ng ph¸p nµy c¸c sè ngÉu nhiªn ®­îc t¹o ra v­ît qua ®­îc c¸c kiÓm tra thèng kª. §Ó cµi ®Æt ch­¬ng tr×nh t¹o sè ngÉu nhiªn theo ph­¬ng ph¸p ®ång d­ céng, chóng ta cÇn gi÷ mét b¶ng gåm c phÇn tö, lu«n chøa c sè ®­îc t¹o ra gÇn nhÊt. ViÖc tÝnh to¸n ®­îc tiÕp tôc b»ng c¸ch thay thÕ mét trong c¸c sè trong b¶ng b»ng tæng cña hai sè kh¸c trong b¶ng. Khëi ®Çu, b¶ng nªn gåm c¸c sè kh«ng lín qu¸ vµ còng kh«ng nhá qu¸. Mét c¸ch ®¬n gi¶n lµ dïng ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh ®Ó sinh ra b¶ng nµy. Knuth khuyªn nªn chän b=31, c=55. Khi ®ã chóng ta cÇn ph¶i gi÷ l¹i 55 sè ®­îc t¹o gÇn nhÊt. CÊu tróc d÷ liÖu thÝch hîp lµ dïng hµng ®îi, nh­ng bëi v× kÝch th­íc cña b¶ng cè ®Þnh nªn chóng ta chØ dïng mét m¶ng kÝch th­íc ®ã, víi chØ sè xoay vßng nh­ sau: Procedure randominit(s:integer); begin a[0]:=s;j:=0; repeat j:=j+1; a[j]:=(nhan(b,a[j-1])+1) mod m; until j=54; end; Function randomint(r:integer):integer; begin j:=(j+1) mod 55; a[j]:=a[(j+23) mod 55] + a[(j+54) mod 55]) mod m; randomint:=((a[j] div m1)*r) div m1; end; BiÕn toµn côc a ®­îc thay b»ng mét m¶ng vµ mét con trá chØ sè j trªn m¶ng. Dung l­îng lín cña m¶ng a lµ mét khuyÕt ®iÓm cña ph­¬ng ph¸p nµy trong mét sè øng dông. Nh­ng nã còng chÝnh lµ mét ­u ®iÓm, bëi v× nã lµm cho chu kú lÆp rÊt dµi, Ýt nhÊt 255-1 ngay c¶ khi m nhá. Hµm randomint tr¶ vÒ mét sè nguyªn gi÷a 0 vµ r-1. Vµ dÜ nhiªn, chóng ta còng cã thÓ dÔ dµng thay ®æi nh­ phÇn tr­íc ®Ó tr¶ vÒ mét sè thùc ngÉu nhiªn gi÷a 0 vµ 1 b»ng c¸ch a[j]/m. Hµm randomint() ®­îc viÕt l¹i randomreal() nh­ sau: Function randomreal:real; begin j:=(j+1) mod 55; a[j]:=a[(j+23) mod 55] + a[(j+54) mod 55]) mod m; randomreal:=a[j]/m; end; VÝ dô: Cho m=10, vµ më réng chuçi 1, 2, 4, 8, 6 ®­îc sinh trong vÝ dô tr­íc. a1 = 1 a2 = 2 a3 = 4 a4 = 8 a5 = 6 a6 = (a5 + a1) mod 10 = (6+1) mod 10 =7 a7 = (a6 + a2) mod 10 = (7+2) mod 10 =9 a8 = (a7 + a3) mod 10 = (9+4) mod 10 =3 a9 = (a8 + a4) mod 10 = (3+8) mod 10 =1 a10 = (a9 +a5) mod 10 = (1+6) mod 10 =7 a11 = (a10 + a6) mod 10 = (7+7) mod 10 =4 a12 = (a11 + a7) mod 10 = (4+9) mod 10 =3 a13 = (a12 + a8) mod 10 = (3+3) mod 10 =6 a14 = (a13 + a9) mod 10 = (6+1) mod 10 =7 a15 = (a14 + a10) mod 10 = (7+7) mod 10 =4 a16 = (a15 + a11) mod 10 = (4+4) mod 10 =8 a17 = (a16 + a12) mod 10 = (8+3) mod 10 =1 a18 = (a17 + a13) mod 10 = (1+6) mod 10 =7 a19 = (a18 + a14) mod 10 = (7+7) mod 10 =4 a20 = (a19 + a15) mod 10 = (4+4) mod 10 =8 III/ KiÓm tra tÝnh ngÉu nhiªn b»ng ph­¬ng ph¸p “Khi b×nh ph­¬ng”. Th­êng cã thÓ dÔ dµng nhËn ra mét chuçi lµ kh«ng ngÉu nhiªn, nh­ng thËt khã chøng minh r»ng mét chuçi lµ ngÉu nhiªn. Nh­ ®· ®Ò cËp tr­íc ®©y, kh«ng cã mét chuçi nµo ®­îc t¹o b»ng m¸y vi tÝnh cã thÓ thùc sù ngÉu nhiªn, nh­ng chóng ta cã thÓ cã ®­îc mét chuçi thÓ hiÖn nhiÒu ®Æc tÝnh cña c¸c sè ngÉu nhiªn. Thùc tÕ, th­êng kh«ng thÓ x¸c ®Þnh chÝnh x¸c thuéc tÝnh nµo cña sè ngÉu nhiªn lµ quan träng ®èi víi mét tr×nh øng dông ®Æc biÖt. H¬n n÷a, lóc nµo còng nªn nghÜ ®Õn viÖc thùc hiÖn mét vµi kiÓu kiÓm tra trªn ph­¬ng ph¸p t¹o sè ngÉu nhiªn, ®Ó ®¶m b¶o r»ng kh«ng cã tr­êng hîp suy tho¸i x¶y ra. C¸c ph­¬ng ph¸p t¹o sè ngÉu nhiªn cã thÓ rÊt tèt nh­ng còng cã khi rÊt xÊu. NhiÒu kiÓm tra ®­îc triÓn khai ®Ó x¸c ®Þnh mét chuçi cã ®­îc nhiÒu thuéc tÝnh cña chuçi ngÉu nhiªn thùc sù hay kh«ng. HÇu hÕt c¸c kiÓm tra nµy ®Òu cã c¬ së trong to¸n häc. Trong sè ®ã kiÓm tra “khi-b×nh ph­¬ng” lµ mét kiÓm tra thèng kª c¬ b¶n, dÔ cµi ®Æt vµ h÷u dông trong nhiÒu øng dông. ý t­ëng cña ph­¬ng ph¸p khi b×nh ph­¬ng lµ xem xÐt c¸c sè t¹o ra cã ph©n bè mét c¸ch hîp lý hay kh«ng. NÕu chóng ta t¹o ra N sè d­¬ng cã gi¸ trÞ nhá h¬n r th× chóng ta mong muèn nhËn ®­îc kho¶ng N/r sè cho mçi gi¸ trÞ. Nh­ng sè lÇn xuÊt hiÖn cña tÊt c¶ c¸c gi¸ trÞ còng kh«ng ®­îc b»ng nhau, v× nÕu sè lÇn xuÊt hiÖn cña tÊt c¶ c¸c gi¸ trÞ b»ng nhau th× kh«ng cßn lµ ngÉu nhiªn n÷a. §iÒu nµy dÉn ®Õn viÖc cÇn tÝnh to¸n xem mét chuçi c¸c sè cã ®­îc ph©n bè gièng nh­ mét chuçi ngÉu nhiªn hay kh«ng b»ng c¸ch tÝnh tæng sè cña b×nh ph­¬ng sè lÇn xuÊt hiÖn cña mçi gi¸ trÞ, chia cho tÇn sè mong muèn (N/r), råi trõ bít chiÒu dµi chuçi (N). Ta cã ch­¬ng tr×nh kiÓm tra tÝnh ngÉu nhiªn cña chuçi ®­îc sinh ra nh­ sau: Function khi_binh_phuong(N,r,s:integer):real; var i,t:integer; f:array[0..rmax] of integer; begin raninit(s); for i:=0 to rmax do f[i]:=0; for i:=1 to n do begin t:=randomint(r); f[t]:=f[t]+1; end; t:=0; for i:=0 to r-1 do t:=t+f[i]*f[i]; Khi_binh_phuong:=((r*t/N)-N); end; Gi¸ trÞ cña hµm lµ gi¸ trÞ thèng kª khi b×nh ph­¬ng vµ còng cã thÓ biÓu diÔn kÕt qu¶ cña c«ng thøc to¸n häc sau: Víi 0<i<r. NÕu gi¸ trÞ thèng kª khi b×nh ph­¬ng “gÇn” víi r th× c¸c sè ®ã lµ ngÉu nhiªn, ng­îc l¹i, nÕu nã “xa” r th× chóng kh«ng ngÉu nhiªn. §èi víi ph­¬ng ph¸p kiÓm tra ®¬n gi¶n mµ chóng ta ®ang thùc hiÖn, gi¸ trÞ thèng kª chØ nªn lÖch mét kho¶ng 2 so víi r. §iÒu nµy chØ ®óng nÕu N lín h¬n 10r. §Ó ®¶m b¶o chuçi t¹o ra lµ ngÉu nhiªn, nªn thùc hiÖn kiÓm tra nhiÒu lÇn. Ph­¬ng ph¸p kiÓm tra nµy cµi ®Æt ®¬n gi¶n nªn thÝch hîp cho viÖc tÝch hîp nã vµo bªn trong mçi ch­¬ng tr×nh t¹o sè ngÉu nhiªn, nh»m ®¶m b¶o r»ng kh«ng cã ®iÒu g× ngoµi dù tÝnh cã thÓ g©y ra c¸c vÊn ®Ò nghiªm träng. TÊt c¶ c¸c thuËt to¸n “tèt” mµ chóng ta ®· th¶o luËn ®Òu v­ît qua ®­îc kiÓm tra nµy. Sö dông ph­¬ng ph¸p t¹o nªu trªn cho 1000 sè cã gi¸ trÞ nhá h¬n 100, chóng ta cã gi¸ trÞ thèng kª khi b×nh ph­¬ng lµ 100.8 ®èi víi ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh vµ 105.4 ®èi víi ph­¬ng ph¸p ®ång d­ céng. C¶ hai ph­¬ng ph¸p ®Òu ®¹t trong vïng lÖch 20 so víi 100 (tøc lµ trong [80,120]). PhÇn 3. KÕt luËn Nh­ chóng ta ®· biÕt, cã nhiÒu ph­¬ng ph¸p t¹o sè ngÉu nhiªn. TiÓu luËn ®· tr×nh bµy kü thuËt t¹o sè ngÉu nhiªn b»ng m¸y vi tÝnh víi hai ph­¬ng ph¸p th«ng dông lµ ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh vµ ph­¬ng ph¸p céng. Cã hai c¸ch ®Ó lËp tr×nh sinh ra chuçi ngÉu nhiªn. Ng­êi ta th­êng t¹o mét hµm, khëi ®éng nã, råi gäi lÆp l¹i nhiÒu lÇn, mçi lÇn tr¶ vÒ mét sè ngÉu nhiªn. Mét c¸ch kh¸c lµ chØ gäi mét lÇn, vµ nã t¹o ra d·y c¸c sè ngÉu nhiªn cho tr×nh øng dông. Trong c¶ hai tr­êng hîp trªn, ng­êi ta ®Òu mong muèn nhËn ®­îc c¸c chuçi gièng nhau trong c¸c lêi gäi kÕ tiÕp (®Ó t×m lçi hay so s¸nh c¸c ch­¬ng tr×nh kh¸c nhau trªn cïng d÷ liÖu nhËp) vµ t¹o ®­îc mét chuçi tïy ý. TÊt c¶ c¸c ®iÓm nªu trªn ®ßi hái ph¶i dïng ®Õn tr¹ng th¸i ®­îc gi÷ l¹i gi÷a c¸c lêi gäi cña hµm t¹o sè ngÉu nhiªn. §iÒu nµy cã thÓ kh«ng thuËn lîi trong mét sè m«i tr­êng lËp tr×nh. Ph­¬ng ph¸p céng bÊt lîi v× cã mét tr¹ng th¸i kh¸ lín (m¶ng gi÷ c¸c sè nguyªn võa t¹o) nh­ng l¹i cã mét thuËn lîi lµ cã mét chu kú dµi, mµ cã thÓ kh«ng cÇn ph¶i khëi t¹o. Cho dï c«ng cô t¹o sè ngÉu nhiªn tèt ®Õn bao nhiªu ®i n÷a vÉn cã thÓ sinh ra chuçi kh«ng ngÉu nhiªn hoÆc kh«ng cã nhiÒu thuéc tÝnh ngÉu nhiªn mong muèn. V× vËy, cÇn ph¶i xem xÐt cÈn thËn c¸c c«ng cô t¹o sè ngÉu nhiªn b»ng c¸ch thùc hiÖn nhiÒu lo¹i kiÓm tra thèng kª, nÕu kh«ng th× th× khã ®¶m b¶o mét ph­¬ng ph¸p t¹o sè ngÉu nhiªn lµ tèt. TiÓu luËn ®· tr×nh bµy ®­îc mét ph­¬ng ph¸p kiÓm tra tÝnh ngÉu nhiªn cña chuçi ®­îc sinh ra, ®ã lµ ph­¬ng ph¸p “khi b×nh ph­¬ng”. §©y lµ mét ph­¬ng ph¸p kiÓm tra kh¸ chÆt chÏ vµ dÔ cµi ®Æt. Ngoµi ra, ®Ó cã ®­îc c«ng cô t¹o sè ngÉu nhiªn tèt th× cÇn ph¶i dùa trªn c¸c ph©n tÝch to¸n häc vµ nhiÒu kinh nghiÖm thùc tÕ. Mét ph­¬ng ph¸p ®­îc ®Ò xuÊt nh»m tr¸nh c¸c sai lÖch x¶y ra trong thao t¸c t¹o sè ngÉu nhiªn lµ kÕt hîp c¸c ph­¬ng ph¸p víi nhau. Ch¼ng h¹n dïng ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh ®Ó t¹o m¶ng ban ®Çu cho ph­¬ng ph¸p ®ång d­ céng. Lêi kÕt: §Ó hoµn thµnh ®­îc ®Ò tµi nµy, ngoµi sù nç lùc vµ cè g¾ng cña b¶n th©n, t¸c gi¶ ®· nhËn ®­îc sù gióp ®ì qóy b¸u cña Quý ThÇy, PGS.TS. TrÇn Léc Hïng. Lµ mét häc viªn chuyªn ngµnh Tin häc vµ dï rÊt t©m ®¾c víi ®Ò tµi ®ang nghiªn cøu nh­ng víi thêi gian cã h¹n vµ khèi l­îng kiÕn thøc cña b¶n th©n cßn Ýt ái nªn ch¾c ch¾n tiÓu luËn kh«ng tr¸nh khái nh÷ng h¹n chÕ trong viÖc tiÕp cËn, nghiªn cøu vµ tr×nh bµy. T¸c gi¶ xin kÝnh träng c¶m ¬n sù gióp ®ì quý b¸u cña Quý ThÇy vµ mong ®­îc ®ãn nhËn tõ Quý ThÇy sù gãp ý ®Ó gióp t¸c gi¶ cã ®­îc hiÓu biÕt ®óng h¬n ®èi víi vÊn ®Ò ®ang nghiªn cøu ®ång thêi mong ®­îc sù l­îng thø cho nh÷ng s¬ suÊt trong tiÓu luËn nµy. tµi liÖu tham kh¶o [1] Ph¹m V¨n Kh¸nh Lý thuyÕt m« pháng ®¹i l­îng ngÉu nhiªn vµ qu¸ tr×nh ngÉu nhiªn [2] Robert Sedgewick Algorithms Addison-Wesley Publishing 2nd Edition [3] C¸c tµi liÖu vÒ sinh sè ngÉu nhiªn: Generation of random numbers Môc lôc Néi dung Trang Më ®Çu ......................................................................................................................... .......................... 1 Néi dung ......................................................................................................................... ...................... 2 1-Sè ngÉu nhiªn vµ sè gi¶ ngÉu nhiªn .......................................................................... 2 2-C¸c ph­¬ng ph¸p t¹o sè ngÉu nhiªn .......................................................................... 3 Ph­¬ng ph¸p ®ång d­ tuyÕn tÝnh .................................................................................. 3 Ph­¬ng ph¸p ®ång d­ céng ............................................................................................... 7 3-KiÓm tra tÝnh ngÉu nhiªn b»ng ph­¬ng ph¸p “khi b×nh ph­¬ng” ...... 10 KÕt luËn ......................................................................................................................... .......................... 13 Tµi liÖu tham kh¶o ........................................................................................................................... 14 Kû thuËt ®ång d­ céng as h¹t gièng cña nã, mét chuçi n sè x1,x2,...,xn. Chuæi sè nµy cã thÓ ®­îc sinh ra tõ mät sè kû thuËt kh¸c. øng dông cña thuËt to¸n nµy sÏ sinh ra mét sù më réng thµnh chuæi xn+1, xn+2... Líp cña thuËt to¸n nµy lµ xj=(xj-1+xj-n) mod m ThuËn lîi chÝnh cña kü thuËt nµy lµ tèc ®é; kh«ng cã sù nh©n lµ cÇn thiÕt. Nã cã thÓ dÉn ®Õn chu kú l¬n h¬n m. Nh­ Knuth ®· ®Ò cËp, thuyÕt hµnh vi cña kü thuËt nµy lµ kh«ng ®­îc hiÓu gièng nh­ hµnh vi cña kü thuËt ®ång d­ hçn hîp. Do ®ã, viÖc x¸c nhËn tÝnh hîp lÖ cña bÊt kú chuçi sè ®­îc sinh bëi kü thuËt nµy lµ cÇn thiÕt. DÔ thÊy r»ng viÖc lµm cho gÇn ®óng thuéc tÝnh “mçi sè cã kh¶ n¨ng xuÊt hiÖn nh­ nhau” trong mét chuçi dµi vÉn ch­a ®ñ. VÝ dô, mçi sè trong ®o¹n [1,100] xuÊt hiÖn mét lÇn trong chuçi (1,2,...,100), nh­ng chuçi nµy kh«ng ch¾c lµ h÷u dông nh­ mét chuçi gÇn t­¬ng ®­¬ng chuçi ngÉu nhiªn. Trong thùc tÕ, trong mét chuçi ngÉu nhiªn gåm 100 sè thuéc miÒn x¸c ®Þnh [1,100] sÏ cã mét vµi sè sÏ xuÊt hiÖn h¬n mét lÇn vµ mét vµi sè kh¸c th× kh«ng cã trong chuçi. NÕu kh«ng ®¹t ®­îc ®iÒu nµy trong mét chuçi gi¶ ngÉu nhiªn th× nghÜa lµ ®· cã sai sãt trong viÖc t¹o chuçi. NhiÒu ph­¬ng ph¸p kiÓm tra dùa trªn c¸c nhËn xÐt nh­ vËy ®· ®­îc ¸p dông cho c¸c ph­¬ng ph¸p t¹o chuçi ngÉu nhiªn nh»m kiÓm tra xem mét chuçi sè gi¶ ngÉu nhiªn cã mét sè thuéc tÝnh cña chuçi ngÉu nhiªn hay kh«ng. Chóng ta còng sÏ xem xÐt mét trong c¸c kiÓm tra quan träng nhÊt, ®ã lµ kiÓm tra ‘khi b×nh ph­¬ng” Chóng ta sÏ bµn kü vÒ c¸c sè ngÉu nhiªn ph©n phèi ®Òu, víi c¸c gi¸ trÞ xem nh­ t­¬ng ®­¬ng nhau. Còng t­¬ng tù cho c¸c sè ngÉu nhiªn tu©n theo c¸c ph©n phèi kh«ng ®ång ®Òu, víi mét sè gi¸ trÞ cã nhiÒu h¬n mét sè kh¸c. C¸c sè gi¶ ngÉu nhiªn víi ph­¬ng ph¸p ph©n phèi kh«ng ®ång ®Òu th­êng bao gåm bëi thùc hiÖn vµi ph©n phèi kiÓu ®ång ®Òu t¹o thµnh. Nh­ chóng ta sÏ thÊy, khã mµ thuyÕt phôc r»ng c¸c sè ngÉu nhiªn chóng ta t¹o cã tÊt c¶ c¸c thuéc tÝnh cña sè ngÉu nhiªn. §©y còng lµ mét vÊn ®Ò quan träng ®èi víi c¸c ph­¬ng ph¸p ph©n phèi kh¸c. Trong nhiÒu m« pháng nh÷ng sù kiÖn x¶y ra ®Ó xuÊt hiÖn ë ngÉu nhiªn hoÆc bao hµm thuéc tÝnh mµ gi¸ trÞ ph¶i ®­îc Ên ®Þnh mét Ýt ngÉu nhiªn. X¶y ra nµy bëi v× hÇu hÕt m« pháng lµ dùa trªn kiÕn thøc ®­îc m« t¶ nh­ mèi quan hÖ chung chung hoÆc cã liªn quan ®Õn lÞch sö. VÝ dô, trong nhiÒu tr­êng hîp kho¶ng thêi gian cña mét sù kiÖn ®­îc kiÕt ®Ó r¬i víi mét ph¹m vi n¸o ®ã. M« pháng cña mét sù kiÖn yªu cÇu mét gi¸ trÞ ®Æc biÖt ®­îc Ên ®Þnh. Gi¶ sö m« pháng cña mét hÖ thèng m¸y tÝnh general-purpose. Mét sù kiÖn mµ ph¶i ®­îc m« h×nh lµ phôc håi cña mét b¶n ghi tõ mét thiÕt bÞ l­u tr÷ truy xuÊt trùc tiÕp. Kho¶ng thêi gian cña sù kiÖn nµy cã thÓ ®­îc x¸c ®Þnh dÓ r¬i víi mét kho¶ng thêi gian nµo ®ã; gi¸ trÞ thùc sù, tuy nhiªn, bÞ ¶nh h­ëng bëi nh÷ng biÕn t×nh cê, ch¼ng h¹n vÞ trÝ cña b¶n ghi liªn quan víi ®Çu ®äc khi yªu cÇu ®­îc thùc hiÖn. Mét vÝ dô kh¸c trong ®ã sù xuÊt hiÖn t×nh cê to play a part lµ trong lan réng sö dông cña sù quyÕt ®Þnh logic trong m« pháng. VÝ dô, môc ®Ých r»ng trong ho¹t ®éng hÖ thèng, mét ®­êng dÉn ®­îc cho ®­îc biÕt ®Ó ®­a ra tû lÖ nµo ®ã cña thêi gian. M« pháng cña mét hÖ thèng yªu cÇu mét ph­¬ng thøc ®Ó chän ®­êng dÉn nµy trªn nh÷ng c¸i kh¸c v× vËy hµnh vi cña m« pháng t­¬ng tù nh­ cña nh÷ng hÖ thèng thùc tÕ. V× hÇu hÕt tr­êng hîp sù quyÕt ®Þnh nµy lµ bÊt kh¶ quyÕt, sù lùa chän th«ng th­êng dùa trªn mèi quan hÖ x¸c suÊt. §èi víi nh÷ng lý do nµy vµ kh¸c, mét ®ßi hái cña hÇu hÕt bÊt kú m« h×nh m« pháng lµ mét sè ph­¬ng tiÖn thuËn lîi ®Ó sinh sè ngÉu nhiªn. Nã ph¶i cã kh¶ n¨ng ®Ó Ên ®Þnh mét gi¸ trÞ cô thÓ ®Ó cã vÎ nh­ nh÷ng sù kiÖn ngÉu nhiªn trªn nh÷ng hÖ thèng m« pháng ®· cho. Trong vÝ dô tr­íc cña m« pháng cña hÖ thèng m¸y tÝnh, nã ph¶i ®­îc Ên ®Þnh mét gi¸ trÞ cô thÓ cho thêi gian yªu cÇu ®Ó t×m l¹i ®­îc mét b¶n ghi tõ mét thiÕt bÞ l­u tr÷ truy xuÊt trùc tiÕp mçi khi mét yªu cÇu t¸i t¹o ®­îc nhËn. Trong tr­êng hîp cña mét khèi quyÕt ®Þnh nã ph¶i lµ tr­îc tiÕp ... Sè ngÉu nhiªn lµ sù say mª vµ then chèt cña m« pháng. Tiªu biÓu, tÊt c¶ tÝnh chÊt ngÉu nhiªn ®­îc yªu cÇu bëi m« h×nh ®­îc m« pháng bëi bé sè ngÉu nhiªn c¸i mµ d÷ liÖu ra cña nã ®­îc gi¶ sö lµ mét chuçi cña sù ®éc lËp vµ ph©n phèi t­¬ng tù nhau U(0,1) nh­ng gi¸ trÞ ngÉu nhiªn (nghÜa lµ nh÷ng gi¸ trÞ ngÉu nhiªn liªn tôc ph©n bè ®ång ®Òu trªn kho¶ng (0,1)). Nh÷ng gi¸ trÞ ngÉu nhiªn nµy ®­îc biÕn ®æi khi cÇn thiÕt ®Ó m« pháng nh÷ng gi¸ trÞ kh¸c nhau tõ nh÷ng ph©n bè x¸c suÊt kh¸c nhau, ch¼ng h¹n lòy thõa, Poisson, nhÞ thøc, h×nh häc, rêi r¹c ®Òu,...còng nh­ Sinh biÕn ngÉu nhiªn. 1/ Giíi thiÖu: Trong ch­¬ng 4 sinh sè ngÉu nhiªn ®­îc th¶o luËn. Trong ch­¬ng nµy, v× sè ngÉu nhiªn lu«n lu«n cã nghÜa biÕn ngÉu nhiªn ®ång ®Òu, biÓu thÞ bëi RN(0,1), c¸i mµ hµm ph©n phèi cña nã lµ FU(u)= (1) Do ®ã nh÷ng sè ngÉu nhiªn lµ lu«n lu«n ph©n phèi ®Òu trªn kho¶ng ®¬n vÞ (0,1). Sù sinh sè ngÉu nhiªn lµ mét chñ ®Ò quan träng trong its own right. Ng­îc l¹i, sinh biÕn ngÉu nhiªn lu«n lu«n liªn quan víi sù sinh ra nh÷ng biÕn mµ x¸c suÊt ph©n phèi cña nã lµ kh¸c nhau mµ cña ®ång ®Òu trªn kho¶ng (0,1). VÊn ®Ò c¬ b¶n lµ v× thÕ ®Ó sinh mét biÕn ngÉu nhiªn, X, mµ hµm ph©n phèi cña nã lµ: F(x)=Pr(X£x) (-¥<x<+¥) (2) ®­îc gi¶ sö lµ hoµn toµn ®­îc biÕt, vµ kh¸c víi (1) HÇu hÕt c¸c hÖ thèng m¸y tÝnh lín chøa nh÷ng th­ viÖn víi sù thùc hiÖn cña nh÷ng bé sinh ®èi víi nh÷ng ph©n phèi tÇm th­êng h¬n. Bé sinh còng biÕn thiªn trong nhiÒu package thèng kª vµ m« pháng hiÖn t¹i cho m¸y tÝnh c¸ nh©n. Sù lùa chän mét bé sinh th­êng cã nhiÒu ®Ó lµm víi nh÷ng thuéc tÝnh cña sù ph©n phèi ®Ó ®­îc sö dông, nh­ víi nh÷ng thuéc tÝnh cña b¶n th©n bé sinh. Trong sù m« t¶ cña nh÷ng bé sinh ®· cho cô thÓ d­íi ®©y, nhÊn m¹nh v× vËy ®­îc cho ®Ó sù n»m d­íi ®Æc ®iÓm cña ph©n phèi ®­îc xem xÐt vµ trong mçi quan hÖ gi÷a ph©n phèi kh¸c nhau. Th«ng tin nµy sÏ lµ h÷u Ých trong sù gióp ®ì sù hiÓu cña nh÷ng thuéctÝnh cña bé sinh. Môc ®Ých lµ ®Ó cho phÐp mét sù lùa chän ®­îc thùc hiÖn, vµ thuËt to¸n sÏ lµ kh«ng cÇn thiÕ ®Ó xem xÐt nhiÒu nh­ lµ sù thùc hiÖn mét hép ®en. Thªm vµo ®ã, nguyªn lý chung vµ ph­¬ng thøc chung cña sinh biÕn ngÉu nhiªn ®­îc mo t¶ c¸i mµ cã thÓ sÏ reader ®Ó x©y dùng bé sinh cho ph©n phèi kh«ng chuÈn. Bé sinh biÕn ngÉu nhiªn lóc nµo còng vËy sö dông nh­ ®iÓm b¾t ®Çu cña chóng mét bé sinh sè ngÉu nhiªn c¸i mµ lµm ra RN(0,1) víi ph©n phèi ®· cho bëi (1). Kû thuËt lµ ®Ó biÕn ®æi hoÆc thùc hiÖn mét hoÆc nhiÒu biÕn ngÉu nhiªn ®ång ®Òu trong mét sè c¸ch hiÖu qu¶ ®Ó thu ®­îc mét biÕn víi ph©n phèi mong muèn (2). Trong ch­¬ng nµy nã sÏ ®­îc gi¶ sö r»ng nguån gèc cña sè ngÉu nhiªn lµ cã s½n. Thªm vµo ®ã, ®Ó lµ ®ång ®Òu, c¸c sè ngÉu nhiªn còng ph¶i lµ ®éc lËp lÉn nhau. Mét vÊn ®Ò ®Çy ý nghÜa ®­îc th¶o luËn trong ch­¬ng 4 lµ x©y dùnh bé sinh mµ s¶n sinh ra sè ngÉu nhiªn mµ cã thÓ an toµn ®­îc xem xÐt nh­ lµ ®éc lËp. Nã ®­îc gi¶ sö trong tiÕp theo mµ mét bé sinh nh­ vËy ®· cã s½n. Trong nh÷ng c¸i d­íi ®©y, nã ®­îc gi¶ sö r»ng mét chuçi sè ®­îc sinh ra bëi mét bé sinh {U1, U2,} ch¹y nhËp nh»ng tõ mét chuçi cña biÕn ph©n phèi ®éc lËp RN(0,1) 1/TÝnh chÝnh x¸c: §iÒ nµy liªn quan víi ph©n phèi cña nh÷ng biÕn ®­îc sinh ra bëi bé sinh. Bé sinh ®­îc gäi lµ chÝnh x¸c nÕu ph©n phèi cña nh÷ng biÕn ®­îc sinh cã d¹ng chÝnh x¸c mong muèn. Trong nh÷ng øng dông nµo ®ã trong ®ã ph©n phèi chÝnh x¸c lµ kh«ng critical, mét ph­¬ng thøc cã thÓ ®­îc chÊp nhËn c¸i mµ cã thÓ lµ tèt nh­ nh÷ng nh©n tè kh¸c ®­îc liªn quan, nh­ng ...... Nguyªn t¾c sinh Nh­ ®· ®Ò cËp trong 5.1, tõ b©y giê trªn nã ®­îc gi¶ sö r»ng mét bé sinh sè sè gi¶ ngÉu nhiªn lµ cã s½n mµ sinh ra mét chuçi cña nh÷ng biÕn ®éc lËp, víi sù hiÓu r»ng mçi lÇn hµm nµy ®­îc gäi, mét biÕn RN(0,1) ®­îc tr¶ vÒ mµ ®éc lËp víi tÊt c¶ c¸c biÕn ®­îc sinh bëi lÇn gäi tr­íc cña hµm nµy. Khi X lµ mét biÕn ngÉu nhiªn ph©n phèi liªn tôc, ph©n phèi cã thÓ ®­îc ®Þnh nghÜa b»ng hµm mËt ®é f(x). Hµm mËt ®é cho phÐp x¸c suÊt mµ X n»m gi÷a hai gi¸ trÞ ®· cho a vµ b (a<b) ®­îc ­íc l­îng lµ: Pr(a£X£b)= Tõ sù ®Þnh nghÜa cña nã, (2), nã sÏ ®­îc xem r»ng hµm ph©n bè trong tr­êng hîp nµy cã thÓ ®­îc ­íc l­îng tõ hµm mËt ®é lµ tÝch ph©n F(x)= Hµm ph©n phèi lµ v× vËy t¨ng nghiªm ngÆt vµ liªn tôc (hinhg 5.1). Trong tr­êng hîp nµy, ®èi víi bÊt kú 0<u<1, ph­¬ng tr×nh F(x)=u cã thÓ ®­îc gi¶i quyÕt ®Ó ®­a ra mét x duy nhÊt. NÕu (vµ ®©y lµ ®iÒu kiÖn tíi h¹n) nghÞch ®¶o cña hµm ph©n phèi cã thÓ ®­îc biÓu diÔn trong mét d¹ng ®¬n gi¶n, ph­¬ng ph¸p nµy cã thÓ ®­îc chøng tá (bao hµm) b»ng c¸ch viÕt ph­¬ng tr×nh trong mét d¹ng t­¬ng ®­¬ng x=F-1(u); v× vËy x ®­îc biÓu diÔn hµm hiÖn cña u. Hµm F-1 nµy d­îc gäi lµ nghÞch ®¶o cña F. This yields ph­¬ng ph¸p thuËn lîi tiÕp theo ®èi víi sinh biÕn víi hµm ph©n phèi ®· cho F... Ph­¬ng ph¸p biÕn ®æi nghÞch ®¶o (tr­êng hîp liªn tôc) Cho U=RN(0,1) Tr¶ vÒ X=F-1(U) §Ó chØ ra r»ng nã lµm viÖc, tÊt c¶ nh÷ng c¸i ®ßi hái ®ã lµ ®Ó x¸c minh r»ng hµm ph©n phèi cña X qu¶ thùc lµ F (nghÜa lµ Pr(X£x)=F(x)). B©y giê Pr(X£x)=Pr[F-1(U) £x)]=Pr[U£F(x)] Nh­ng x¸c suÊt bªn ph¶i lµ hµm ph©n phèi cña mét biÕn ngÉu nhiªn ®ång ®Òu ­íc l­îng t¹i gi¸ trÞ F(x), vµ tõ (1) ®©y lµ b»ng víi F(x), nh­ ®· quy ®Þnh. VÝ dô ®­îc biÕt nhiÒu nhÊt vµ h÷u dông nhÊt lµ khi X lµ mét biÕn ngÉu nhiªn ph©n phèi lòy th÷a víi a>0. hµm ph©n phèi cña nã lµ F(x)= (3) Gi¶i u=F(x) ®èi víi x trong tr­êng hîp nµy nghiÖm (yields) lµ x=F-1(u)=-a ln (1-u) (4) Mät biÕn ngÉu nhiªn v¬i hµm ph©n phèi (3) v× thÕ thu ®­îc bëi sö dông c«ng thøc (4) ®Ó tÝnh X, víi u ®­îc sinh ra nh­ mét biÕn U(0,1) Ph­¬ng ph¸p biÕn ®æi nghÞch ®¶o (tr­êng hîp rêi r¹c) Cho U=RN(0,1) Cho i=1 While F(xi)<U do i:=i+1; Return X:=xi Bëi v× ph­¬ng thøc sö dông mét t×m kiÕm tuyÕn tÝnh, nã cã thÓ kh«ng hiÖu qu¶ nÕu n lµ lín. Ph­¬ng ph¸p hiÖu qu¶ h¬n ®­îc m« t¶ nh­ sau: NÕu mét b¶ng c¸c gi¸ trÞ xi víi sù t­¬ng ÷ng nh÷ng gi¸ trÞ F(xi) ®­îc l­u, ph­¬ng ph¸p còng ®­îc gäi lµ table-lookup method. Ph­¬ng ph¸p thùc hiÖn th«ng qua b¶ng so s¸nh U víi mçi F(xi), vµ tr¶ vÒ, nh­ X, xi ®Çu tiªn ®­îc b¾t gÆp for which F(xi)³U.