Sobol sequence
'সোবল' সিকোয়েন্সগুলি (যাকে এল. পি. টি. ও সিকোয়েন্স বা বেস 2-এ (টি, এস) সিকোয়েন্সও বলা হয়) আধা-এলোমেলো নিম্ন-বৈষম্য সিকোয়েন্সের একটি উদাহরণ। এগুলি প্রথম 1967 সালে রাশিয়ান গণিতবিদ ইলিয়া এম. সোবল দ্বারা প্রবর্তিত হয়েছিল। এই ক্রমগুলি একক ব্যবধানের ধারাবাহিকভাবে সূক্ষ্ম অভিন্ন বিভাজন তৈরি করতে এবং তারপরে প্রতিটি মাত্রায় স্থানাঙ্কগুলি পুনর্বিন্যাস করতে দুটির ভিত্তি ব্যবহার করে। এস-মাত্রিক একক হাইপারকিউবে ভাল বন্টন ধরা যাক = [0,1] এস-মাত্রিক একক হাইপারকিউবে, এবং এফ একটি বাস্তব ইন্টিগ্রেবল ফাংশন। 'সোবল'-এর মূল অনুপ্রেরণা ছিল 'ইস'-এ একটি অনুক্রম xn তৈরি করা যাতে এবং অভিসরণ যত দ্রুত সম্ভব হয়। এটি কমবেশি স্পষ্ট যে যোগফলটি ইন্টিগ্রালের দিকে একত্রিত হওয়ার জন্য, xn পয়েন্টগুলি পূরণ করা উচিত যা গর্তগুলিকে কমিয়ে দেয়। আরেকটি ভালো বৈশিষ্ট্য হল যে, ইস-এর একটি নিম্ন-মাত্রিক মুখের উপর xn-এর অনুমানগুলি খুব কম ছিদ্র রেখে যায়। সুতরাং ইস-এর সমজাতীয় ভরাট যোগ্য নয় কারণ নিম্ন মাত্রায় অনেক পয়েন্ট একই জায়গায় থাকবে, তাই অবিচ্ছেদ্য অনুমানের জন্য অকেজো। এই ভাল বন্টনগুলিকে বলা হয় (টি, এম, এস)-নেট এবং (টি, এস)-অনুক্রমগুলি বেস বি-তে। তাদের পরিচয় করিয়ে দেওয়ার জন্য, প্রথমে একটি প্রাথমিক s-ব্যবধান সংজ্ঞায়িত করুন যার ভিত্তি b, যা Is-এর একটি উপসেট যেখানে aj এবং dj অ-ঋণাত্মক পূর্ণসংখ্যা, এবং {1,., s}-এর সমস্ত j-এর জন্য। 2টি পূর্ণসংখ্যা দেওয়া হলে, b-এর গোড়ায় a (t, m, s)-নেট হল bm বিন্দুর xn-এর এমন একটি ক্রম যা হাইপারভলিউম λ (P) = bt−m-এর গোড়ায় সমস্ত প্রাথমিক ব্যবধান P-এর জন্য। একটি অ-ঋণাত্মক পূর্ণসংখ্যা t দেওয়া হলে, b-এর গোড়ায় a (t, s)-ক্রম হল xn বিন্দুর একটি অসীম ক্রম, যাতে সমস্ত পূর্ণসংখ্যার জন্য b-এর গোড়ায় a (t, m, s)-নেট হয়। তাঁর নিবন্ধে, সোবল 'Πτ-মেশেস এবং LPτ সিকোয়েন্সগুলি বর্ণনা করেছেন, যা যথাক্রমে বেস 2-এ (t, m, s)-নেট এবং (t, s)-সিকোয়েন্স। বেস বি-তে (টি, এম, এস)-নেট এবং (টি, এস)-সিকোয়েন্স শব্দগুলি (যাকে নাইডেরাইটার সিকোয়েন্সও বলা হয়) 1988 সালে হ্যারাল্ড নাইডেরাইটার তৈরি করেছিলেন। হল্টন, ফাউরে এবং অন্যান্য কম বৈষম্যের ক্রমের তুলনায় 'সোবল' ক্রমটি ইংরেজিভাষী গবেষণাপত্রে প্রবর্তিত হয়েছিল। একটি দ্রুত অ্যালগরিদম অ্যান্টোনভ এবং সালিয়েভ দ্বারা আরও দক্ষ গ্রে কোড বাস্তবায়নের প্রস্তাব দেওয়া হয়েছিল। সোবোল সংখ্যার উৎপাদনের ক্ষেত্রে, তারা স্পষ্টভাবে n-তম পয়েন্ট ড্র নির্মাণের জন্য n এর পরিবর্তে ধূসর কোড ব্যবহার করে সহায়তা করে। ধরুন আমরা ইতিমধ্যেই সমস্ত 'সোবল' ক্রম তৈরি করেছি এবং সমস্ত প্রয়োজনীয় মাত্রার জন্য xn−1, j মানগুলি স্মৃতিতে রেখেছি। যেহেতু ধূসর কোড G (n) পূর্ববর্তী G (n−1)-এর থেকে শুধুমাত্র একটি একক দ্বারা পৃথক, ধরুন k-th, বিট (যা n−1-এর ডানদিকের শূন্যতম বিট), তাই xn−1-এর সমস্তটিকে xn-এ প্রসারিত করার জন্য প্রতিটি মাত্রার জন্য একটি একক XOR অপারেশন করা প্রয়োজন, অর্থাৎ। অতিরিক্ত অভিন্নতার বৈশিষ্ট্য 'সোবল' বৈশিষ্ট্য এ এবং এ 'নামে পরিচিত অতিরিক্ত অভিন্নতার শর্ত প্রবর্তন করে। সংজ্ঞা 2d দৈর্ঘ্যের ডি-ডাইমেনশনাল সিকোয়েন্সের কোনও বাইনারি সেগমেন্টের জন্য (কোনও নির্বিচারে উপসেট নয়) প্রতিটি 2d হাইপারকিউবে ঠিক একটি ড্র থাকলে একটি নিম্ন-বৈষম্য ক্রমকে সম্পত্তি A-কে সন্তুষ্ট বলে মনে করা হয় যা প্রতিটি দৈর্ঘ্যের এক্সটেনশন সহ ইউনিট হাইপারকিউবকে অর্ধে উপবিভাজিত করার ফলস্বরূপ। সংজ্ঞা 4d দৈর্ঘ্যের ডি-ডাইমেনশনাল সিকোয়েন্সের কোনও বাইনারি সেগমেন্টের জন্য (নির্বিচারে উপসেট নয়) প্রতিটি 4d হাইপারকিউবে ঠিক একটি ড্র থাকলে একটি নিম্ন-বৈষম্য ক্রমকে সম্পত্তি A 'কে সন্তুষ্ট বলে মনে করা হয়, যার ফলস্বরূপ একক হাইপারকিউবের প্রতিটি দৈর্ঘ্যের এক্সটেনশনকে চারটি সমান অংশে বিভক্ত করা হয়। এমন কিছু গাণিতিক শর্ত রয়েছে যা 'এ' এবং 'এ' বৈশিষ্ট্যের নিশ্চয়তা দেয়। উপপাদ্য 'ডি-ডাইমেনশনাল সোবল' ক্রমের বৈশিষ্ট্য হল এ আই. এফ. এফ যেখানে ভি. ডি হল ডি × ডি বাইনারি ম্যাট্রিক্স যা ভি. কে, জে, এম দিয়ে সংজ্ঞায়িত করা হয় যা ভি. কে, জে = (0. ভি. কে, জে, 1ভি. কে, জে, 2.) 2 দিকের বাইনারি বিন্দুর পরে এম-তম অঙ্ককে নির্দেশ করে। উপপাদ্য 'ডি-মাত্রিক সোবল' ক্রমের বৈশিষ্ট্য হল 'এ' আই. এফ. এফ যেখানে 'উদ' হল 2ডি × 2ডি বাইনারি ম্যাট্রিক্স যা 'ভিকে', 'জে', 'এম' দিয়ে সংজ্ঞায়িত করা হয়েছে, যা 'ভিকে', 'জে' = (0. ভিকে, জে, 1ভিকে, জে, 2.) 2-এর বাইনারি বিন্দুর পরে এম-তম অঙ্ককে নির্দেশ করে। 'এ' এবং 'এ' বৈশিষ্ট্যের জন্য পরীক্ষাগুলি স্বাধীন। এইভাবে 'সোবল' ক্রমটি তৈরি করা সম্ভব যা 'এ' এবং 'এ' উভয় বৈশিষ্ট্যকে সন্তুষ্ট করে বা তাদের মধ্যে কেবল একটি। 'সোবল' সংখ্যাগুলির সূচনা একটি 'সোবল' ক্রম তৈরি করতে, vi, j দিকনির্দেশক সংখ্যার একটি সেট নির্বাচন করতে হবে। প্রাথমিক দিকের সংখ্যা নির্বাচনের ক্ষেত্রে কিছুটা স্বাধীনতা রয়েছে। অতএব, নির্বাচিত মাত্রাগুলির জন্য 'সোবল' ক্রমের বিভিন্ন উপলব্ধি পাওয়া সম্ভব। প্রাথমিক সংখ্যার একটি খারাপ নির্বাচন গণনার জন্য ব্যবহার করা হলে 'সোবল' ক্রমের দক্ষতা উল্লেখযোগ্যভাবে হ্রাস করতে পারে। যুক্তিসঙ্গতভাবে প্রারম্ভিককরণ সংখ্যার জন্য সবচেয়ে সহজ পছন্দ হল এল-তম বামতম বিট সেট করা, এবং অন্যান্য সমস্ত বিট শূন্য হওয়া, অর্থাৎ। সকল k এবং j-এর জন্য mk, j = 1। এই সূচনাকে সাধারণত একক সূচনা বলা হয়। যাইহোক, এই ধরনের ক্রম কম মাত্রার জন্যও সম্পত্তি এ এবং এ-এর পরীক্ষায় ব্যর্থ হয় এবং তাই এই সূচনাটি খারাপ। বাস্তবায়ন এবং প্রাপ্যতা বিভিন্ন মাত্রার জন্য ভাল সূচনা সংখ্যা বিভিন্ন লেখক দ্বারা সরবরাহ করা হয়। উদাহরণস্বরূপ, 'সোবল' 51 পর্যন্ত মাত্রার জন্য প্রারম্ভিক সংখ্যা প্রদান করে। প্রারম্ভিক সংখ্যার একই সেট ব্র্যাটলি এবং ফক্স দ্বারা ব্যবহৃত হয়। উচ্চ মাত্রার প্রাথমিক সংখ্যা জো এবং কুওতে পাওয়া যায়। পিটার জ্যাকেল তাঁর "মন্টে কার্লো মেথডস ইন ফাইন্যান্স" বইয়ে মাত্রা 32 পর্যন্ত প্রারম্ভিক সংখ্যা প্রদান করেছেন। অন্যান্য বাস্তবায়নগুলি সি, ফোরট্রান 77, বা ফোরট্রান 90 রুটিন হিসাবে সফ্টওয়্যারের সংখ্যাসূচক রেসিপি সংগ্রহে পাওয়া যায়। জো এবং কুও সূচনা সংখ্যার উপর ভিত্তি করে 1111 মাত্রা পর্যন্ত একটি মুক্ত/মুক্ত-উৎস বাস্তবায়ন সি-তে এবং পাইথন এবং জুলিয়ায় 21201 মাত্রা পর্যন্ত পাওয়া যায়। সি + +, ফোরট্রান 90, ম্যাটল্যাব এবং পাইথনের জন্য 1111 মাত্রা পর্যন্ত একটি ভিন্ন ফ্রি/ওপেন-সোর্স বাস্তবায়ন উপলব্ধ। পরিশেষে, বাণিজ্যিক 'সোবল' সিকোয়েন্স জেনারেটর পাওয়া যায়, উদাহরণস্বরূপ, এনএজি লাইব্রেরির মধ্যে। ব্রিটিশ-রাশিয়ান অফশোর ডেভেলপমেন্ট এজেন্সি (বি. আর. ও. ডি. এ) থেকে একটি সংস্করণ পাওয়া যায়। ম্যাটল্যাবে তার পরিসংখ্যান টুলবক্সের অংশ হিসাবে একটি বাস্তবায়নও রয়েছে। আরও দেখুন নিম্ন-বৈষম্য ক্রম আধা-মন্টে কার্লো পদ্ধতি নোটস রেফারেন্স বাহ্যিক লিঙ্ক এসিএম-এর সংগৃহীত অ্যালগরিদম (অ্যালগরিদম 647,659 এবং 738 দেখুন।) 'সোবল' সিকোয়েন্স জেনারেটর প্রোগ্রামিং কোডের সংগ্রহ 'সোবল' সিকোয়েন্সের ফ্রিওয়্যার সি + + জেনারেটর নিম্ন-বৈষম্য সিকোয়েন্স এবং সিরিজ