ไวยากรณ์ Pr[D = 1] หมายถึงอะไร

ฉันกำลังดู PDF นี้เพื่อทำความเข้าใจอาร์กิวเมนต์ไฮบริด: http://www.cs.columbia.edu/~tal/4261/F14/hybrid.pdf

สองสามบรรทัดแรกมีดังนี้:

สมมติว่าคุณมี oracles สองรายการ หรือการกระจายอินพุต $O_0,O_1$และคุณต้องการพิสูจน์ว่าพวกมันแยกกันไม่ออก เช่น. สำหรับทุกความน่าจะเป็น โพลิโนเมียล-ไทม์ (PPT) ดิฟเฟอเรเตอร์ งต้องถือสิ่งต่อไปนี้: $$ |Pr[D^{O_1} = 1] - Pr[D^{O_0} = 1]| = ละเลย $$

ฉันพยายามที่จะเข้าใจสิ่งที่ $Pr[D^{O_1} = 1]$ วิธี. ความน่าจะเป็นที่ตัวแยกความแตกต่างถูกต้องหรือไม่?

$\newcommand{\pr}{\mathbf{Pr}}$ การตีความโดยสัญชาตญาณที่เป็นไปได้อีกอย่างคือ: นี่หมายความว่า พฤติกรรม ของ $D$ ไม่เปลี่ยนแปลงอย่างรู้ทัน สมมติ $D$ เอาต์พุต 0 หรือ 1 จากนั้นพฤติกรรมเอาต์พุตของ $D$ สามารถสรุปได้โดยการแจกแจงความน่าจะเป็นของ $D$ของเอาต์พุต และนี่สามารถเขียนเป็นเวกเตอร์ได้ $(\pr[D=0], \pr[D=1])$.

พิจารณาระยะห่าง L1 ระหว่างเวกเตอร์การกระจายที่เกี่ยวกับออราเคิล $O_0, O_1$: $$|\pr[D^{O_1}=0]-\pr[D^{O_0}=0]|+|\pr[D^{O_1}=1]-\pr[D^{O_0}= 1]|.$$

เนื่องจาก $\pr[D^{O_1}=0]=1-\pr[D^{O_1}=1]$ และ $\pr[D^{O_0}=0]=1-\pr[D^{O_0}=1]$เสียบเข้ากับระยะ L1 เราจะได้ $$2|\pr[D^{O_1}=1]-\pr[D^{O_0}=1]|.$$

ดังนั้น เงื่อนไขที่กำหนดคือการแจกแจงความน่าจะเป็นของผลลัพธ์จะไม่เปลี่ยนแปลงมากนัก เมื่อมีการสับเปลี่ยน $O_0$ และ $O_1$.

สิ่งนี้สมเหตุสมผลแล้ว: ความสามารถในการแยกแยะสองสถานการณ์หมายความว่าสามารถดำเนินการแตกต่างกันไปตามสถานการณ์ที่กำหนด หากพฤติกรรมของใครบางคนไม่เคยเปลี่ยน (และไม่สามารถเปลี่ยนแปลงได้) แม้ว่าคุณจะเปลี่ยนจากอีกอันหนึ่ง หมายความว่าเขา/เธอไม่รู้จักสวิตช์นั้น

เกิดอะไรขึ้นถ้า $D$ ผลลัพธ์ไม่เพียง แต่เล็กน้อย แต่ยังมีอะไรอีกบ้าง? พูด, $D$ สามารถออกหมายเลข แม้ในกรณีที่ $D$ ทำงานแตกต่างออกไปเมื่อมีการเปลี่ยนออราเคิล ลักษณะของผลลัพธ์บางอย่างต้องเปลี่ยนไป. ตัวอย่างเช่น พูด MSB ของเอาต์พุตของ $D$ สามารถเปลี่ยนแปลงได้ ในกรณีนั้น เราอาจกำหนดความแตกต่างอื่น $D'$ ซึ่งวิ่ง $D$แล้วส่งออกเฉพาะ MSB ของ $D$ผลลัพธ์ของ ดังนั้นหากไม่มีสิ่งนั้น $D'$แล้วไม่มีสิ่งนั้น $D$. ดังนั้น ไม่มากก็น้อยโดยไม่สูญเสียลักษณะทั่วไป เราอาจพิจารณาเฉพาะตัวแยกความแตกต่างด้วยเอาต์พุตไบนารีเมื่อกำหนดความแยกไม่ออก