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

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

تعریف

فرایند برنولی دنباله‌ای متناهی یا نامتناهی از متغیرهای تصادفی مستقل ${\displaystyle X1,X2,X3,...}$ است که در آن:

• به ازای هر ${\displaystyle i}$ مقدار ${\displaystyle Xi}$، صفر یا یک است.
• برای تمام مقادیر ${\displaystyle i}$ احتمال اینکه ${\displaystyle Xi=1}$ برابر ${\displaystyle p}$ است.

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

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

تعبیر فرایند

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

دو تعبیر معمول دیگر عبارتند از، «درست» و «غلط» یا «بله» و «خیر». با هر تعبیر از این دو مقدار، متغیر تصادفی${\displaystyle Xi}$ _{آزمایش برنولی} با پارامتر ${\displaystyle p}$ نامیده می‌شود.

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

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

• تعداد موفقیت‌ها در n آزمایش اول که توزیع دوجمله‌ای دارد ${\displaystyle B(n,p)}$.
• تعداد آزمایش‌های مورد نیاز برای r موفقیت که توزیع توزیع دوجمله‌ای منفی دارد ${\displaystyle NB(r,p)}$.
• تعداد آزمایش‌های لازم برای حصول یک موفقیت که توزیع هندسی دارد ${\displaystyle NB(1,p)}$. این یک حالت خاص از توزیع دو جمله‌ای منفی است.

تعریف رسمی

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

${\displaystyle 2=\{H,T\}}$.

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

بررسی هر کدام از مجموعهٔ یک طرفه ${\displaystyle \Omega =2^{\mathbb {N} }=\{H,T\}^{\mathbb {N} }}$ یا دو طرفه ${\displaystyle \Omega =2^{\mathbb {Z} }}$ رایج است. یک توپولوژی طبیعی روی این فضا، product topology نام دارد. مجموعه‌ها در این توپولوژی دنباله‌های محدود از پرتاب‌های سکه هستند که همان رشته‌هایی از شیر یا خط با طول محدود هستند که مابقی دنباله به صورت حالات بی اهمیت در نظر گرفته می‌شود. این مجموعه‌ها از دنباله‌های متناهی، به مجموعه‌های استوانه ای در توپولوژِی ضرب باز می‌گردد. مجموعهٔ تمام رشته‌های این چنینی ا یک جبر سیگما، یا به‌طور خاص یک جبر بارل را می‌سازد. این جبر عموماً به صورت ${\displaystyle (\Omega ,{\mathcal {F}})}$ نوشته می‌شود به‌طوری‌که اجزای ${\displaystyle {\mathcal {F}}}$ دنباله‌هایی با طول محدود از پرتاب سکه هستند.

اگر شانس شیر یا خط به صورت ${\displaystyle \{p,1-p\}}$ داده شده باشد، آنگاه می‌توان یک اندازه گیر طبیعی در فضای ضربی ${\displaystyle P=\{p,1-p\}^{\mathbb {N} }}$ تعریف کرد. با فرض یک مجموعهٔ استوانه‌ای که یک دنباله خاص از نتایج پرتاب سکه‌ها ${\displaystyle [\omega _{1},\omega _{2},\cdots \omega _{n}]}$ در زمان‌های ${\displaystyle 1,2,\cdots ,n}$است، احتمال مشاهدهٔ یک دنبالهٔ خاص به صورت زیر است:

${\displaystyle P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{n-k}}$

در رابطهٔ اخیر ${\displaystyle k}$ تعداد دفعات مشاهدهٔ شیر در دنباله و ${\displaystyle n-k}$ دفعات مشاهدهٔ خط در همان دنباله است. نوشتار گوناگونی برای تعبیر بالا وجود دارد. یک نمونهٔ رایح این‌گونه نوشته می‌شود:

${\displaystyle P(X_{1}=\omega _{1},X_{2}=\omega _{2},\cdots ,X_{n}=\omega _{n})=p^{k}(1-p)^{n-k}}$

در رابطهٔ بالا ${\displaystyle X_{i}}$ یک متغیر تصادفی دودویی است. مقدار احتمال ${\displaystyle P}$ Bernoulli measure نامیده می‌شود.

توجه شود که احتمال هر دنباله نامتناهی خاص از پرتاب سکه‌ها صفر است، زیرا برای هر ${\displaystyle 0\leq p<1}$ ،${\displaystyle \lim _{n\to \infty }p^{n}=0}$ .

بنابراین یک فرایند برنولی با سه تایی احتمالاتی ${\displaystyle (\Omega ,{\mathcal {F}},P)}$ تعریف می‌شود.

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

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

${\displaystyle {\bar {X}}_{n}:={\frac {1}{n}}\sum _{i=1}^{n}X_{i}}$

بیان می‌شود به امید ریاضی خود میل می‌کند. رخدادهایی که این حد را ارضا نمی‌کند احتمال صفر دارند. امید ریاضی در رخداد شیرها که فرض می‌شود با ۱ نمایش داده شده برابر است با ${\displaystyle p}$ . برای هر متغیر تصادفی ${\displaystyle X_{i}}$ در میان دنباله نامتناهی از آژمایش‌های برنولی که فرایند برنولی را می‌سازد رابطهٔ زیر برقرار است:

${\displaystyle \mathbb {E} [X_{i}]=\mathbb {P} ([X_{i}=1])=p,}$

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

${\displaystyle N(k,n)={n \choose k}={\frac {n!}{k!(n-k)!}}}$

اگر احتمال رخداد شیر با ${\displaystyle p}$ مشخص شود، آنگاه احتمال کل مشاهدهٔ یک رشته به طول ${\displaystyle n}$ با ${\displaystyle k}$ بار شیر در آن به صورت زیر است :

${\displaystyle S_{n}=\sum _{i=1}^{n}X_{i}}$

${\displaystyle \mathbb {P} ([S_{n}=k])={n \choose k}p^{k}(1-p)^{n-k}}$

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

مقدار حدی ${\displaystyle S_{n}}$ برای یک دنباله به اندازه کافی بزرگ از پرتاب سکه‌ها، با استفاده از تقریب استرلینگ به صورت زیر است :

${\displaystyle n!={\sqrt {2\pi n}}\;n^{n}e^{-n}\left(1+{\mathcal {O}}\left({\frac {1}{n}}\right)\right)}$

با قرار دادن رابطهٔ اخیر در ${\displaystyle P(k,n)}$ توزیع نرمال بدست می‌آید. این مطلب محتوای قضیه حد مرکزی و ساده‌ترین مثال از آن است.

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

سیستم دینامیکی

فرایند برنولی را می‌توان به عنوان یک سیستم دینامیکی فهمید. علت این امر وجود یک تقارن طبیعی در فضای ضربی ${\displaystyle \Omega =2^{\mathbb {Z} }}$است که با عملگر شیفت داده می‌شود.

${\displaystyle TX_{i}=X_{i+1}}$

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

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

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

${\displaystyle \mathbb {Z} ^{x}=\{n\in \mathbb {Z} :X_{n}(x)=1\}\,}$

این دنباله، دنباله برنولی مرتبط با فرایند برنولی می‌باشد. برای مثال اگر ${\displaystyle x}$ یک دنباله از پرتاب سکه‌ها را نمایش دهد، آنگاه دنبالهٔ برنولی مرتبط لیست اعداد طبیعی یا نقطه‌های زمانی هست که پیشامد شیر رخ داده است.

بنابر تعریف یک دنباله برنولی ${\displaystyle \mathbb {Z} ^{x}}$، نیز زیرمجموعه تصادفی از مجموعهٔ شاخص‌ها (index) می‌باشد که همان اعداد طبیعی ${\displaystyle \mathbb {N} }$ است.

تقریباً تمام دنباله‌های برنولی ${\displaystyle \mathbb {Z} ^{x}}$ دنباله‌های ارگودیک هستند.

استخراج اعداد تصادفی

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

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

اگر فرایند مشاهده شده را با دنباله‌ای از صفرها و یک‌ها یا بیت‌ها نمایش دهیم، و رشتهٔ ورودی را ره صورت غیر همپوشان از زوج بیت‌های پشت سر هم نمایش دهیم، ${\displaystyle (11)(00)(10)...}$ آنگاه برای هر زوج :

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

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

input	output
00	discard
01	0
10	1
11	discard

برای نمونه یک رشتهٔ ورودی از هشت بیت به صورت ${\displaystyle 10011011}$ می‌تواند به صورت ${\displaystyle (10)(01)(10)(11)}$ گروه بندی شود. آنگاه با توجه به جدول بالا این زوج‌ها به خروجی زیر منجر می‌شود:

${\displaystyle (1)(0)(1)()(=101)}$

در رشتهٔ خروچی 0 و 1 به‌طور مساوی محتمل هستند همان‌طور که 01 و 10 به‌طور یکسان محتمل هستند که هر دو دارای احتمال ${\displaystyle pq=qp}$ هستند. این استخراج از توزیع یکنواخت نیاز به آزمایش‌های ورودی مستقل از هم ندارد تنها کافیلست که ناهمبسته باشند. به‌طور کلی تر، این مکانیز برای هر دنبالهٔ جابجایی پذیر از بیت‌ها کار می‌کند:تمام چینش‌های دنباله‌ها ی متناهی دارای شانس یکسان هستند.

استخراج‌کننده فون نویمان از دوبیت ورودی برای تولید خروجی 1 یا 0 استفاده می‌کند، بنابراین طول دنباله خروجی حداقل نصف دنباله ورودی است. به‌طور میانگین محاسبات متناسب با ${\displaystyle p^{2}+(1-p)^{2}}$ از زوج‌های ورودی را دور می‌ریزد.

دور ریختن رودی حداقل متناسب با ${\displaystyle 1/2}$ است، و این حداقل زمانی رخ می‌دهد که ${\displaystyle p=1/2}$.

استخراج‌کننده فون نیومن تکراری (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

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

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

مثال: رشتهٔ ورودی به صورت ${\displaystyle 10011011}$ است که پردازش آن به صورت زیر است:

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

بنابر این خروجی به صورت ${\displaystyle (101)(1)(0)()()()(=10110)}$ است، پس از هشت بیت ورودی، پنج از خروجی تولید شد این درحالی است که الگوریتم پایه تنها 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