رند کردن تصادفی با نمونه‌گیری

http://homes.cs.washington.edu/~shayan/courses/cse599/adv-approx-6.pdf

در رند کردن تصادفی معمولاً هر متغیری را جداگانه رند می‌کنیم. (رند کردن تصادفی مستقل)

اما این بار می‌خواهیم تعدادی متغیر را با هم رند کنیم. برای این کار باید ثابت کنیم که متغیرهایی که داریم با هم به آنها مقدار می‌دهیم از بازه‌ی جوابهای مجاز خارج نمی‌شوند. در این مثال از روش نمونه‌گیری، مجموعه‌ی همه‌ی درخت‌های پوشا در نظر گرفته شده است (مسئله‌ی اصلی مربوط به یک گراف بوده است) و یکی از این گرافها به صورت تصادفی انتخاب شده است. چندوجهی همه‌ی درخت‌های پوشا زیرمجموعه‌ی چندوجهی همه‌ی جوابهای ممکن است. این را با نوشتن چندوجهی درخت‌های پوشای کمینه و اثبات اینکه در قید‌های مسئله صدق می‌کنند ثابت کرده است.

با این کار ویژگی اضافه‌ای نسبت به رند کردن تصادفی به دست آورده است که همبندی جواب است. این باعث شده است که کران پایین لگاریتمی برای ضریب تقریب را که رندکردن‌های تصادفی دارند، نداشته باشد.

دلیل درست کار کردن رند‌کردن تصادفی رعایت کردن دو قید زیر است:

۱- امید ریاضی هر ترکیب خطی از متغیرها ثابت بماند.

۲- هر تابع لیپشیتز (شیب تابع باید از یک عدد ثابت کمتر باشد) از متغیرها حول میانگینش است. در حالت عادی این را با نامساوی چرنف ثابت می‌کنند.

حالا که از روش دیگری ثابت کرده‌ایم، استقلال متغیرهای تصادفی را از دست داده‌ایم و باید با روش دیگری این را ثابت کنیم. خلاصه‌ی کاری که کرده این است که نشسته حساب کرده! خودش ارجاع داده به جلسه‌ی سوم درسش و وقتی می‌روی این قسمت را می‌خوانی نوشته احتمال هر زیرمجموعه از یالهای درخت پوشای تصادفی، از احتمال اینکه آنها یک درخت تشکیل بدهند کمتر است. حالا انگار لازم است این را کسی ثابت کند که اگر یک سری یال تصادفی برداری احتمال اینکه درخت بشود کم است! تنها چیزی که من می‌بینم این است که به جای اینکه روی یک یال چرنف بزند روی زیرمجموعه‌های یالها چرنف زده است. خودتان ببینید:

http://homes.cs.washington.edu/~shayan/courses/cse599/adv-approx-3.pdf

در ادامه در مورد رند کردن تصادفی با ماکسیمم کردن آنتروپی حرف زده و گفته است که هر چقدر آنتروپی را بیشتر می‌کنیم باعث می‌شود که تصادفی بودن بیشتر بشود. (با استدلال قسمت قبل به نظر می‌رسد به اینکه میانگین صفر بشود و بتواند چرنف بزند نزدیک‌تر می‌شود.)