فرایند برنولی
فرایند برنولی در آمار و احتمال فرایند برنولی یک دنباله متناهی یا نامتناهی از متغیرهای تصادفی دودویی است. این فرایند، یک فرایند تصادفی گسسته در زمان است که فقط دو مقدار را می‌گیرد (به صورت متعارف صفر و یک). متغیرهای برنولی formula_1 دارای توزیع یکسان و مستقل از هم هستند. در واقع این فرایند را می‌توان به صورت پرتاب‌های متوالی سکه تعبیر کرد که امکان دارد سکه عادل نباشد (احتمال رو آمدن و پشت آمدنش برابر نیست) اما میزان عدم توازن احتمال در طول زمان ثابت است. هر متغیر تصادفی formula_1 در این دنباله متناظر است با یک آزمایش برنولی. تمامی این پرتاب‌ها دارای توزیع برنولی هستند. بیشتر آنچه را که دربارهٔ فرایند برنولی گفته می‌شود می‌توان به آزمایشی با بیش از 2 پیشامد تعمیم داد (مانند پرتاب یک تاس شش وجهی)
فرایند برنولی دنباله‌ای متناهی یا نامتناهی از متغیرهای تصادفی مستقل formula_3 است که در آن: به بیان دیگر فرایند برنولی دنباله‌ای از آزمایش‌های برنولی مستقل با توزیع یکسان است. مستقل بودن آزمایش‌ها این مفهوم را می‌رساند که این فرایند بدون حافظه است. با فرض دانستن مقدار formula_8، رخدادهای گذشته اطلاعی از رخدادهای آینده نمی‌دهد. (به واقع ، در صورتی که formula_8 مشخص نباشد، آن را از رخدادهای گذشته بدست می آوریم)
اگر فرایند نامتناهی باشد از هر نقطه‌ای به بعد در دنباله فرایندی مشابه با فرایند اصلی را خواهیم داشت.
دو مقدار ممکن برای هر کدام ازformula_1ها به صورت معمول «موفقیت» و «شکست» نامیده می‌شود؛ بنابراین هنگام نمایش با اعداد ۰ یا ۱ پیشامد به صورت تعداد موفقیت در formula_4 امین پرتاب تعبیر می‌شود.
دو تعبیر معمول دیگر عبارتند از، «درست» و «غلط» یا «بله» و «خیر». با هر تعبیر از این دو مقدار، متغیر تصادفیformula_1 با پارامتر formula_8 نامیده می‌شود.
در بسیاری از کاربردها زمان به صورت یک شاخص formula_4 در آزمایش‌ها ظاهر می‌شود و افزایش می‌یابد. به بیان دیگر آزمایش‌هایformula_16 در زمان‌هایformula_17 رخ می‌دهد. به صورت عام هرformula_1 formula_19 در این فرایند به صورت ساده دو عضو از یک مجموعه متغیرهای تصادفی با شاخص‌های {1, 2, … , "n"} یا {۱, ۲, ۳, ...} به صورت متناهی یا نامتناهی هستند.
تعدادی متغیرهای تصادفی و توزیع‌های احتمالاتی از فرایند برنولی به صورت زیر استخراج می‌شود: فرایند برنولی را می‌توان در فرم فضای احتمالاتی به صورت یک دنباله از متغیرهای تصادفی مستقل تعبیر کرد که می‌تواند دو مقدار شیر یا خط بگیرد. فضای حالت برای یک مقدار یکتا به صورت زیر بیان می‌شود
formula_23.
به‌طور خاص، مجموعه شمارا. بررسی هر کدام از مجموعه‌های ؟
بررسی هر کدام از مجموعهٔ یک طرفه formula_24 یا دو طرفه formula_25 رایج است. یک توپولوژی طبیعی روی این فضا، product topology نام دارد. مجموعه‌ها در این توپولوژی دنباله‌های محدود از پرتاب‌های سکه هستند که همان رشته‌هایی از شیر یا خط با طول محدود هستند که مابقی دنباله به صورت حالات بی اهمیت در نظر گرفته می‌شود. این مجموعه‌ها از دنباله‌های متناهی، به مجموعه‌های استوانه ای در توپولوژِی ضرب باز می‌گردد. مجموعهٔ تمام رشته‌های این چنینی ا یک جبر سیگما، یا به‌طور خاص یک جبر بارل را می‌سازد. این جبر عموماً به صورت formula_26 نوشته می‌شود به‌طوری‌که اجزای formula_27 دنباله‌هایی با طول محدود از پرتاب سکه هستند.
اگر شانس شیر یا خط به صورت formula_28 داده شده باشد، آنگاه می‌توان یک اندازه گیر طبیعی در فضای ضربی formula_29 تعریف کرد. با فرض یک مجموعهٔ استوانه‌ای که یک دنباله خاص از نتایج پرتاب سکه‌ها formula_30 در زمان‌های formula_31است، احتمال مشاهدهٔ یک دنبالهٔ خاص به صورت زیر است:
formula_32
در رابطهٔ اخیر formula_33 تعداد دفعات مشاهدهٔ شیر در دنباله و formula_34 دفعات مشاهدهٔ خط در همان دنباله است. نوشتار گوناگونی برای تعبیر بالا وجود دارد. یک نمونهٔ رایح این‌گونه نوشته می‌شود:
formula_35
در رابطهٔ بالا formula_36 یک متغیر تصادفی دودویی است. مقدار احتمال formula_37 نامیده می‌شود.
توجه شود که احتمال هر دنباله نامتناهی خاص از پرتاب سکه‌ها صفر است، زیرا برای هر formula_38 ،formula_39 .
بنابراین یک فرایند برنولی با سه تایی احتمالاتی formula_40 تعریف می‌شود.
فرایندی را فرض کنید که در آن شیر با ۱ و خط با ۰ نشان داده می‌شود. قانون اعداد بزرگ بیان می‌کند که میانگین دنباله‌های تصادفی که به صورت :
formula_41
بیان می‌شود به امید ریاضی خود میل می‌کند. رخدادهایی که این حد را ارضا نمی‌کند احتمال صفر دارند. امید ریاضی در رخداد شیرها که فرض می‌شود با ۱ نمایش داده شده برابر است با formula_8 . برای هر متغیر تصادفی formula_36 در میان دنباله نامتناهی از آژمایش‌های برنولی که فرایند برنولی را می‌سازد رابطهٔ زیر برقرار است:
formula_50
این احتمال با نام توزیع دو جمله‌ای شناخته می‌شود.
مقدار حدی formula_51 برای یک دنباله به اندازه کافی بزرگ از پرتاب سکه‌ها، با استفاده از تقریب استرلینگ به صورت زیر است :
formula_52
با قرار دادن رابطهٔ اخیر در formula_53 توزیع نرمال بدست می‌آید. این مطلب محتوای قضیه حد مرکزی و ساده‌ترین مثال از آن است.
ترکیب قانون اعداد بزرگ و قضیه حد مرکزی به یک نتیجه جالب می انجامد.
فرایند برنولی را می‌توان به عنوان یک سیستم دینامیکی فهمید. علت این امر وجود یک تقارن طبیعی در فضای ضربی formula_25است که با عملگر شیفت داده می‌شود.
formula_55
مقدار اندازه‌گیری (measure ) نسبت به انتقال نا متغیر است .
عبارت دنباله برنولی عموماً به فهم از همان فرایند برنولی بازمی‌گردد، با این وجود این عبارت یک مفهوم کاملاً متفاوت دارد. فرض کیند یک فرایند برنولی به صورت رسمی، یک متغیر تصادفی تعریف شود. برای هر دنباله نامتناهی formula_56 از پرتاب سکه‌ها یک دنبالهٔ طبیعی به‌طور زیر تعریف می‌شود:
formula_57
این دنباله، دنباله برنولی مرتبط با فرایند برنولی می‌باشد. برای مثال اگر formula_56 یک دنباله از پرتاب سکه‌ها را نمایش دهد، آنگاه دنبالهٔ برنولی مرتبط لیست اعداد طبیعی یا نقطه‌های زمانی هست که پیشامد شیر رخ داده است.
بنابر تعریف یک دنباله برنولی formula_59، نیز زیرمجموعه تصادفی از مجموعهٔ شاخص‌ها (index) می‌باشد که همان اعداد طبیعی formula_60 است.
تقریباً تمام دنباله‌های برنولی formula_59 دنباله‌های ارگودیک هستند.
قدیمی‌ترین استخراج‌کنندهٔ تصادفی که
اگر فرایند مشاهده شده را با دنباله‌ای از صفرها و یک‌ها یا بیت‌ها نمایش دهیم، و رشتهٔ ورودی را ره صورت غیر همپوشان از زوج بیت‌های پشت سر هم نمایش دهیم، formula_62 آنگاه برای هر زوج : جدول زیر محاسبات را خلاصه می‌کند.
برای نمونه یک رشتهٔ ورودی از هشت بیت به صورت formula_63 می‌تواند به صورت formula_64 گروه بندی شود. آنگاه با توجه به جدول بالا این زوج‌ها به خروجی زیر منجر می‌شود:
formula_65
در رشتهٔ خروچی 0 و 1 به‌طور مساوی محتمل هستند همان‌طور که 01 و 10 به‌طور یکسان محتمل هستند که هر دو دارای احتمال formula_66 هستند. این استخراج از توزیع یکنواخت نیاز به آزمایش‌های ورودی مستقل از هم ندارد تنها کافیلست که ناهمبسته باشند. به‌طور کلی تر، این مکانیز برای هر دنبالهٔ جابجایی پذیر از بیت‌ها کار می‌کند:تمام چینش‌های دنباله‌ها ی متناهی دارای شانس یکسان هستند.
استخراج‌کننده فون نویمان از دوبیت ورودی برای تولید خروجی 1 یا 0 استفاده می‌کند، بنابراین طول دنباله خروجی حداقل نصف دنباله ورودی است. به‌طور میانگین محاسبات متناسب با formula_67 از زوج‌های ورودی را دور می‌ریزد.
دور ریختن رودی حداقل متناسب با formula_68 است، و این حداقل زمانی رخ می‌دهد که formula_69.
کاهش بهره وری و هدر رفتن ویژگی تصادفی در رشتهٔ ورودی با استفاده از تکرار الگوریتم قابل کاهش یافتن است. یه این وسیله خروجی را می‌توان به میزان دلخواه به باند آنتروپی نزدیک کرد. الگوریتم به صورت بازگشتی تصادفی بودن هدر رفتهٔ موجود در دو منبع ورودی را بازیافت می‌کند. به صورت سر راست، الگوریتم بر این واقعیت استوار است که به فرض مشخص بودن دنبالهٔ تولید شده، هر دو منبع هنوز دنباله‌های قابل تعویض از بیت‌ها هستند و بنابراین برای مرحلهٔ بعد الگوریتم استخراج مناسب است.
آنگاه الگوریتم بر روی هر کدام از دو رشتهٔ جدید به صورت بازگشتی اعمال می‌شود تا زمانی که ورودی خالی شود.
مثال: رشتهٔ ورودی به صورت formula_63 است که پردازش آن به صورت زیر است:
بنابر این خروجی به صورت formula_71 است، پس از هشت بیت ورودی، پنج از خروجی تولید شد این درحالی است که الگوریتم پایه تنها 3 بیت تولید می‌کرد.
http://en.wikipedia.org/w/index.php?title=Bernoulli_process&oldid=468109289