Sobol sequence
'સોબોલ' સિક્વન્સ (જેને એલ. પી. ટી. ઓ. સિક્વન્સ અથવા બેઝ 2 માં (ટી, એસ) સિક્વન્સ પણ કહેવાય છે) અર્ધ-યાદૃચ્છિક ઓછી-વિસંગતતા સિક્વન્સનું ઉદાહરણ છે. તેઓ સૌપ્રથમ 1967 માં રશિયન ગણિતશાસ્ત્રી ઇલ્યા એમ. સોબોલ દ્વારા રજૂ કરવામાં આવ્યા હતા. આ સિક્વન્સ એકમ અંતરાલના ક્રમિક રીતે વધુ સારા સમાન પાર્ટીશનો બનાવવા માટે બે આધારનો ઉપયોગ કરે છે અને પછી દરેક પરિમાણમાં કોઓર્ડિનેટ્સને ફરીથી ગોઠવે છે. S-પરિમાણીય એકમ હાયપરક્યુબમાં સારું વિતરણ ચાલો Is = [0,1] s એ S-પરિમાણીય એકમ હાયપરક્યુબ છે, અને f એ IS પર વાસ્તવિક સંકલનક્ષમ કાર્ય છે. 'સોબોલ' ની મૂળ પ્રેરણા 'ઇસ' માં xn ક્રમ બનાવવાની હતી જેથી કન્વર્જન્સ શક્ય તેટલી ઝડપથી થાય. તે વધુ કે ઓછું સ્પષ્ટ છે કે સંકલન તરફ સરવાળો કરવા માટે, xn બિંદુઓએ છિદ્રોને ઘટાડવું જોઈએ. બીજો સારો ગુણધર્મ એ હશે કે ઇસના નીચલા-પરિમાણીય ચહેરા પર xn ના અંદાજો પણ ખૂબ ઓછા છિદ્રો છોડે છે. તેથી Is નું સજાતીય ભરણ યોગ્ય નથી કારણ કે નીચલા પરિમાણોમાં ઘણા બિંદુઓ એક જ સ્થાને હશે, તેથી અભિન્ન અંદાજ માટે નકામું છે. આ સારા વિતરણોને આધાર b માં (t, m, s)-જાળી અને (t, s)-અનુક્રમ કહેવામાં આવે છે. તેમને રજૂ કરવા માટે, પહેલા બેઝ b માં પ્રાથમિક s-અંતરાલને વ્યાખ્યાયિત કરો જ્યાં aj અને dj બિન-નકારાત્મક પૂર્ણાંકો છે, અને {1,., s} માં તમામ j માટે. 2 પૂર્ણાંકો આપવામાં આવે તો, આધાર b માં a (t, m, s)-નેટ એ bm બિંદુઓનો xn એવો ક્રમ છે કે હાયપરવોલ્યુમ λ (P) = bt − m ના આધાર b માં તમામ પ્રાથમિક અંતરાલ P માટે. બિન-નકારાત્મક પૂર્ણાંક t ને જોતાં, આધાર b માં a (t, s)-ક્રમ એ બિંદુઓ xn નો અનંત ક્રમ છે જેમ કે તમામ પૂર્ણાંકો માટે, આધાર b માં ક્રમ a (t, m, s)-નેટ છે. તેમના લેખમાં, સોબોલ 'એ Πτ-મેશેસ અને LPτ સિક્વન્સ વર્ણવ્યા છે, જે અનુક્રમે બેઝ 2 માં (t, m, s)-નેટ અને (t, s)-સિક્વન્સ છે. બેઝ બી (જેને નિડેરરીટર સિક્વન્સ પણ કહેવાય છે) માં શબ્દો (ટી, એમ, એસ)-નેટ્સ અને (ટી, એસ)-સિક્વન્સ 1988માં હેરાલ્ડ નિડેરરીટર દ્વારા રચવામાં આવ્યા હતા. હેલ્ટન, ફોરે અને અન્ય ઓછી વિસંગતતા ધરાવતા ક્રમની સરખામણીમાં અંતમાં અંગ્રેજી બોલતા કાગળોમાં 'સોબોલ' ક્રમ શબ્દ રજૂ કરવામાં આવ્યો હતો. એક ઝડપી અલ્ગોરિધમ એન્ટોનોવ અને સાલેવ દ્વારા વધુ કાર્યક્ષમ ગ્રે કોડ અમલીકરણની દરખાસ્ત કરવામાં આવી હતી. જ્યાં સુધી 'સોબોલ' સંખ્યાઓની પેઢીની વાત છે, ત્યાં સુધી તેઓ સ્પષ્ટ રીતે n-th પોઇન્ટ ડ્રો બનાવવા માટે n ને બદલે ગ્રે કોડનો ઉપયોગ કરીને મદદ કરે છે. ધારો કે આપણે પહેલેથી જ તમામ સોબોલ 'ક્રમ n − 1 સુધી દોરી ગયો છે અને તમામ જરૂરી પરિમાણો માટે xn − 1, j મૂલ્યોને મેમરીમાં રાખ્યા છે. ગ્રે કોડ G (n) અગાઉના G (n−1) કરતા માત્ર એકથી અલગ હોવાથી, કહો કે k-th, બીટ (જે n−1નો સૌથી જમણો શૂન્ય બીટ છે), દરેક પરિમાણ માટે માત્ર એક જ XOR ઓપરેશન કરવાની જરૂર છે જેથી તમામ xn−1 ને xn, એટલે કે xn સુધી ફેલાવી શકાય. વધારાના એકરૂપતા ગુણધર્મો 'સોબોલ' એ મિલકત એ અને એ 'તરીકે ઓળખાતી વધારાની એકરૂપતા શરતો રજૂ કરી. વ્યાખ્યા 2d લંબાઈના d-પરિમાણીય ક્રમના કોઈપણ દ્વિસંગી વિભાગ (મનસ્વી સબસેટ નહીં) માટે દરેક 2d હાયપરક્યુબ્સમાં બરાબર એક ડ્રો હોય છે જે એકમ હાયપરક્યુબને તેના દરેક લંબાઈના વિસ્તરણ સાથે અડધા ભાગમાં વિભાજિત કરવાથી પરિણમે છે. વ્યાખ્યા ઓછી વિસંગતતા ધરાવતો ક્રમ ગુણધર્મ A 'ને સંતોષ આપે છે, જો લંબાઈ 4d ના d-પરિમાણીય ક્રમના કોઈપણ દ્વિસંગી વિભાગ (મનસ્વી સબસેટ નહીં) માટે દરેક 4d હાયપરક્યુબ્સમાં બરાબર એક ડ્રો હોય, જે એકમ હાયપરક્યુબને તેના દરેક લંબાઈના વિસ્તરણ સાથે ચાર સમાન ભાગોમાં વિભાજિત કરવાથી પરિણમે છે. એવી ગાણિતિક પરિસ્થિતિઓ છે જે ગુણધર્મો A અને A 'ની બાંયધરી આપે છે. પ્રમેય 'd-પરિમાણીય સોબોલ' અનુક્રમમાં ગુણધર્મ A iff છે જ્યાં Vd એ d × d દ્વિસંગી મેટ્રિક્સ છે જે vk, j, m દ્વારા વ્યાખ્યાયિત થયેલ છે, જે દિશા સંખ્યા vk, j = (0. vk, j, 1vk, j, 2.) 2 ના દ્વિસંગી બિંદુ પછી m-th અંકને સૂચવે છે. પ્રમેય 'd-પરિમાણીય સોબોલ' અનુક્રમ ગુણધર્મ A 'iff ધરાવે છે જ્યાં Ud એ 2d × 2d દ્વિસંગી મેટ્રિક્સ છે જે vk, j, m દ્વારા વ્યાખ્યાયિત થયેલ છે જે દિશા સંખ્યા vk, j = (0. vk, j, 1vk, j, 2.) 2 ના દ્વિસંગી બિંદુ પછી m-th અંકને સૂચવે છે. ગુણ A અને A 'માટેના પરીક્ષણો સ્વતંત્ર છે. આમ એ અને એ બંને ગુણધર્મોને સંતોષતા 'સોબોલ' ક્રમની રચના કરવી શક્ય છે અથવા તેમાંથી માત્ર એક જ. 'સોબોલ' સંખ્યાઓનું આરંભીકરણ 'સોબોલ' ક્રમ બનાવવા માટે, દિશા સંખ્યાઓ vi, j નો સમૂહ પસંદ કરવાની જરૂર છે. પ્રારંભિક દિશા સંખ્યાઓની પસંદગીમાં થોડી સ્વતંત્રતા છે. તેથી, પસંદ કરેલા પરિમાણો માટે 'સોબોલ' ક્રમની વિવિધ અનુભૂતિઓ પ્રાપ્ત કરવી શક્ય છે. પ્રારંભિક સંખ્યાઓની ખરાબ પસંદગી ગણતરી માટે ઉપયોગમાં લેવાતી વખતે 'સોબોલ' ક્રમની કાર્યક્ષમતામાં નોંધપાત્ર ઘટાડો કરી શકે છે. પ્રારંભિક સંખ્યાઓ માટે સૌથી સરળ પસંદગી એ છે કે માત્ર l-th ડાબી બાજુનો બીટ સેટ હોવો જોઈએ, અને અન્ય તમામ બિટ્સ શૂન્ય હોવા જોઈએ, એટલે કે. mk, j = 1 બધા k અને j માટે. આ આરંભીકરણને સામાન્ય રીતે એકમ આરંભીકરણ કહેવામાં આવે છે. જો કે, આવા ક્રમ નીચા પરિમાણો માટે પણ ગુણધર્મ એ અને એ માટે પરીક્ષણમાં નિષ્ફળ જાય છે અને તેથી આ પ્રારંભિકતા ખરાબ છે. અમલીકરણ અને ઉપલબ્ધતા વિવિધ પરિમાણો માટે સારા પ્રારંભિક સંખ્યાઓ ઘણા લેખકો દ્વારા પ્રદાન કરવામાં આવે છે. ઉદાહરણ તરીકે, 'સોબોલ' 51 સુધીના પરિમાણો માટે પ્રારંભિક સંખ્યાઓ પ્રદાન કરે છે. પ્રારંભિક સંખ્યાઓના સમાન સમૂહનો ઉપયોગ બ્રેટલી અને ફોક્સ દ્વારા કરવામાં આવે છે. ઉચ્ચ પરિમાણો માટે પ્રારંભિક સંખ્યાઓ જૉ અને કુઓ પર ઉપલબ્ધ છે. પીટર જેકેલે તેમના પુસ્તક "મોન્ટે કાર્લો મેથડ્સ ઇન ફાઇનાન્સ" માં પરિમાણ 32 સુધીની પ્રારંભિક સંખ્યાઓ પ્રદાન કરી છે. અન્ય અમલીકરણ સોફ્ટવેરના આંકડાકીય વાનગીઓના સંગ્રહમાં સી, ફોરટ્રાન 77 અથવા ફોરટ્રાન 90 દિનચર્યાઓ તરીકે ઉપલબ્ધ છે. જૉ અને કુઓ પ્રારંભિક સંખ્યાઓ પર આધારિત 1111 પરિમાણો સુધી મફત/ઓપન-સોર્સ અમલીકરણ, સીમાં અને પાયથોન અને જુલિયામાં 21201 પરિમાણો સુધી ઉપલબ્ધ છે. સી + +, ફોરટ્રાન 90, મેટલેબ અને પાયથોન માટે 1111 પરિમાણો સુધી એક અલગ મફત/ઓપન-સોર્સ અમલીકરણ ઉપલબ્ધ છે. છેવટે, વ્યાવસાયિક 'સોબોલ' અનુક્રમ જનરેટર, ઉદાહરણ તરીકે, એન. એ. જી. પુસ્તકાલયમાં ઉપલબ્ધ છે. એક સંસ્કરણ બ્રિટિશ-રશિયન ઓફશોર ડેવલપમેન્ટ એજન્સી (બી. આર. ઓ. ડી. એ.) પાસેથી ઉપલબ્ધ છે. MATLAB તેના સ્ટેટિસ્ટિક્સ ટૂલબોક્સના ભાગ રૂપે અમલીકરણ પણ ધરાવે છે. ઓછી વિસંગતતા શ્રેણીઓ અર્ધ-મોન્ટે કાર્લો પદ્ધતિ નોંધો સંદર્ભો બાહ્ય કડીઓ ACM ના એકત્રિત અલ્ગોરિધમ્સ જુઓ (અલ્ગોરિધમ્સ 647,659, અને 738 જુઓ.) 'સોબોલ' સિક્વન્સ જનરેટર પ્રોગ્રામિંગ કોડનો સંગ્રહ 'સોબોલ' સિક્વન્સના ફ્રીવેર સી + + જનરેટર ઓછી વિસંગતતા સિક્વન્સ સિક્વન્સ અને સિરીઝ