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

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

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

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

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

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

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

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

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

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

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

قدم زدن تصادفی: گرافهای نامتناهی و قدم‌زدن چندگانه

گفته یک آدم مست ممکنه راهش را پیدا کنه، اما یک پرنده‌ی مست ممکنه هیچ وقت راهش را پیدا نکنه!

https://www.cs.bris.ac.uk/Research/Algorithms/events/BAD16/Slides/sauerwald.pdf

یک کران پایین با استفاده از مسئله‌ی جمع کردن کوپن داده (باید از همه‌ی انواع کوپن داشته باشید، باید چند تا بخرید تا با احتمال بالایی برنده بشوید؟):

https://en.wikipedia.org/wiki/Coupon_collector%27s_problem

ثابت کرده که برای گسترگرافها کمتره. (البته الآن مقاله‌ای که من ارائه می‌دهم برای یک گسترگرافه و ثابت کرده لگاریتم n تقسیم بر توان ۲ گسترش گراف است.)

چیزی که انگار هیچ کس در نظر نگرفته این است که گذشتن همزمان چند نفر از یک رأس کار خوبی نیست. البته این به اسم intersection time ازش حرف زده.

زمان لازم برای پوشش گراف با قدم‌زدن‌های تصادفی موازی

https://arxiv.org/pdf/0705.0467.pdf

تصادف دو الگوریتم قدم زدن تصادفی

دو تا الگوریتم قدم زدن تصادفی از یک جا شروع می‌کنند، احتمال اینکه بعد از n قدم به هم برسند چقدر است؟ (یک بعدی: روی یک مسیر)

http://math.stackexchange.com/questions/118046/exact-probability-of-collision-of-two-independent-random-walkers-after-n-steps

روی گرافش چقدر می‌شود؟

حداکثر چند تا می‌شود با هم همزمان اجرا کرد که تعداد برخوردهایشان x باشد؟

به نظرم در جواب سوال قبلی اینکه از کجا شروع کنیم هم تأثیر زیادی دارد.

توپ و ظرف

احتمال اینکه هیچ سطلی خالی نماند:
http://math.stackexchange.com/questions/174674/if-n-balls-are-thrown-into-k-bins-what-is-the-probability-that-every-bin-gets-a
اگر تعداد توپ‌ها بیشتر از ظرف‌ها باشد به مسئله‌ی روز تولد مشهور است (من تا الآن فرق این دو تا را نمی‌دانستم). این را نوشته که با اصل شمول و عدم شمول ثابت می‌شود:
https://en.wikipedia.org/wiki/Birthday_problem
حالا اصلاً چیزی که من می‌خواستم حساب کنم این بود که حداکثر چند تا توپ می‌توانم بندازم که با احتمال بالایی تداخل نداشته باشند؟
با احتمال یک ان-ام در هر سطلی می‌افتند، پس با احتمال یک ان‌-ام به توان ۲ دو تا در یک سطل می‌افتند. بعد با اصل شمول و عدم شمول می‌شود نوشت. می‌شود یک به علاوه‌ی یک ان-ام کلش به توان k، منهای ۱. این احتمال این است که حداقل دو تا در یک سطل بیفتند، پس احتمال اینکه هیچ دوتایی در یک سطل نیفتند یک منهای این می‌شود.

2-(1+1/n)^k <= 1/n

2 <= (1+1/n)^k+1/n

که برای k=n که برقراره (همون e) ولی برای کمترش هم فکر نکنم بشه چون تقریبش 1+k/n می‌شود که با خود یک ان‌-ام عبارت سمت راست به ازای n=k-1 می‌شود ۲.