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

دو تا الگوریتم قدم زدن تصادفی از یک جا شروع می‌کنند، احتمال اینکه بعد از 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 می‌شود ۲.

مقدمه‌ای بر discrepency

http://www.cs.toronto.edu/~anikolov/Files/introtodisc.pdf

Geometric Probability

https://ia800708.us.archive.org/20/items/GeometricProbability/Geometric_Probability-Solomon.pdf

algorithmic Lovász local lemma

https://en.wikipedia.org/wiki/Algorithmic_Lov%C3%A1sz_local_lemma

الگوریتم تصادفی (کتاب هارپلد)

http://sarielhp.org/teach/13/b_574_rand_alg/book.pdf

الگوریتم تصادفی

https://www.ceid.upatras.gr/webpages/courses/pithmeth/

On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams

مربوط به دیاگرام ورونوی وزن‌دار است که در آن همان دیاگرام ورونوی فقط با نقاطی است که وزن هم دارند. :)
قسمت جالبش این بود که کاربردش در رشد بلور است! (یکی از کارهایی که من از بچگی بهش علاقه زیادی داشتم.)
https://en.wikipedia.org/wiki/Weighted_Voronoi_diagram
اصل مقاله:
http://arxiv.org/pdf/1401.1477.pdf
در ضمن یکشنبه هفته‌ی بعد یکی سر کلاس تصادفی ارائه‌اش می‌دهد:
http://ce.sharif.edu/courses/94-95/1/ce685-1/index.php/section/assignments/file/assignments

unique game conjecture

http://corelab.ntua.gr/courses/grad-algo/old/12-13/slides/UGC_Koiliaris.pdf

ماکسیمم متغیرهای تصادفی

http://www.math.ucsd.edu/~gptesler/283/slides/longrep_f13-handout.pdf