موضوع مقاله: فرایند برنولی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فرایند برنولی | مقدمه: فرایند برنولی در آمار و احتمال فرایند برنولی یک دنباله متناهی یا نامتناهی از متغیرهای تصادفی دودویی است. | ## بخش 1: فرایند برنولی | این فرایند، یک فرایند تصادفی گسسته در زمان است که فقط دو مقدار را می‌گیرد (به صورت متعارف صفر و یک). در واقع این فرایند را می‌توان به صورت پرتاب‌های متوالی سکه تعبیر کرد که امکان دارد سکه عادل نباشد (احتمال رو آمدن و پشت آمدنش برابر نیست) اما میزان عدم توازن احتمال در طول زمان ثابت است. بیشتر آنچه را که دربارهٔ فرایند برنولی گفته می‌شود می‌توان به آزمایشی با بیش از ۲ پیشامد تعمیم داد (مانند پرتاب یک تاس شش وجهی) تعریف فرایند برنولی دنباله‌ای متناهی یا نامتناهی از متغیرهای تصادفی مستقل است که در آن: به ازای هر مقدار ، صفر یا یک است. به بیان دیگر فرایند برنولی دنباله‌ای از آزمایش‌های برنولی مستقل با توزیع یکسان است. (به واقع، در صورتی که مشخص نباشد، آن را از رخدادهای گذشته بدست می‌آوریم) اگر فرایند نامتناهی باشد از هر نقطه‌ای به بعد در دنباله فرایندی مشابه با فرایند اصلی را خواهیم داشت. تعبیر فرایند دو مقدار ممکن برای هر کدام ازها به صورت معمول «موفقیت» و «شکست» نامیده می‌شود؛ بنابراین هنگام نمایش با اعداد ۰ یا ۱ پیشامد به صورت تعداد موفقیت در امین پرتاب تعبیر می‌شود. با هر تعبیر از این دو مقدار، متغیر تصادفی آزمایش برنولی با پارامتر نامیده می‌شود. در بسیاری از کاربردها زمان به صورت یک شاخص در آزمایش‌ها ظاهر می‌شود و افزایش می‌یابد. به صورت عام هرi و در این فرایند به صورت ساده دو عضو از یک مجموعه متغیرهای تصادفی با شاخص‌های {۱, ۲, … , n} یا {۱, ۲, ۳, ...} به صورت متناهی یا نامتناهی هستند. تعدادی متغیرهای تصادفی و توزیع‌های احتمالاتی از فرایند برنولی به صورت زیر استخراج می‌شود: تعداد موفقیت‌ها در n آزمایش اول که توزیع دوجمله‌ای دارد . تعریف رسمی فرایند برنولی را می‌توان در فرم فضای احتمالاتی به صورت یک دنباله از متغیرهای تصادفی مستقل تعبیر کرد که می‌تواند دو مقدار شیر یا خط بگیرد. مجموعه‌ها در این توپولوژی دنباله‌های محدود از پرتاب‌های سکه هستند که همان رشته‌هایی از شیر یا خط با طول محدود هستند که مابقی دنباله به صورت حالات بی‌اهمیت در نظر گرفته می‌شود. | ## بخش 2: فرایند برنولی | این مجموعه‌ها از دنباله‌های متناهی، به مجموعه‌های استوانه ای در توپولوژِی ضرب بازمی‌گردد. مجموعهٔ تمام رشته‌های این چنینی ا یک جبر سیگما، یا به‌طور خاص یک جبر بارل را می‌سازد. این جبر عموماً به صورت نوشته می‌شود به‌طوری‌که اجزای دنباله‌هایی با طول محدود از پرتاب سکه هستند. اگر شانس شیر یا خط به صورت داده شده باشد، آنگاه می‌توان یک اندازه‌گیر طبیعی در فضای ضربی تعریف کرد. با فرض یک مجموعهٔ استوانه‌ای که یک دنباله خاص از نتایج پرتاب سکه‌ها در زمان‌های است، احتمال مشاهدهٔ یک دنبالهٔ خاص به صورت زیر است: در رابطهٔ اخیر تعداد دفعات مشاهدهٔ شیر در دنباله و دفعات مشاهدهٔ خط در همان دنباله است. یک نمونهٔ رایح این‌گونه نوشته می‌شود: در رابطهٔ بالا یک متغیر تصادفی دودویی است. توجه شود که احتمال هر دنباله نامتناهی خاص از پرتاب سکه‌ها صفر است، زیرا برای هر ، . قانون اعداد بزرگ، توزیع دوجمله‌ای و قضیهٔ حد مرکزی فرایندی را فرض کنید که در آن شیر با ۱ و خط با ۰ نشان داده می‌شود. قانون اعداد بزرگ بیان می‌کند که میانگین دنباله‌های تصادفی که به صورت: بیان می‌شود به امید ریاضی خود میل می‌کند. برای هر متغیر تصادفی در میان دنباله نامتناهی از آژمایش‌های برنولی که فرایند برنولی را می‌سازد رابطهٔ زیر برقرار است: برای دانستن تعداد شیرها در یک دنباله از پرتاب سکه‌ها به تعداد n به سادگی تعداد حالات شمرده می‌شود: در پرتاب n بار یک سکه، که یک رشته به طول n را می‌سازد، تعداد k بار شیر در این پرتاب‌ها از توزیع دوجمله‌ای با ضرایب زیر بدست می‌آید: اگر احتمال رخداد شیر با مشخص شود، آنگاه احتمال کل مشاهدهٔ یک رشته به طول با بار شیر در آن به صورت زیر است: این احتمال با نام توزیع دو جمله‌ای شناخته می‌شود. مقدار حدی برای یک دنباله به اندازه کافی بزرگ از پرتاب سکه‌ها، با استفاده از تقریب استرلینگ به صورت زیر است: با قرار دادن رابطهٔ اخیر در توزیع نرمال بدست می‌آید. دنباله برنولی عبارت دنباله برنولی عموماً به فهم از همان فرایند برنولی بازمی‌گردد، با این وجود این عبارت یک مفهوم کاملاً متفاوت دارد. | ## بخش 3: فرایند برنولی | برای هر دنباله نامتناهی از پرتاب سکه‌ها یک دنبالهٔ طبیعی به‌طور زیر تعریف می‌شود: این دنباله، دنباله برنولی مرتبط با فرایند برنولی می‌باشد. برای مثال اگر یک دنباله از پرتاب سکه‌ها را نمایش دهد، آنگاه دنبالهٔ برنولی مرتبط لیست اعداد طبیعی یا نقطه‌های زمانی هست که پیشامد شیر رخ داده است. بنابر تعریف یک دنباله برنولی ، نیز زیرمجموعه تصادفی از مجموعهٔ شاخص‌ها (index) می‌باشد که همان اعداد طبیعی است. استخراج اعداد تصادفی قدیمی‌ترین استخراج‌کنندهٔ تصادفی که von Neumann extractor استخراج کنندی پایهٔ فون نویمان اگر فرایند مشاهده شده را با دنباله‌ای از صفرها و یک‌ها یا بیت‌ها نمایش دهیم، و رشتهٔ ورودی را ره صورت غیر همپوشان از زوج بیت‌های پشت سر هم نمایش دهیم، آنگاه برای هر زوج: اگر بیت‌ها یکسان بودند، دور ریخته شود اگر بیت‌ها یکسان نبودند، اولین بیت خروجی داده شود. آنگاه با توجه به جدول بالا این زوج‌ها به خروجی زیر منجر می‌شود: در رشتهٔ خروچی ۰ و ۱ به‌طور مساوی محتمل هستند همان‌طور که ۰۱ و ۱۰ به‌طور یکسان محتمل هستند که هر دو دارای احتمال هستند. این استخراج از توزیع یکنواخت نیاز به آزمایش‌های ورودی مستقل از هم ندارد تنها کافیلست که ناهمبسته باشند. به‌طور کلی تر، این مکانیز برای هر دنبالهٔ جابجایی پذیر از بیت‌ها کار می‌کند:تمام چینش‌های دنباله‌ها ی متناهی دارای شانس یکسان هستند. استخراج‌کننده فون نویمان از دوبیت ورودی برای تولید خروجی ۱ یا ۰ استفاده می‌کند، بنابراین طول دنباله خروجی حداقل نصف دنباله ورودی است. استخراج‌کننده فون نیومن تکراری (iterated) کاهش بهره‌وری و هدر رفتن ویژگی تصادفی در رشتهٔ ورودی با استفاده از تکرار الگوریتم قابل کاهش یافتن است. الگوریتم به صورت بازگشتی تصادفی بودن هدر رفتهٔ موجود در دو منبع ورودی را بازیافت می‌کند. | ## جمع‌بندی | به صورت سر راست، الگوریتم بر این واقعیت استوار است که به فرض مشخص بودن دنبالهٔ تولید شده، هر دو منبع هنوز دنباله‌های قابل تعویض از بیت‌ها هستند و بنابراین برای مرحلهٔ بعد الگوریتم استخراج مناسب است.