فرایند برنولی

از ویکی‌پدیا، دانشنامهٔ آزاد
(تغییرمسیر از فرآیند برنولی)
پرش به: ناوبری، جستجو

فرایند برنولی در آمار و احتمال فرایند برنولی یک دنباله متناهی یا نا متناهی از متغیرهای تصادفی دودویی است. این فرایند، یک فرایند تصادفی گسسته در زمان است که فقط دو مقدار را می‌گیرد (به صورت متعارف صفر و یک).متغیر های برنولی دارای توزیع یکسان و مستقل از هم هستند.در واقع این فرایند را می‌توان به صورت پرتاب‌های متوالی سکه تعبیر کرد که امکان دارد سکه عادل نباشد (احتمال رو آمدن و پشت آمدنش برابر نیست) اما میزان عدم توازن احتمال در طول زمان ثابت است. هر متغیر تصادفی در این دنباله متناظر است با یک آزمایش برنولی. تمامی این پرتاب ها دارای توزیع برنولی هستند. بیشتر آنچه را که درباره ی فرایند برنولی گفته می شود می توان به آزمایشی با بیش از 2 پیشامد تعمیم داد (مانند پرتاب یک تاس شش وجهی)

تعریف[ویرایش]

فرایند برنولی دنباله‌ای متناهی یا نا متناهی از متغیرهای تصادفی مستقل است که در آن:

  • به ازای هر مقدار ، صفر یا یک است
  • برای تمام مقادیر احتمال اینکه برابر است

به بیان دیگر فرایند برنولی دنباله‌ای از آزمایش‌های برنولی مستقل با توزیع یکسان است. مستقل بودن آزمایش‌ها این مفهوم را می‌رساند که این فرایند بدون حافظه است.با فرض دانستن مقدار ، رخداد های گذشته اطلاعی از رخداد های آینده نمی دهد. (به واقع ، در صورتی که مشخص نباشد ، آن را از رخداد های گذشته بدست می آوریم)

اگر فرایند نامتناهی باشد از هر نقطه‌ای به بعد در دنباله فرآیندی مشابه با فرایند اصلی را خواهیم داشت.

تعبیر فرایند[ویرایش]

دو مقدار ممکن برای هر کدام از ها به صورت معمول «موفقیت» و «شکست» نامیده می‌شود؛ بنابراین هنگام نمایش با اعداد ۰ یا ۱ پیشامد به صورت تعداد موفقیت در امین پرتاب تعبیر می‌شود.

دو تعبیر معمول دیگر عبارتند از، «درست» و «غلط» یا «بله» و «خیر». با هر تعبیر از این دو مقدار ، متغیر تصادفی آزمایش برنولی با پارامتر نامیده می‌شود.

در بسیاری از کاربردها زمان به صورت یک شاخص در آزمایش‌ها ظاهر می‌شود و افزایش می‌یابد. به بیان دیگر آزمایش‌های در زمان‌های رخ می‌دهد. به صورت عام هرi و در این فرایند به صورت ساده دو عضو از یک مجموعه متغیرهای تصادفی با شاخص‌های {1, 2, … , n} یا {۱, ۲, ۳, ...} به صورت متناهی یا نامتناهی هستند.

تعدادی متغیرهای تصادفی و توزیع‌های احتمالاتی از فرایند برنولی به صورت زیر استخراج می‌شود:

  • تعداد موفقیت‌ها در n آزمایش اول که توزیع دوجمله‌ای دارد .
  • تعداد آزمایش‌های مورد نیاز برای r موفقیت که توزیع توزیع دوجمله‌ای منفی دارد .
  • تعداد آزمایش‌های لازم برای حصول یک موفقیت که توزیع هندسی دارد .این یک حالت خاص از توزیع دو جمله ای منفی است.

تعریف رسمی[ویرایش]

فرایند برنولی را می‌توان در فرم فضای احتمالاتی به صورت یک دنباله از متغیرهای تصادفی مستقل تعبیر کرد که می تواند دو مقدار شیر یا خط بگیرد. فضای حالت برای یک مقدار یکتا به صورت زیر بیان می‌شود

.

به طور خاص، مجموعه شمارا. بررسی هر کدام از مجموعه‌های ؟

بررسی هر کدام از مجموعه ی یک طرفه یا دو طرفه رایج است. یک توپولوژی طبیعی روی این فضا، product topology نام دارد. مجموعه‌ها در این توپولوژی دنباله‌های محدود از پرتاب‌های سکه هستند که همان رشته‌هایی از شیر یا خط با طول محدود هستند که مابقی دنباله به صورت حالات بی اهمیت در نظر گرفته می شود. این مجموعه ها از دنباله های متناهی ، به مجموعه های استوانه ای در توپولوژِی ضرب باز می گردد. مجموعه ی تمام رشته های این چنینی ا یک جبر سیگما ، یا به طور خاص یک جبر بارل را می سازد. این جبر عموما به صورت نوشته می شود به طوری که اجزای دنباله هایی با طول محدود از پرتاب سکه هستند.

اگر شانس شیر یا خط به صورت داده شده باشد ، آنگاه می توان یک اندازه گیر طبیعی در فضای ضربی تعریف کرد.با فرض یک مجموعه ی استوانه ای که یک دنباله خاص از نتایج پرتاب سکه ها در زمان های است ، احتمال مشاهده ی یک دنباله ی خاص به صورت زیر است:

در رابطه ی اخیر تعداد دفعات مشاهده ی شیر در دنباله و دفعات مشاهده ی خط در همان دنباله است.نوشتار گوناگونی برای تعبیر بالا وجود دارد. یک نمونه ی رایح اینگونه نوشته می شود:

در رابطه ی بالا یک متغیر تصادفی دودویی است. مقدار احتمال Bernoulli measure نامیده می شود.

توجه شود که احتمال هر دنباله نا متناهی خاص از پرتاب سکه ها صفر است ، زیرا برای هر ، .

بنابراین یک فرایند برنولی با سه تایی احتمالاتی تعریف می شود.

قانون اعداد بزرگ، توزیع دوجمله‌ای و قضیهٔ حد مرکزی[ویرایش]

فرایندی را فرض کنید که در آن شیر با ۱ و خط با ۰ نشان داده می‌شود. قانون اعداد بزرگ بیان می‌کند که میانگین دنباله‌های تصادفی که به صورت :

بیان می‌شود به امید ریاضی خود میل می‌کند.رخداد هایی که این حد را ارضا نمی کند احتمال صفر دارند. امید ریاضی در رخداد شیرها که فرض می‌شود با ۱ نمایش داده شده برابر است با . برای هر متغیر تصادفی در میان دنباله نا متناهی از آژمایش های برنولی که فرایند برنولی را می سازد رابطه ی زیر برقرار است:

برای دانستن تعداد شیرها در یک دنباله از پرتاب سکه‌ها به تعداد n به سادگی تعداد حالات شمرده می شود : در پرتاب n بار یک سکه، که یک رشته به طول n را می‌سازد، تعداد k بار شیر در این پرتاب‌ها از توزیع دوجمله‌ای با ضرایب زیر بدست می‌آید:
اگر احتمال رخداد شیر با مشخص شود، آنگاه احتمال کل مشاهدهٔ یک رشته به طول با بار شیر در آن به صورت زیر است :

این احتمال با نام توزیع دو جمله‌ای شناخته می‌شود.

مقدار حدی برای یک دنباله به اندازه کافی بزرگ از پرتاب سکه ها ، با استفاده از تقریب استرلینگ به صورت زیر است :

با قرار دادن رابطه ی اخیر در توزیع نرمال بدست می آید. این مطلب محتوای قضیه حد مرکزی و ساده ترین مثال از آن است.

ترکیب قانون اعداد بزرگ و قضیه حد مرکزی به یک نتیجه جالب asymptotic equipartition property می انجامد.

سیستم‌ دینامیکی[ویرایش]

فرایند برنولی را می‌توان به عنوان یک سیستم دینامیکی فهمید. علت این امر وجود یک تقارن طبیعی در فضای ضربی است که با عملگر شیفت داده می‌شود.

مقدار اندازه گیری (measure ) نسبت به انتقال نا متغیر است .

دنباله برنولی[ویرایش]

عبارت دنباله برنولی عموماً به فهم از همان فرایند برنولی بازمی‌گردد، با این وجود این عبارت یک مفهوم کاملاً متفاوت دارد. فرض کیند یک فرایند برنولی به صورت رسمی ، یک متغیر تصادفی تعریف شود. برای هر دنباله نامتناهی از پرتاب سکه ها یک دنباله ی طبیعی به طور زیر تعریف می شود:

این دنباله ، دنباله برنولی مرتبط با فرایند برنولی می باشد.برای مثال اگر یک دنباله از پرتاب سکه ها را نمایش دهد ، آنگاه دنباله ی برنولی مرتبط لیست اعداد طبیعی یا نقطه های زمانی هست که پیشامد شیر رخ داده است.

بنابر تعریف یک دنباله برنولی ، نیز زیرمجموعه تصادفی از مجموعه ی شاخص ها (index) می باشد که همان اعداد طبیعی است.

تقریبا تمام دنباله های برنولی دنباله های ارگودیک هستند.

استخراج اعداد تصادفی[ویرایش]

قدیمی ترین استخراج کننده ی تصادفی که von Neumann extractor

استخراج کنندی پایه ی فون نویمان[ویرایش]

اگر فرایند مشاهده شده را با دنباله ای از صفر ها و یک ها یا بیت ها نمایش دهیم ، و رشته ی ورودی را ره صورت غیر همپوشان از زوج بیت های پشت سر هم نمایش دهیم ، آنگاه برای هر زوج :

  • اگر بیت ها یکسان بودند ، دور ریخته شود
  • اگر بیت ها یکسان نبودند ، اولین بیت خروجی داده شود.

جدول زیر محاسبات را خلاصه می کند.

input output
00 discard
01 0
10 1
11 discard

برای نمونه یک رشته ی ورودی از هشت بیت به صورت می تواند به صورت گروه بندی شود. آنگاه با توجه به جدول بالا این زوج ها به خروجی زیر منجر می شود:

در رشته ی خروچی 0 و 1 به طور مساوی محتمل هستند همان طور که 01 و 10 به طور یکسان محتمل هستند که هر دو دارای احتمال هستند. این استخراج از توزیع یکنواخت نیاز به آزمایش های ورودی مستقل از هم ندارد تنها کافیلست که ناهمبسته باشند. به طور کلی تر ، این مکانیز برای هر دنباله ی جابجایی پذیر از بیت ها کار می کند:تمام چینش های دنباله ها ی متناهی دارای شانس یکسان هستند.

استخراج کننده فون نویمان از دوبیت ورودی برای تولید خروجی 1 یا 0 استفاده می کند،بنابراین طول دنباله خروجی حداقل نصف دنباله ورودی است. به طور میانگین محاسبات متناسب با از زوج های ورودی را دور می ریزد.

دور ریختن رودی حداقل متناسب با است، واین حداقل زمانی رخ می دهد که .

استخراج کننده فون نیومن تکراری (iterated)[ویرایش]

کاهش بهره وری و هدر رفتن ویژگی تصادفی در رشته ی ورودی با استفاده از تکرار الگوریتم قابل کاهش یافتن است. یه این وسیله خروجی را میتوان به میزان دلخواه به باند آنتروپی نزدیک کرد.الگوریتم به صورت بازگشتی تصادفی بودن هدر رفته ی موجود در دو منبع ورودی را بازیافت می کند. به صورت سر راست ، الگوریتم بر این واقعیت استوار است که به فرض مشخص بودن دنباله ی تولید شده ، هر دو منبع هنوز دنباله های قابل تعویض از بیت ها هستند و بنابر این برای مرحله ی بعد الگوریتم استخراج مناسب است.

input output new sequence 1 new sequence 2
00 none 0 0
01 0 1 none
10 1 1 none
11 none 0 1

(در صورتی که طول داده ی ورودی فرد باشد ، آخرین بیت دور ریخته می شود)

آنگاه الگوریتم بر روی هر کدام از دو رشته ی جدید به صورت بازگشتی اعمال می شود تا زمانی که ورودی خالی شود.

مثال: رشته ی ورودی به صورت است که پردازش آن به صورت زیر است:

step number input output new sequence 1 new sequence 2
0 (10)(01)(10)(11) (1)(0)(1)() (1)(1)(1)(0) ()()()(1)
1 (11)(10) ()(1) (0)(1) (1)()
1.1 (01) (0) (1) ()
1.1.1 1 none none none
1.2 1 none none none
2 1 none none none

بنابر این خروجی به صورت است، پس از هشت بیت ورودی ، پنج از خروجی تولید شد این درحالی است که الگوریتم پایه تنها 3 بیت تولید می کرد.

منابع[ویرایش]

http://en.wikipedia.org/w/index.php?title=Bernoulli_process&oldid=468109289

مطالعهٔ بیشتر[ویرایش]

  • Carl W. Helstrom, Probability and Stochastic Processes for Engineers, (1984) Macmillan Publishing Company, New York ISBN 0-02-353560-1.
  • Dimitri P. Bertsekas and John N. Tsitsiklis, Introduction to Probability, (2002) Athena Scientific, Massachusetts ISBN 1-886529-40-X