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

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

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

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

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

دو مقدار ممکن برای هر کدام از${\displaystyle Xi}$

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

در بسیاری از کاربردها زمان به صورت یک شاخص ${\displaystyle i}$

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

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

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

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

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

بررسی هر کدام از مجموعهٔ یک طرفه ${\displaystyle \mathrm{\Omega }=2^{\mathbb{N}}=\{H,T{\}}^{\mathbb{N}}}$

اگر شانس شیر یا خط به صورت ${\displaystyle \{p,1-p\}}$

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

در رابطهٔ اخیر ${\displaystyle 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 (\mathrm{\Omega },\mathcal{F},P)}$

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

${\displaystyle {\overline{X}}_n:=\frac{1}{n}\sum _{i=1}^n{X}_i}$

بیان می‌شود به امید ریاضی خود میل می‌کند. رخدادهایی که این حد را ارضا نمی‌کند احتمال صفر دارند. امید ریاضی در رخداد شیرها که فرض می‌شود با ۱ نمایش داده شده برابر است با ${\displaystyle p}$

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

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

${\displaystyle N(k,n)=(\genfrac{}{}{0ex}{}{n}{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])=(\genfrac{}{}{0ex}{}{n}{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 \mathrm{\Omega }=2^{\mathbb{Z}}}$

${\displaystyle T{X}_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}$

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

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

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

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

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

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

برای نمونه یک رشتهٔ ورودی از هشت بیت به صورت ${\displaystyle 10011011}$

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

در رشتهٔ خروچی 0 و 1 به‌طور مساوی محتمل هستند همان‌طور که 01 و 10 به‌طور یکسان محتمل هستند که هر دو دارای احتمال ${\displaystyle pq=qp}$

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

دور ریختن رودی حداقل متناسب با ${\displaystyle 1/2}$

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

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

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

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

مثال: رشتهٔ ورودی به صورت ${\displaystyle 10011011}$

بنابر این خروجی به صورت ${\displaystyle (101)(1)(0)()()()(=10110)}$

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