به محفل ریاضی ایرانیان خوش آمدید! لطفا برای استفاده از تمامی امکانات عضو شوید
سایت پرسش و پاسخ ریاضی
+4 امتیاز
59 بازدید
در دبیرستان و دانشگاه توسط Pouyan0x4A (32 امتیاز)

فرض کنید $n$ سکه‌ی ناسالم (biased) موجود بوده که احتمال رو شدن شیر برای هر یک برابر $p$ است. با پرتاب تمامی سکه‌ها به صورت هم‌زمان، احتمال این که تعداد شیرها بیشتر از خط‌ها باشد چقدر است؟ (یعنی بیش از نیمی از سکه‌ها، شیر را نشان دهند — می‌توانید فرض کنید که $n$ عددی فرد است)

با جستجو برای یافتن راه حل، به مسئله‌ای مشابه بر خوردم که پیرامون پرتاب یک سکه‌ی ناسالم به تعداد $n$ مرتبه است. در صورتی که یک مرتبه پرتاب $n$ سکه، هم‌ارز با با $n$ مرتبه پرتاب یک سکه باشد، پیشنهاد شده است که احتمال مطلوب را با روش زیر محاسبه کرد: $$\sum_{k=0}^{\left\lfloor\frac n2\right\rfloor}{n\choose k}p^{n-k}(1-p)^k$$ در هر صورت، این پایان مسئله نیست. اکنون فرض کنید که $m$ گروه داریم (مجدداً برای سهولت در محاسبات می‌توانید آن را عددی فرد فرض کنید) که هر یک شامل $n$ سکه از نوع بالا می‌شود. اگر اکثریت سکه‌های یک گروه شیر را نشان دهند، خروجی گروه برابر با $1$ خواهد بود. در غیر این صورت، خروجی گروه ممکن است به احتمال $q$ همچنان برابر $1$ و به احتمال $(1-q)$ برابر $0$ شود. حال اگر خود گروه‌ها نیز یک ابر-گروه با قوانینی مشابه (خروجی $1$ اگر اکثریت زیرگروه‌ها $1$ را نشان دهند؛ در غیر این صورت $1$ به احتمال $q$ و $0$ به احتمال متمم آن) تشکیل‌دهند، احتمال به دست آمدن $1$ به عنوان خروجی نهایی ابر-گروه چقدر است؟


پی‌نوشت: من این مسئله را به فرض $n=3$، $m=3$، $p=0.7$ و $q=0.1$ در کد زیر به زبان برنامه‌نویسی Python شبیه‌سازی کرده‌ام:

import random
import statistics

def weighted_random(p):
    return 1 if random.random() < p else 0

def C():
    """
    Coin flip function
    """
    return weighted_random(0.7) # p


def B(*args):
    """
    Batch voting function
    """
    majority = statistics.mode([*args])
    if majority == 0:
        return weighted_random(0.1) # q
    return 1


def test_megabatch(epochs=1_000):
    sum = 0

    for _ in range(epochs):
        c1 = C()
        c2 = C()
        c3 = C()
        c4 = C()
        c5 = C()
        c6 = C()
        c7 = C()
        c8 = C()
        c9 = C()

        b1 = B(c1, c2, c3)
        b2 = B(c4, c5, c6)
        b3 = B(c7, c8, c9)

        b = B(b1, b2, b3)

        sum +=b

    return sum

print(test_megabatch(10_000) / 10_000) # approximately 0.91

ولی لازم دارم که مسئله را حل کرده و به یک راه‌حل تعمیم‌یافته برسم.

توسط AmirHosein (14,031 امتیاز)
@Pouyan0x4A می‌توانم بپرسم که کجا به این مسأله نیاز پیدا کرده‌اید؟
توسط Pouyan0x4A (32 امتیاز)
+1
@AmirHosein نخست بگم که صحبت با شما، قربان، باعث افتخار منه! همچنین اضافه کنم که پرسش رو در Stack Exchange هم بازنویسی کردم و با کمی کمک از دوستان، پاسخش پیدا شد. به زودی ترجمه‌ی پاسخ رو همین‌جا هم بازنشر خواهم کرد که کاربران این سایت هم بتونن استفاده کنن. مسئله رو خودم طرح کردم تا کمک کنه مسئله‌ی دیگری رو حل کنم که مربوط می‌شه به علوم کامپیوتر. داخل مقاله‌ی DOI:10.1007/3-540-45014-9_1 مربوط به ensemble learning تلاش کرده از نظر آماری توضیح بده که چرا عملکرد یک ensemble عمدتاً بهتر هست تا عملکرد چند مدل مبتنی بر یادگیری ماشین به صورت جداگانه. من هم سعی داشتم همین استدلالش رو بیشتر بسط بدم تا برای انواع دیگری از ensembleها هم قابل تعمیم باشه.

1 پاسخ

+1 امتیاز
توسط Pouyan0x4A (32 امتیاز)

بالاخره به یک راه حل جامع رسیدم. معادله‌ی یادشده درست بود؛ به این معنا که یک بار پرتاب $n$ سکه با $n$بار پرتاب یک سکه، هم‌ارز است. بگذارید معادله‌ی رأی اکثریتمان را به شکل یک تابع تعریف کنیم: $$f(x, y) = \sum_{k=0}^{\left\lfloor\frac x2\right\rfloor}{x\choose k}y^{x-k}(1-y)^k$$ همچنین $r$ احتمال حصول تعداد بیشتری شیر نسبت به خط در یک گروه است: $$r = f(n,p)$$ هر گروه احتمال $r$ را برای بازگردانی $1$ در تلاش نخست دارد. اما در صورت شکست، شانس دیگری نیز با احتمال $q$ برای بازگردانی $1$ خواهد داشت. بنابراین احتمال $s$ برای بازگردانی $1$ در هر یک از تلاش‌ها از این قرار خواهد بود: $$s = p+q(1-p)$$ از آنجایی که احتمال بازگردانی $1$ از یک گروه واحد مشخص شده است، اکنون می‌توانیم خود ابرگروه را به عنوان پرتاب $m$ سکه با احتمال $s$ برای ظاهر شدن شیر در اکثریت (یا در این مورد: خروجی اکثریت زیردسته‌ها $1$ باشد) در نظر بگیریم. در این صورت، همان تابع $f$ می‌تواند به کار رود: $$t = f(m,s)$$ همچنین ابر-گروه نیز خاصیت فرصت مجدد $q$ برای بازگردانی $1$ در صورت شکست در تلاش نخست را دارد و در نتیجه $u$ به عنوان احتمال بازگردانی $1$ به عنوان خروجی نهایی به شکل زیر تعریف می‌شود: $$u = t+q(1-t) = t(1-q)+q =$$ $$f\Big(m, f(n,p)(1-q) + q\Big).(1-q) + q$$ و پیاده‌سازی آن به زبان برنامه‌نویسی Python نیز از قرار زیر است:

from math import comb

def f(x,y):
    sigma = 0
    for k in range(int((x+1)/2)):
        sigma += comb(x, k) * y**(x-k) * (1-y)**k
    return sigma

def mega_batch(n, m, p, q):
    return f(m, f(n,p)*(1-q) + q)*(1-q) + q

print(mega_batch(n=3, m=3, p=0.7, q=0.1)) # ≈ 0.9111872806912

پ.ن: این پاسخ ترجمه‌ای از پاسخی در سایت Mathematics Stack Exchange از سوی خود بنده است تا بتواند مورد استفاده‌ی کاربران گرانقدر محفل ریاضی ایرانیان نیز قرار گیرد.


حمایت مالی

کانال تلگرام محفل ریاضی
امروز : تاریخ شمسی اینجا نمایش داده می‌شود
...