Randomized rounding
কম্পিউটার বিজ্ঞান এবং অপারেশন গবেষণায়, র্যান্ডমাইজড রাউন্ডিং হল আনুমানিক অ্যালগরিদম ডিজাইন এবং বিশ্লেষণের জন্য ব্যাপকভাবে ব্যবহৃত একটি পদ্ধতি। অনেক কম্বিনেটোরিয়াল অপ্টিমাইজেশান সমস্যা সঠিকভাবে (অপ্টিমালিটি) সমাধান করার জন্য গণনামূলকভাবে জটিল। এই ধরনের সমস্যার জন্য, র্যান্ডমাইজড রাউন্ডিং দ্রুত (বহুপদী সময়) আনুমানিক অ্যালগরিদম ডিজাইন করতে ব্যবহার করা যেতে পারে-অর্থাৎ, যে কোনও ইনপুট দেওয়া প্রায় সর্বোত্তম সমাধান ফেরত দেওয়ার নিশ্চয়তা দেওয়া অ্যালগরিদম। র্যান্ডমাইজড রাউন্ডিং-এর মূল ধারণা হল সমস্যার শিথিলকরণের একটি সর্বোত্তম সমাধানকে মূল সমস্যার প্রায় সর্বোত্তম সমাধানে রূপান্তর করা। ফলস্বরূপ অ্যালগরিদম সাধারণত সম্ভাব্য পদ্ধতি ব্যবহার করে বিশ্লেষণ করা হয়। সংক্ষিপ্ত বিবরণ মৌলিক পদ্ধতির তিনটি ধাপ রয়েছেঃ একটি পূর্ণসংখ্যা রৈখিক প্রোগ্রাম (আইএলপি) হিসাবে সমাধান করার জন্য সমস্যাটি প্রণয়ন করুন। আইএলপি-র লিনিয়ার প্রোগ্রামিং রিল্যাক্সেশন (এলপি)-এর একটি সর্বোত্তম ভগ্নাংশ সমাধান গণনা করুন। এল. পি-র ভগ্নাংশ সমাধানকে আই. এল. পি-র একটি পূর্ণসংখ্যা সমাধানে বৃত্তাকার করুন। (যদিও পদ্ধতিটি সাধারণত রৈখিক প্রোগ্রামগুলির সাথে প্রয়োগ করা হয়, তবে কখনও কখনও অন্যান্য ধরণের শিথিলকরণ ব্যবহার করা হয়। উদাহরণস্বরূপ, গোম্যানস এবং উইলিয়ামসনের সেমিডিফাইনাইট প্রোগ্রামিং-ভিত্তিক ম্যাক্স-কাট আনুমানিক অ্যালগরিদম দেখুন।) প্রথম ধাপে, চ্যালেঞ্জ হল একটি উপযুক্ত পূর্ণসংখ্যা রৈখিক প্রোগ্রাম নির্বাচন করা। রৈখিক প্রোগ্রামিংয়ের সাথে পরিচিতি, বিশেষত রৈখিক প্রোগ্রাম এবং পূর্ণসংখ্যা রৈখিক প্রোগ্রাম ব্যবহার করে মডেলিং করা প্রয়োজন। অনেক সমস্যার জন্য, একটি প্রাকৃতিক পূর্ণসংখ্যা রৈখিক প্রোগ্রাম রয়েছে যা ভাল কাজ করে, যেমন নীচের সেট কভার উদাহরণে। (পূর্ণসংখ্যা রৈখিক প্রোগ্রামে একটি ছোট অবিচ্ছেদ্য ব্যবধান থাকা উচিত; প্রকৃতপক্ষে যাদৃচ্ছিক বৃত্তাকার প্রায়শই অবিচ্ছেদ্য ব্যবধানের সীমা প্রমাণ করতে ব্যবহৃত হয়।) দ্বিতীয় ধাপে, সর্বোত্তম ভগ্নাংশ সমাধানটি সাধারণত যে কোনও স্ট্যান্ডার্ড লিনিয়ার প্রোগ্রামিং অ্যালগরিদম ব্যবহার করে বহুপদী সময়ে গণনা করা যেতে পারে। তৃতীয় ধাপে, ভগ্নাংশ সমাধানকে অবশ্যই একটি পূর্ণসংখ্যা সমাধানে রূপান্তরিত করতে হবে (এবং এইভাবে মূল সমস্যার সমাধান)। একে বলা হয় ভগ্নাংশ সমাধানকে বৃত্তাকার করা। ফলস্বরূপ পূর্ণসংখ্যা সমাধানের খরচ (প্রমাণযোগ্যভাবে) ভগ্নাংশ সমাধানের খরচের চেয়ে অনেক বেশি হওয়া উচিত নয়। এটি নিশ্চিত করবে যে পূর্ণসংখ্যা সমাধানের খরচ সর্বোত্তম পূর্ণসংখ্যা সমাধানের খরচের চেয়ে অনেক বেশি নয়। তৃতীয় ধাপ (রাউন্ডিং) করার জন্য ব্যবহৃত প্রধান কৌশলটি হল র্যান্ডমাইজেশন ব্যবহার করা, এবং তারপরে রাউন্ডিংয়ের কারণে ব্যয় বৃদ্ধির জন্য সম্ভাব্য যুক্তি ব্যবহার করা (কম্বিনেটরিক্স থেকে সম্ভাব্য পদ্ধতি অনুসরণ করে)। এতে, সম্ভাব্য যুক্তিগুলি কাঙ্ক্ষিত বৈশিষ্ট্য সহ বিচ্ছিন্ন কাঠামোর অস্তিত্ব দেখানোর জন্য ব্যবহার করা হয়। এই প্রসঙ্গে, নিম্নলিখিতগুলি দেখানোর জন্য এই ধরনের যুক্তি ব্যবহার করা হয়ঃ এল. পি-র যে কোনও ভগ্নাংশ সমাধানের পরিপ্রেক্ষিতে, ধনাত্মক সম্ভাবনার সাথে র্যান্ডমাইজড রাউন্ডিং প্রক্রিয়া একটি পূর্ণসংখ্যা সমাধান তৈরি করে যা কিছু কাঙ্ক্ষিত মানদণ্ড অনুযায়ী আনুমানিক হয়। পরিশেষে, তৃতীয় ধাপটিকে গণনামূলকভাবে দক্ষ করার জন্য, একটি হয় দেখায় যে এটি উচ্চ সম্ভাবনার সাথে আনুমানিক (যাতে ধাপটি এলোমেলোভাবে থাকতে পারে) অথবা একটি সাধারণত শর্তাধীন সম্ভাবনার পদ্ধতি ব্যবহার করে বৃত্তাকার ধাপটিকে বিকৃত করে। পরের পদ্ধতিটি র্যান্ডমাইজড রাউন্ডিং প্রক্রিয়াকে একটি দক্ষ নির্ধারক প্রক্রিয়ায় রূপান্তরিত করে যা একটি ভাল ফলাফলে পৌঁছানোর নিশ্চয়তা দেয়। উদাহরণস্বরূপঃ সেট কভার সমস্যা নিম্নলিখিত উদাহরণটি দেখায় যে কীভাবে র্যান্ডমাইজড রাউন্ডিং সেট কভার সমস্যার জন্য একটি আনুমানিক অ্যালগরিদম ডিজাইন করতে ব্যবহার করা যেতে পারে। একটি মহাবিশ্বের উপর সেট কভারের যে কোনও উদাহরণ ঠিক করুন। ভগ্নাংশ সমাধান গণনা করা প্রথম ধাপের জন্য, এই উদাহরণের জন্য সেট কভারের জন্য আইপি স্ট্যান্ডার্ড পূর্ণসংখ্যা রৈখিক প্রোগ্রাম হতে দিন। দ্বিতীয় ধাপের জন্য, এল. পি. কে আই. পি-র রৈখিক প্রোগ্রামিং শিথিলকরণ হতে দিন এবং যে কোনও মানক রৈখিক প্রোগ্রামিং অ্যালগরিদম ব্যবহার করে এল. পি-র একটি সর্বোত্তম সমাধান গণনা করুন। এটি ইনপুট আকারে পলিনোমিয়াল নিতে সময় নেয়। এলপি-র সম্ভাব্য সমাধানগুলি হল ভেক্টর যা প্রতিটি সেটকে একটি অ-নেতিবাচক ওজন নির্ধারণ করে, যেমন, প্রতিটি উপাদানের জন্য, আচ্ছাদন-ধারণকারী সেটগুলির জন্য নির্ধারিত মোট ওজন কমপক্ষে 1, অর্থাৎ, সর্বোত্তম সমাধান হল একটি সম্ভাব্য সমাধান যার খরচ যতটা সম্ভব কম। মনে রাখবেন যে কোনও সেট কভার একটি সম্ভাব্য সমাধান দেয় (যেখানে, অন্যথায়)। এর খরচ সমান, অর্থাৎ, অন্য কথায়, লিনিয়ার প্রোগ্রাম এল. পি হল প্রদত্ত সেট-কভার সমস্যার একটি শিথিলতা। যেহেতু এল. পি-র সম্ভাব্য সমাধানগুলির মধ্যে ন্যূনতম খরচ রয়েছে, তাই সর্বোত্তম সেট কভারের খরচের উপর এর খরচ কম। র্যান্ডমাইজড রাউন্ডিং ধাপ 3য় ধাপে, আমাদের অবশ্যই ন্যূনতম ব্যয়ের ভগ্নাংশ সেট কভারকে একটি সম্ভাব্য পূর্ণসংখ্যা সমাধানে (একটি প্রকৃত সেট কভারের সাথে সম্পর্কিত) রূপান্তর করতে হবে। বৃত্তাকার পদক্ষেপটি এমন একটি উৎপাদন করতে হবে, যার ইতিবাচক সম্ভাব্যতা সহ, ব্যয়ের একটি ছোট ফ্যাক্টরের মধ্যে খরচ রয়েছে। তারপর (যেহেতু এর খরচ সর্বোত্তম সেট কভারের ব্যয়ের উপর কম সীমাবদ্ধ), এর খরচ সর্বোত্তম ব্যয়ের একটি ছোট ফ্যাক্টরের মধ্যে থাকবে। একটি সূচনা বিন্দু হিসাবে, সবচেয়ে স্বাভাবিক বৃত্তাকার পরিকল্পনাটি বিবেচনা করুনঃ প্রতিটি সেটের জন্য, সম্ভাব্যতা সহ নিন, অন্যথায় নিন। এই বৃত্তাকার পরিকল্পনার সাথে, নির্বাচিত সেটগুলির প্রত্যাশিত খরচ সর্বাধিক, ভগ্নাংশ কভারের খরচ। এ তো ভালো কথা। দুর্ভাগ্যবশত কভারেজ ভালো নয়। যখন ভেরিয়েবলগুলি ছোট হয়, তখন কোনও উপাদানটি আচ্ছাদিত না হওয়ার সম্ভাবনা প্রায় হয় সুতরাং শুধুমাত্র উপাদানগুলির একটি ধ্রুবক ভগ্নাংশ প্রত্যাশায় আচ্ছাদিত হবে। উচ্চ সম্ভাব্যতা সহ প্রতিটি উপাদানকে আচ্ছাদন করার জন্য, স্ট্যান্ডার্ড রাউন্ডিং স্কিমটি প্রথমে একটি উপযুক্ত ফ্যাক্টর দ্বারা রাউন্ডিং সম্ভাব্যতাগুলিকে স্কেল করে। এখানে স্ট্যান্ডার্ড রাউন্ডিং স্কিম রয়েছেঃ একটি প্যারামিটার ঠিক করুন। পালাক্রমে প্রতিটি সেটের জন্য, সম্ভাবনার সাথে নিন, অন্যথায় নিন। সম্ভাব্যতা বৃদ্ধি করে প্রত্যাশিত খরচ বৃদ্ধি করে, তবে সমস্ত উপাদানের কভারেজকে সম্ভাব্য করে তোলে। ধারণাটি হল যতটা সম্ভব ছোট বেছে নেওয়া যাতে সমস্ত উপাদানগুলি অ-শূন্য সম্ভাবনার সাথে প্রমাণিতভাবে আচ্ছাদিত থাকে। এখানে একটি বিস্তারিত বিশ্লেষণ রয়েছে। লেম্মা (বৃত্তাকার পরিকল্পনার জন্য আনুমানিক গ্যারান্টি) ঠিক করুন। ইতিবাচক সম্ভাবনার সাথে, বৃত্তাকার প্রকল্পটি সর্বাধিক ব্যয়ের একটি নির্দিষ্ট কভার প্রদান করে (এবং এইভাবে সর্বোত্তম সেট কভারের ব্যয়ের গুণ)। (দ্রষ্টব্যঃ যত্ন সহকারে হ্রাস করা যেতে পারে।) প্রমাণ র্যান্ডম রাউন্ডিং স্কিমের আউটপুটের কাঙ্ক্ষিত বৈশিষ্ট্য রয়েছে যতক্ষণ না নিম্নলিখিত "খারাপ" ঘটনাগুলির কোনওটিই ঘটে নাঃ অতিক্রমের খরচ, বা কিছু উপাদানের জন্য, আচ্ছাদন করতে ব্যর্থ হয়। প্রত্যেকের প্রত্যাশা সর্বাধিক। প্রত্যাশার রৈখিকতা দ্বারা, এর প্রত্যাশা সর্বাধিক হয়। সুতরাং, মার্কভের অসমতা অনুসারে, উপরের প্রথম খারাপ ঘটনার সম্ভাবনা সর্বাধিক। অবশিষ্ট খারাপ ঘটনাগুলির জন্য (প্রতিটি উপাদানের জন্য একটি), মনে রাখবেন যে, যেহেতু কোনও প্রদত্ত উপাদানের জন্য, যে সম্ভাবনাটি অন্তর্ভুক্ত করা হয় না তা হল (এটি বৈষম্য ব্যবহার করে, যা এর জন্য কঠোর।) সুতরাং, প্রতিটি উপাদানের জন্য, উপাদানটি আচ্ছাদিত না হওয়ার সম্ভাবনা এর চেয়ে কম। ইউনিয়ন বাউন্ড দ্বারা, খারাপ ঘটনাগুলির মধ্যে একটি ঘটার সম্ভাবনা তার চেয়ে কম। সুতরাং, ইতিবাচক সম্ভাবনার সাথে কোনও খারাপ ঘটনা নেই এবং এটি সর্বাধিক ব্যয়ের একটি নির্দিষ্ট আবরণ। শর্তসাপেক্ষ সম্ভাবনার পদ্ধতি ব্যবহার করে কিউইডি ড্যারান্ডোমাইজেশন উপরের লেম্মাটি ব্যয়ের একটি নির্দিষ্ট আবরণের অস্তিত্ব দেখায়)। এই প্রসঙ্গে আমাদের লক্ষ্য হল একটি দক্ষ আনুমানিক অ্যালগরিদম, কেবল একটি অস্তিত্ব প্রমাণ নয়, তাই আমাদের কাজ শেষ হয়নি। একটি পদ্ধতি হ 'ল কিছুটা বৃদ্ধি করা, তারপরে দেখান যে সাফল্যের সম্ভাবনা কমপক্ষে, ধরুন, 1/4। এই পরিবর্তনের মাধ্যমে, র্যান্ডম রাউন্ডিং ধাপটি কয়েকবার পুনরাবৃত্তি করা উচ্চ সম্ভাবনার সাথে একটি সফল ফলাফল নিশ্চিত করার জন্য যথেষ্ট। এই পদ্ধতিটি আনুমানিক অনুপাতকে দুর্বল করে দেয়। এরপরে আমরা একটি ভিন্ন পদ্ধতির বর্ণনা দিই যা একটি নির্ধারক অ্যালগরিদম প্রদান করে যা উপরের অস্তিত্ব প্রমাণের আনুমানিক অনুপাতের সাথে মেলে। এই পদ্ধতিকে বলা হয় শর্তাধীন সম্ভাবনার পদ্ধতি। নির্ধারক অ্যালগরিদম র্যান্ডমাইজড রাউন্ডিং স্কিম অনুকরণ করেঃ এটি প্রতিটি সেটকে পর্যায়ক্রমে বিবেচনা করে এবং বেছে নেয়। কিন্তু এলোমেলোভাবে প্রতিটি পছন্দ করার পরিবর্তে, এটি সিদ্ধান্তমূলকভাবে পছন্দ করে, যাতে ব্যর্থতার শর্তাধীন সম্ভাবনা বজায় রাখা যায়, এখনও পর্যন্ত পছন্দগুলি 1-এর নিচে দেওয়া হয়েছে। ব্যর্থতার শর্তাধীন সম্ভাবনাকে সীমাবদ্ধ করা আমরা প্রতিটি পরিবর্তনশীলকে পালাক্রমে নির্ধারণ করতে সক্ষম হতে চাই যাতে ব্যর্থতার শর্তাধীন সম্ভাবনা 1-এর নিচে রাখা যায়। এটি করার জন্য, আমাদের ব্যর্থতার শর্তাধীন সম্ভাবনার উপর একটি ভাল সীমাবদ্ধতা প্রয়োজন। মূল অস্তিত্ব প্রমাণকে পরিমার্জন করার মাধ্যমে সীমাবদ্ধতা আসবে। সেই প্রমাণটি র্যান্ডম ভেরিয়েবলের প্রত্যাশার দ্বারা ব্যর্থতার সম্ভাবনাকে অন্তর্নিহিতভাবে সীমাবদ্ধ করে, যেখানে শেষে অনাবৃত থাকা উপাদানগুলির সেট রয়েছে। র্যান্ডম ভেরিয়েবলটি কিছুটা রহস্যময় বলে মনে হতে পারে, তবে এটি একটি নিয়মতান্ত্রিক উপায়ে সম্ভাব্য প্রমাণকে প্রতিফলিত করে। প্রথম টার্মটি আসে মার্কভের অসমতা প্রয়োগ করে প্রথম খারাপ ঘটনার সম্ভাবনাকে সীমাবদ্ধ করার জন্য (খরচ খুব বেশি)। এর খরচ যদি খুব বেশি হয় তবে এটি কমপক্ষে 1-এর অবদান রাখে। দ্বিতীয় পদটি দ্বিতীয় ধরনের (অনাবৃত উপাদান) খারাপ ঘটনার সংখ্যা গণনা করে। যদি কোনও উপাদান অনাবৃত থাকে তবে এটি কমপক্ষে 1 অবদান রাখে। সুতরাং, যে কোনও ফলাফলে যেখানে 1-এর কম, সেখানে অবশ্যই সমস্ত উপাদানকে অন্তর্ভুক্ত করতে হবে এবং লেমা থেকে কাঙ্ক্ষিত সীমা পূরণ করতে হবে। সংক্ষেপে, যদি বৃত্তাকার পদক্ষেপটি ব্যর্থ হয়, তাহলে। এটি (মার্কভের বৈষম্য দ্বারা) বোঝায় যা ব্যর্থতার সম্ভাবনার উপর একটি ঊর্ধ্বসীমা। লক্ষ্য করুন যে উপরের যুক্তিটি ইতিমধ্যে লেম্মার প্রমাণের মধ্যে অন্তর্নিহিত, যা গণনার মাধ্যমেও তা দেখায়। শর্তাধীন সম্ভাবনার পদ্ধতি প্রয়োগ করার জন্য, বৃত্তাকার ধাপ এগিয়ে যাওয়ার সাথে সাথে আমাদের ব্যর্থতার শর্তাধীন সম্ভাব্যতাকে আবদ্ধ করার জন্য যুক্তিটি প্রসারিত করতে হবে। সাধারণত, এটি একটি নিয়মতান্ত্রিক উপায়ে করা যেতে পারে, যদিও এটি প্রযুক্তিগতভাবে ক্লান্তিকর হতে পারে। সুতরাং, ব্যর্থতার শর্তাধীন সম্ভাব্যতা সম্পর্কে কী বলা যায় কারণ বৃত্তাকার ধাপটি সেটগুলির মধ্য দিয়ে পুনরাবৃত্তি করে? যেহেতু যে কোনও ফলাফলে যেখানে মার্কভের অসমতা দ্বারা বৃত্তাকার পদক্ষেপটি ব্যর্থ হয়, ব্যর্থতার শর্তাধীন সম্ভাবনা সর্বাধিক শর্তাধীন প্রত্যাশা। এরপরে আমরা শর্তসাপেক্ষ প্রত্যাশা গণনা করি, ঠিক যেমন আমরা মূল প্রমাণের শর্তহীন প্রত্যাশা গণনা করেছি। কিছু পুনরাবৃত্তির শেষে বৃত্তাকার প্রক্রিয়ার অবস্থা বিবেচনা করুন। এখন পর্যন্ত বিবেচিত সেটগুলি (প্রথম সেটগুলি) বোঝানো যাক। (আংশিকভাবে নির্ধারিত) ভেক্টরকে বোঝানো যাক (তাই শুধুমাত্র যদি নির্ধারণ করা হয়)। প্রতিটি সেটের জন্য, 1-এ সেট করা সম্ভাব্যতা নির্দেশ করা যাক। আসুন এখনও আবৃত নয় এমন উপাদানগুলি ধারণ করি। তারপর শর্তসাপেক্ষ প্রত্যাশা, এখন পর্যন্ত করা পছন্দগুলি দেওয়া হয়েছে, অর্থাৎ, দেওয়া হয়েছে, নোট যা শুধুমাত্র পুনরাবৃত্তির পরে নির্ধারিত হয়। ব্যর্থতার শর্তসাপেক্ষ সম্ভাবনা 1-এর নিচে রাখা ব্যর্থতার শর্তসাপেক্ষ সম্ভাবনা 1-এর নিচে রাখতে, শর্তসাপেক্ষ প্রত্যাশা 1-এর নিচে রাখা যথেষ্ট। এটি করার জন্য, বৃদ্ধি থেকে শর্তসাপেক্ষ প্রত্যাশা বজায় রাখা যথেষ্ট। অ্যালগরিদম এটাই করবে। এটি (কোথায়) নিশ্চিত করার জন্য প্রতিটি পুনরাবৃত্তিতে সেট করা হবে। তৃতীয় পুনরাবৃত্তিতে, অ্যালগরিদম কীভাবে তা নিশ্চিত করতে পারে? দেখা যাচ্ছে যে এটি সহজভাবে সেট করতে পারে যাতে এর ফলস্বরূপ মান হ্রাস করা যায়। কেন তা দেখতে, পুনরাবৃত্তি শুরু হওয়ার সময় বিন্দুতে মনোনিবেশ করুন। সেই সময়ে, নির্ধারিত হয়, কিন্তু এখনও নির্ধারিত হয় না---পুনরাবৃত্তিতে কীভাবে সেট করা হয় তার উপর নির্ভর করে এটি দুটি সম্ভাব্য মান নিতে পারে। এর মান নির্দেশ করা যাক। ধরা যাক এবং, এর দুটি সম্ভাব্য মান নির্দেশ করুন, যা যথাক্রমে 0 বা 1-এ সেট করা আছে কিনা তার উপর নির্ভর করে। শর্তাধীন প্রত্যাশার সংজ্ঞা অনুসারে, যেহেতু দুটি পরিমাণের ওজনযুক্ত গড় সর্বদা সেই দুটি পরিমাণের মধ্যে সর্বনিম্ন হয়, তাই এটি অনুসরণ করে যে এইভাবে, সেটিং যাতে ফলাফলের মানকে হ্রাস করা যায় তা নিশ্চিত করবে। অ্যালগরিদম এটাই করবে। বিস্তারিতভাবে, এর অর্থ কী? একটি ফাংশন হিসাবে বিবেচিত (অন্যান্য সমস্ত পরিমাণ স্থির সহ) একটি রৈখিক ফাংশন, এবং সেই ফাংশনের সহগ হল সুতরাং, অ্যালগরিদমটি 0 এ সেট করা উচিত যদি এই অভিব্যক্তিটি ধনাত্মক হয়, এবং অন্যথায় 1। এটি নিম্নলিখিত অ্যালগরিদম দেয়। সেট কভার ইনপুটের জন্য র্যান্ডমাইজড-রাউন্ডিং অ্যালগরিদমঃ সেট সিস্টেম, মহাবিশ্ব, খরচ ভেক্টর আউটপুটঃ সেট কভার (সেট কভারের জন্য স্ট্যান্ডার্ড পূর্ণসংখ্যা রৈখিক প্রোগ্রামের একটি সমাধান) একটি ন্যূনতম-খরচ ভগ্নাংশ সেট কভার গণনা করুন (এলপি শিথিলকরণের একটি সর্বোত্তম সমাধান)। যাক। প্রত্যেকের জন্য ছেড়ে দিন। প্রত্যেকের জন্যঃ যাক। (এতে এখনও নির্ধারিত নয় এমন সেট রয়েছে।) যদি তারপর সেট করা থাকে, অন্যথায় সেট এবং। (এতে এখনও আচ্ছাদিত নয় এমন উপাদান রয়েছে।) ফিরে আসুন। লেম্মা (অ্যালগরিদমের জন্য আনুমানিক গ্যারান্টি) উপরের অ্যালগরিদমটি যে কোনও (ভগ্নাংশ) সেট কভারের সর্বনিম্ন ব্যয়ের বেশিরভাগ সময়ে ব্যয়ের একটি সেট কভার প্রদান করে। প্রমাণ অ্যালগরিদম নিশ্চিত করে যে, এর শর্তাধীন প্রত্যাশা প্রতিটি পুনরাবৃত্তিতে বৃদ্ধি পায় না। যেহেতু এই শর্তাধীন প্রত্যাশা প্রাথমিকভাবে 1-এর চেয়ে কম (যেমন আগে দেখানো হয়েছে), অ্যালগরিদম নিশ্চিত করে যে শর্তাধীন প্রত্যাশা 1-এর নিচে থাকে। যেহেতু ব্যর্থতার শর্তাধীন সম্ভাবনা সর্বাধিক শর্তাধীন প্রত্যাশা, এইভাবে অ্যালগরিদম নিশ্চিত করে যে ব্যর্থতার শর্তাধীন সম্ভাবনা 1 এর নিচে থাকে। সুতরাং, শেষ পর্যন্ত, যখন সমস্ত পছন্দ নির্ধারণ করা হয়, অ্যালগরিদম একটি সফল ফলাফলে পৌঁছায়। অর্থাৎ, উপরের অ্যালগরিদমটি যে কোনও (ভগ্নাংশ) সেট কভারের সর্বনিম্ন ব্যয়ের বেশিরভাগ সময়ে ব্যয়ের একটি সেট কভার প্রদান করে। মন্তব্য উপরের উদাহরণে, অ্যালগরিদমটি একটি এলোমেলো চলকের শর্তাধীন প্রত্যাশা দ্বারা পরিচালিত হয়েছিল। কিছু ক্ষেত্রে, একটি সঠিক শর্তাধীন প্রত্যাশার পরিবর্তে, কিছু শর্তাধীন প্রত্যাশার উপর একটি উচ্চ সীমা (বা কখনও কখনও একটি নিম্ন সীমা) ব্যবহার করা হয়। একে বলা হয় হতাশাবাদী প্রাক্কলনকারী। সম্ভাব্য পদ্ধতির অন্যান্য প্রয়োগের সাথে তুলনা র্যান্ডমাইজড রাউন্ডিং ধাপটি সম্ভাব্য পদ্ধতির বেশিরভাগ প্রয়োগের থেকে দুটি দিক থেকে আলাদাঃ বৃত্তাকার ধাপের গণনামূলক জটিলতা গুরুত্বপূর্ণ। এটি একটি উপবাস দ্বারা বাস্তবায়নযোগ্য হওয়া উচিত (যেমন। বহুপদী সময়) অ্যালগরিদম। র্যান্ডম পরীক্ষার অন্তর্নিহিত সম্ভাব্যতা বিতরণ হল সমস্যার উদাহরণের শিথিলকরণের সমাধানের একটি ফাংশন। এই সত্যটি আনুমানিক অ্যালগরিদম-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- তুলনায়, সংমিশ্রণে সম্ভাব্য পদ্ধতির প্রয়োগগুলি সাধারণত এমন কাঠামোর অস্তিত্ব দেখায় যার বৈশিষ্ট্যগুলি ইনপুটের অন্যান্য পরামিতিগুলির উপর নির্ভর করে। উদাহরণস্বরূপ, তুরানের উপপাদ্য বিবেচনা করুন, যা বলা যেতে পারে "গড় মাত্রার শীর্ষ সহ যে কোনও গ্রাফের কমপক্ষে একটি স্বাধীন আকারের সেট থাকতে হবে। (তুরানের উপপাদ্যের সম্ভাব্য প্রমাণের জন্য এটি দেখুন।) যদিও এমন গ্রাফ রয়েছে যার জন্য এই সীমাটি আঁটসাঁট, এমন গ্রাফও রয়েছে যার স্বাধীন সেটগুলি এর চেয়ে অনেক বড়। সুতরাং, একটি গ্রাফে তুরানের উপপাদ্য দ্বারা বিদ্যমান স্বাধীন সেটের আকার, সাধারণভাবে, সেই গ্রাফের জন্য সর্বাধিক স্বাধীন সেটের তুলনায় অনেক ছোট হতে পারে। আরও দেখুন শর্তসাপেক্ষ সম্ভাবনার পদ্ধতি রৈখিক প্রোগ্রামটি সমাধান না করে র্যান্ডমাইজড রাউন্ডিং। রেফারেন্স। আরও পড়া অ্যালগরিদম সম্ভাব্য যুক্তি