เหตุใดตัวแก้ไข von ​​Neumann จึงทำงานเฉพาะเมื่อบิตอินพุตเป็นอิสระจากกันและมีอคติเดียวกัน

เหตุใดตัวแก้ไข Von Neumann จึงทำงานเฉพาะเมื่อบิตอินพุตเป็นอิสระจากกันและมีอคติเดียวกัน ?

Von Neumann dibiaser พื้นฐานทำงานดังนี้: คุณสร้างสองบิต X, Y แล้วส่งออกบิต (หรือไม่ส่งออกบิต) ด้วยตรรกะนี้:

X=0 Y=0 -> ไม่มีเอาต์พุต
X=0 Y=1 -> เอาท์พุต a 0
X=1 Y=0 -> เอาท์พุต a 1
X=1 Y=1 -> ไม่มีเอาต์พุต

ถ้า X และ Y ไม่มีความสัมพันธ์กันและมีอคติเดียวกัน (นั่นคือ ความน่าจะเป็นที่จะเป็น 0 คือ $p$ และความน่าจะเป็นของ 1 คือ $(1-p)$) จากนั้นจะตามมาทันทีว่าความน่าจะเป็นของขั้นตอนข้างต้นที่ส่งออกเป็น 0 คือ $p(1-p)$ และความน่าจะเป็นของ 1 คือ $p(1-p)$ซึ่งเหมือนกัน (และมีความน่าจะเป็น $p^2 + (1-p)^2$ ที่ไม่ได้ส่งออกอะไรเลย - เราจะเรียกใช้อีกครั้งด้วยบิตอินพุตอีกสองบิต) นอกจากนี้ เนื่องจากเราสันนิษฐานว่าบิตอินพุตเป็นอิสระต่อกัน การเรียกใช้ดีไบเซอร์หลายครั้งบนบิตอินพุตอิสระจะสร้างเอาต์พุตอิสระ

อย่างไรก็ตาม คำถามของคุณคือ "จะเกิดอะไรขึ้นถ้าบิตไม่เป็นอิสระหรือไม่มีอคติเดียวกัน")

ในกรณีนั้น ตรรกะข้างต้นจะไม่ถือ

หากบิตมีค่าไบแอสต่างกัน นั่นคือ หากบิตแรกมีค่า 0 ที่มีความน่าจะเป็น $p$และบิตที่สองคือ 0 ด้วยความน่าจะเป็น $q \n พี$) แล้วความน่าจะเป็นของ 0 คือ $p(1-q) = p - pq$ และความน่าจะเป็นของ 1 คือ $q(1-p) = คิว - pq$อย่างที่เราคิดไว้นั่นแหละ $p \ne คิว$สิ่งเหล่านี้แตกต่างกันอย่างเห็นได้ชัด ดังนั้นเอาต์พุตของ dibiaser จึงมีความลำเอียง

หากบิตมีอคติเฉลี่ยเท่ากัน แต่มีความสัมพันธ์กัน สิ่งที่อาจเกิดขึ้นคือบิตลำดับจากตัวแยกวิเคราะห์อาจสัมพันธ์กัน ตัวอย่างเช่น ถ้า ก 01 ลำดับตามด้วยอื่น 01 ลำดับ 90% ของเวลา (และในทำนองเดียวกันสำหรับ a 10 ตามลำดับ) จากนั้นเอาต์พุตที่อยู่ติดกันจาก debiaser จะมีความสัมพันธ์กันอย่างมาก นั่นคือ dibiaser ล้มเหลวในการเปลี่ยนสตริงอินพุตดิบให้เป็นสิ่งที่ 'สุ่ม'

คำตอบก่อนหน้า (ซึ่งเพิ่งให้ตัวอย่าง):

พิจารณากรณีที่บิตอินพุตคู่คือ 0 90% ของเวลา และบิตอินพุตคี่คือ 1 90% ของเวลา

ในกรณีนั้น เอาต์พุตของคอร์เรคเตอร์ฟอน นอยมันน์จะมีความลำเอียงมากกว่าอินพุตเสียอีก

แบบฝึกหัดสำหรับคุณ: สร้างตัวอย่างที่คล้ายกันโดยที่บิตไม่เป็นอิสระจากกัน...

พอลบ่นว่าตัวอย่างของฉัน "สุดโต่งเกินไป" (ไม่ว่าจะหมายความว่าอย่างไร - ฉันคิดว่าจะใช้ตัวอย่างแย้งใดๆ ก็ได้) ไม่ว่าในกรณีใด ฉันจะตอบกลับด้วยตัวอย่างอื่นที่รุนแรงกว่านั้น

พิจารณาแหล่งที่มาที่สร้างคู่ของบิตด้วยการแจกแจงความน่าจะเป็นนี้:

• 00 กับความน่าจะเป็น 1/3
• 01 ด้วยความน่าจะเป็น 1/3
• 11 กับความน่าจะเป็น 1/3

(โดยแต่ละคู่ไม่มีความสัมพันธ์กับคู่อื่น)

การคำนวณอย่างง่ายแสดงให้เห็นว่าแต่ละคู่มีเอนโทรปีของแชนนอน $log_2(3) \ประมาณ 1.5850$ บิต (หรือประมาณ $0.7925$ เอนโทรปีบิตต่อบิต)

อย่างไรก็ตาม หากเรารันผ่านคอร์เรคเตอร์ของฟอน นอยมันน์ เราจะได้สตรีมที่มี 0 บิตของเอนโทรปี ...