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

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 می‌شود ۲.

داده‌های مناظره انتخاباتی آمریکا (۲۰۱۶)

اینها را Kaggle گذاشته ولی انقدر تهدید کرده در مورد کپی رایت که من فکر نکنم حتی اجازه داشته باشم تحلیل شده‌اش را هم بگذارم.

BIN-PACKING WITH FRAGILE OBJECTS

http://www.win.tue.nl/~nikhil/pubs/winet2.pdf

Wrong Question, Right Answer.

http://advertisementfeature.cnn.com/think-brilliant/wrong-question-right-answer.html

مقدمه‌ای بر discrepency

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

Geometric Probability

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

Lower Bounds For Algebraic Computation Trees

https://www.hni.uni-paderborn.de/fileadmin/Fachgruppen/Algorithmen/Lehre/Vorlesungsarchiv/SS2011/Concrete_Complexity_Theory/ACTs_Ben-Or.pdf

Distributed Spanner Construction in Doubling Metric Spaces ∗

http://homepage.cs.uiowa.edu/~sriram/papers/DD.Spanner.pdf