====== سوال ۲ ======



یک جایشگت نزولی از اعداد $1$ تا $n$ داریم. در هر گام دو عدد متمایز به صورت تصادفی انتخاب شده و به احتمال $\frac{1}{2}$ جای آن‌ها عوض می‌شود. اگر پس از چند گام این جایگشت مرتّب شود (یعنی اعداد به ترتیب صعودی در جایگشت قرار بگیرند)، علیرضا می‌برد و در غیر این صورت سپهر برنده‌ی بازی است (تعداد گام‌ها محدودیتی ندارد). به چه احتمالی علیرضا برنده می‌شود؟


  - $0$
  - $\dfrac{1}{n!}$
  - $1$
  - $\dfrac{1}{n}$
  - $\dfrac{1}{2}$




<پاسخ>
گزینه (۳) درست است.

‫به ازای یک جایگشت اولیه، یک دنباله از جابجایی‌ها که جایگشت را مرتب می‌کند در نظر بگیرید.

‫احتمال وقوع این دنباله‬ بیشتر از
$$(1/N^2 \times 1/2) ^ {(N^2)}$$
است. پس احتمال اینکه در یک $$N^2$$ متوالی این جایگشت مرتّب نشود حداکثر برابر است با
$$1 - (1/N^2 \times 1/2) ^ {(N^2)}$$
پس احتمال اینکه پس از t مرحله ی $$N^2$$ تایی از جابجایی ها مرتب نشده باشد حداکثر برابر است با:
$$(1 - (1/N^2 \times 1/2) ^ {(N^2)}) ^ t$$
که با میل کردن $t$ به بینهایت این مقدار نیز به صفر میل می‌کند. پس احتمال مرتب‌شدن جایگشت در نهایت برابر 1 است و علیرضا به احتمال 1 برنده می‌شود.

</پاسخ>
  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]