📐 پشت پرده ریاضی مسئله توقف بهینه: چرا دقیقاً ۳۷٪؟
در پست قبل دیدیم که استراتژی بهینه در مسئله منشی (Secretary Problem)، رد کردن ۳۷٪ اول گزینه‌ها و سپس انتخاب اولین مورد بهتر است.
اما این عدد جادویی از کجا آمده است؟
چرا ۵۰٪ یا ۲۵٪ نه؟
در این پست به دل ریاضیات مسئله می‌رویم و نشان می‌دهیم که چگونه عدد نپر (e) و لگاریتم طبیعی در قلب یک مسئله تصمیم‌گیری ظاهر می‌شوند.
━━━━━━━━━━━━━━
🔢 فرمول‌بندی احتمال موفقیت
فرض کنید n متقاضی داریم و تصمیم می‌گیریم r نفر اول را رد کنیم (فاز مشاهده). حالا می‌خواهیم احتمال انتخاب بهترین فرد کل مجموعه را محاسبه کنیم که آن را P(r) می‌نامیم.
بهترین فرد کل مجموعه (فرد شماره kام) تنها در صورتی انتخاب می‌شود که دو شرط همزمان برقرار باشد:
اول: k باید بزرگتر از r باشد (یعنی جزو فاز مشاهده نباشد که کورکورانه رد شده باشد).
دوم: بهترین فرد بین r+1 تا k-1، باید حتماً در آن r نفر اول بوده باشد. چرا؟ چون اگر بهترینِ قبلی‌ها در فاز مشاهده نباشد، ما پیش از رسیدن به فرد kام، شخص دیگری را استخدام کرده و بازی تمام شده است.
احتمال اینکه بهترین فردِ k-1 نفر اول، در r نفر اول باشد برابر r/(k-1) است.
احتمال اینکه بهترین فرد کل مجموعه دقیقاً در جایگاه kام باشد نیز 1/n است.
بنابراین، کل احتمال موفقیت برابر است با مجموع این احتمالات برای تمام k ها از r+1 تا n:
P(r) = Σ [ (1/n) × (r / (k-1)) ] برای k از r+1 تا n
می‌توانیم 1/n و r را از سیگما خارج کنیم:
P(r) = (r/n) × Σ [ 1 / (k-1) ] برای k از r+1 تا n
این سیگما در واقع جمع کسرهای 1/r + 1/(r+1) + ... + 1/(n-1) است.
━━━━━━━━━━━━━━
📉 تبدیل جمع به انتگرال (وقتی n → ∞)
برای حل این عبارت وقتی تعداد گزینه‌ها زیاد است، یک تغییر متغیر اعمال می‌کنیم.
فرض کنید x = r/n (نسبتی که منتظرش هستیم).
وقتی n بسیار بزرگ شود، آن جمع کسرها به انتگرال تبدیل می‌شود:
Σ [ 1/k ] ≈ ∫(1/t) dt = -ln(x)
پس تابع احتمال ما به شکل زیر ساده می‌شود:
P(x) = -x.ln(x)
━━━━━━━━━━━━━━
✨ یافتن نقطه بهینه با مشتق
برای یافتن بیشترین احتمال، باید از P(x) مشتق بگیریم و آن را برابر صفر قرار دهیم:
dP/dx = -ln(x) - 1 = 0
ln(x) = -1
x = e^(-1) = 1/e ≈ 0.3678...
اگر این مقدار x را در فرمول احتمال جایگذاری کنیم:
P(1/e) = -(1/e) × ln(1/e) = -(1/e) × (-1) = 1/e ≈ 0.3678...
نتیجه شگفت‌انگیز است: نسبت بهینه 1/e است و بیشترین احتمال موفقیت نیز دقیقاً همان 1/e است.
هرچه تعداد متقاضیان بیشتر شود (۱۰۰، ۱۰۰۰ یا یک میلیون)، این عدد ثابت می‌ماند.
━━━━━━━━━━━━━━
💡 چرا عدد e اینجا ظاهر شد؟
عدد e پایه لگاریتم طبیعی است و هر جا پای «نرخ رشد»، «جمع‌های پیوسته» یا «حدگیری دنباله‌ها» وسط باشد، سر و کله‌اش پیدا می‌شود.
در اینجا، ما داشتیم جمع گسسته‌ای از احتمالات را روی تعداد زیادی گزینه حساب می‌کردیم. وقتی این جمع به حد بی‌نهایت میل می‌کند، رفتار آن شبیه مساحت زیر منحنی 1/x می‌شود که تعریف لگاریتم طبیعی است.
به زبان ساده: ساختار مسئله (انتظار کشیدن + مقایسه نسبی) ذاتاً با لگاریتم و عدد e گره خورده است.
━━━━━━━━━━━━━━
📌 جمع‌بندی ریاضی
مسئله توقف بهینه نمونه‌ای زیبا از قدرت ریاضیات در تصمیم‌گیری است.
از یک سوال ساده شروع شد: «کی متوقف شوم؟»
به یک فرمول جمع رسید.
با حدگیری به انتگرال و لگاریتم تبدیل شد.
و با مشتق‌گیری، عدد 1/e را بیرون کشید.
این یعنی حتی در تصمیم‌های روزمره مثل استخدام یا خرید خانه، ریاضیات پنهانی وجود دارد که اگر بشناسیمش، شانس موفقیت‌مان را از ۱٪ به ۳۷٪ می‌رساند.
━━━━━━━━━━━━━━
📚 منابع:
📖 Ferguson, T.S. (1989). Who Solved the Secretary Problem? Statistical Science.
📖 Christian, B., & Griffiths, T. (2016). Algorithms to Live By: The Computer Science of Human Decisions.
📖 Lindley, D.V. (1961). Dynamic Programming and Decision Theory. Applied Statistics.
📖 Mosteller, F. (1965). Fifty Challenging Problems in Probability with Solutions. Dover.
┏━━━━━
🌐 @Amar_kadeh 📊
┗━━━━━━━━━━
در پست قبل دیدیم که استراتژی بهینه در مسئله منشی (Secretary Problem)، رد کردن ۳۷٪ اول گزینه‌ها و سپس انتخاب اولین مورد بهتر است.
اما این عدد جادویی از کجا آمده است؟
چرا ۵۰٪ یا ۲۵٪ نه؟
در این پست به دل ریاضیات مسئله می‌رویم و نشان می‌دهیم که چگونه عدد نپر (e) و لگاریتم طبیعی در قلب یک مسئله تصمیم‌گیری ظاهر می‌شوند.
━━━━━━━━━━━━━━
🔢 فرمول‌بندی احتمال موفقیت
فرض کنید n متقاضی داریم و تصمیم می‌گیریم r نفر اول را رد کنیم (فاز مشاهده). حالا می‌خواهیم احتمال انتخاب بهترین فرد کل مجموعه را محاسبه کنیم که آن را P(r) می‌نامیم.
بهترین فرد کل مجموعه (فرد شماره kام) تنها در صورتی انتخاب می‌شود که دو شرط همزمان برقرار باشد:
اول: k باید بزرگتر از r باشد (یعنی جزو فاز مشاهده نباشد که کورکورانه رد شده باشد).
دوم: بهترین فرد بین r+1 تا k-1، باید حتماً در آن r نفر اول بوده باشد. چرا؟ چون اگر بهترینِ قبلی‌ها در فاز مشاهده نباشد، ما پیش از رسیدن به فرد kام، شخص دیگری را استخدام کرده و بازی تمام شده است.
احتمال اینکه بهترین فردِ k-1 نفر اول، در r نفر اول باشد برابر r/(k-1) است.
احتمال اینکه بهترین فرد کل مجموعه دقیقاً در جایگاه kام باشد نیز 1/n است.
بنابراین، کل احتمال موفقیت برابر است با مجموع این احتمالات برای تمام k ها از r+1 تا n:
P(r) = Σ [ (1/n) × (r / (k-1)) ] برای k از r+1 تا n
می‌توانیم 1/n و r را از سیگما خارج کنیم:
P(r) = (r/n) × Σ [ 1 / (k-1) ] برای k از r+1 تا n
این سیگما در واقع جمع کسرهای 1/r + 1/(r+1) + ... + 1/(n-1) است.
━━━━━━━━━━━━━━
📉 تبدیل جمع به انتگرال (وقتی n → ∞)
برای حل این عبارت وقتی تعداد گزینه‌ها زیاد است، یک تغییر متغیر اعمال می‌کنیم.
فرض کنید x = r/n (نسبتی که منتظرش هستیم).
وقتی n بسیار بزرگ شود، آن جمع کسرها به انتگرال تبدیل می‌شود:
Σ [ 1/k ] ≈ ∫(1/t) dt = -ln(x)
پس تابع احتمال ما به شکل زیر ساده می‌شود:
P(x) = -x.ln(x)
━━━━━━━━━━━━━━
✨ یافتن نقطه بهینه با مشتق
برای یافتن بیشترین احتمال، باید از P(x) مشتق بگیریم و آن را برابر صفر قرار دهیم:
dP/dx = -ln(x) - 1 = 0
ln(x) = -1
x = e^(-1) = 1/e ≈ 0.3678...
اگر این مقدار x را در فرمول احتمال جایگذاری کنیم:
P(1/e) = -(1/e) × ln(1/e) = -(1/e) × (-1) = 1/e ≈ 0.3678...
نتیجه شگفت‌انگیز است: نسبت بهینه 1/e است و بیشترین احتمال موفقیت نیز دقیقاً همان 1/e است.
هرچه تعداد متقاضیان بیشتر شود (۱۰۰، ۱۰۰۰ یا یک میلیون)، این عدد ثابت می‌ماند.
━━━━━━━━━━━━━━
💡 چرا عدد e اینجا ظاهر شد؟
عدد e پایه لگاریتم طبیعی است و هر جا پای «نرخ رشد»، «جمع‌های پیوسته» یا «حدگیری دنباله‌ها» وسط باشد، سر و کله‌اش پیدا می‌شود.
در اینجا، ما داشتیم جمع گسسته‌ای از احتمالات را روی تعداد زیادی گزینه حساب می‌کردیم. وقتی این جمع به حد بی‌نهایت میل می‌کند، رفتار آن شبیه مساحت زیر منحنی 1/x می‌شود که تعریف لگاریتم طبیعی است.
به زبان ساده: ساختار مسئله (انتظار کشیدن + مقایسه نسبی) ذاتاً با لگاریتم و عدد e گره خورده است.
━━━━━━━━━━━━━━
📌 جمع‌بندی ریاضی
مسئله توقف بهینه نمونه‌ای زیبا از قدرت ریاضیات در تصمیم‌گیری است.
از یک سوال ساده شروع شد: «کی متوقف شوم؟»
به یک فرمول جمع رسید.
با حدگیری به انتگرال و لگاریتم تبدیل شد.
و با مشتق‌گیری، عدد 1/e را بیرون کشید.
این یعنی حتی در تصمیم‌های روزمره مثل استخدام یا خرید خانه، ریاضیات پنهانی وجود دارد که اگر بشناسیمش، شانس موفقیت‌مان را از ۱٪ به ۳۷٪ می‌رساند.
━━━━━━━━━━━━━━
📚 منابع:
📖 Ferguson, T.S. (1989). Who Solved the Secretary Problem? Statistical Science.
📖 Christian, B., & Griffiths, T. (2016). Algorithms to Live By: The Computer Science of Human Decisions.
📖 Lindley, D.V. (1961). Dynamic Programming and Decision Theory. Applied Statistics.
📖 Mosteller, F. (1965). Fifty Challenging Problems in Probability with Solutions. Dover.
┏━━━━━
🌐 @Amar_kadeh 📊
┗━━━━━━━━━━