ตัวแยกสัญญาณและตัวทำนายบิตถัดไปโดยไม่มีการแจกแจงแบบสม่ำเสมอ

พิจารณาการแจกแจงความน่าจะเป็น $D$ เกิน $n$ สตริงบิต แสดงว่า $U$ เพื่อเป็นเครื่องแบบกระจายทั่วกัน $n$ สตริงบิตและ $U_{n}$ เป็นการแจกแจงแบบสม่ำเสมอของจำนวนเต็ม $\{1, 2, \ldots, n\}$.

พิจารณาข้อความเทียบเท่าสองข้อความต่อไปนี้ (เทียบเท่ากับทฤษฎีบทของเหยา):

1. ไม่มีตัวทำนายบิตถัดไปของเวลาพหุนามที่เหมือนกัน $A$ ดังนั้น $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq \frac{1} {2} + \frac{1}{\text{poly}(n)} $$
2. ไม่มีตัวแยกเวลาพหุนามที่เหมือนกัน $B$ ดังนั้น $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim U}{\text{Pr}}[B(Y)=1]\ กลาง \geq \frac{1}{\text{poly}(n)} $$

ฉันกำลังคิดถึงจุดศูนย์กลางของการกระจายเครื่องแบบในการลดลง ข้อความเหล่านี้บางรูปแบบจะทำงานได้หรือไม่เมื่อเราแทนที่การแจกแจงแบบสม่ำเสมอด้วยการแจกแจงตัวอย่างที่รู้จักและมีประสิทธิภาพ $D_2$? สมมติว่าเราสามารถสุ่มตัวอย่างได้อย่างมีประสิทธิภาพจากทุกๆ ส่วนต่างของ $D_2$.

กล่าวอีกนัยหนึ่ง ให้พิจารณาถ้อยแถลงที่ 3 ดังนี้

คำชี้แจง 3: ไม่มีตัวแยกเวลาพหุนามที่เหมือนกัน $B$ ดังนั้น $$ \mid\underset{X \sim D}{\text{Pr}}[B(X)=1] - \underset{Y \sim D_2}{\text{Pr}}[B(Y)=1]\ กลาง \geq \frac{1}{\text{poly}(n)} $$

ข้อความนี้บอกเป็นนัยและ/หรือบอกเป็นนัยโดยข้อความ 4 ดังต่อไปนี้ (หรือรูปแบบอื่นของข้อความนี้) หรือไม่

คำชี้แจง 4: ไม่มีตัวทำนายบิตถัดไปของเวลาพหุนามที่เหมือนกัน $A$ ดังนั้น $$ \underset{X \sim D \ M \sim U_{n} }{\text{Pr}}[A(X_1X_2.....X_{M-1})=X_M] \geq c, $$ ที่ไหน $ค$ ขึ้นอยู่กับการกระจาย $D_2$ และข้อได้เปรียบที่แตกต่างของ $B$.

ถ้าเป็นเช่นนั้น เราขอแบบฟอร์มที่ชัดเจนสำหรับ $ค$?

คำถามที่ดี!

สิ่งนี้ดูเหมือนจะได้รับการแก้ไขในการประชุม กระดาษ นอกจากนี้ยังมี ที่นี่ โดย Schrift และ Shamir ในปี 1991:

ก.ว. Schrift, A. Shamir เกี่ยวกับความเป็นสากลของการทดสอบบิตถัดไป การประชุมเกี่ยวกับทฤษฎีและการประยุกต์ใช้การเข้ารหัส, 1990.

มีวารสารรุ่นหลังใน Journal of Cryptology เช่นกัน

โดยสรุป พวกเขาพิจารณาแหล่งที่มาของ บิตลำเอียง แต่เป็นอิสระ และวิธีการสร้างความแตกต่างให้กับมัน โปรดทราบว่าโดยไม่สูญเสียความเป็นทั่วไป พวกเขาถือว่าความน่าจะเป็นของ $1$ บิตคือ $b\ใน (1/2,1)$ แต่เรียกตามปริมาณ $ข$ อคติ ซึ่งค่อนข้างจะสวนทางกับสัญชาตญาณเมื่อเทียบกับการใช้อคติสำหรับปริมาณแบบดั้งเดิม $b-\frac{1}{2}$.

โดยเฉพาะอย่างยิ่ง พวกเขากำหนดอัตราความสำเร็จแบบถ่วงน้ำหนักของอัลกอริทึม PPTA ที่ไม่คงที่ใดๆ $$A:\{0,1\}^n\ลูกศรขวา \{0,1\}$$ ในการทำนาย $i^{th}$ แหล่งที่มาที่มีอคติเล็กน้อย

บันทึก: สัญกรณ์ $f<O(\nu(n))$ ใช้สำหรับฟังก์ชันใด ๆ ที่หายไปเร็วกว่าพหุนามใด ๆ อำนาจซึ่งกันและกันเช่นใด ๆ หายไป การทำงาน.

มีการทดสอบทางเลือกอื่น ๆ ที่เสนอในบทความ

บทความนี้ถูกอ้างถึงค่อนข้างมาก แต่ส่วนใหญ่เป็นเอกสารที่ใช้กับแหล่งข้อมูลต่างๆ ในความเป็นจริง ดูเหมือนว่าผู้เขียนคนเดียวกันนี้ได้ใช้เทคนิคนี้แล้วเพื่อพิสูจน์ผลลัพธ์ของความแข็งของทุกบิต รวมถึงบิตที่มีนัยสำคัญสูงสุดแบบไม่มีอคติสำหรับโมดูโลบันทึกแบบไม่ต่อเนื่องของจำนวนประกอบ