ค่าที่คาดหวังของคุณสมบัติการหมุน XOR เฉพาะของลำดับของบิตสตริงแบบสุ่มคืออะไร

สมมติว่า $x$ เป็นลำดับของ $l$ บิตและ $0 \le n < l$, อนุญาต $R(x, n)$ แสดงถึงผลลัพธ์ของการหมุนตามบิตซ้ายของ $x$ โดย $n$ บิตตัวอย่างเช่น ถ้า $x = 0100110001110000$, แล้ว $$\begin{อาร์เรย์}{l} R(x,0) = {\rm{0100110001110000}},\ R(x,1) = {\rm{1001100011100000}},\ R(x,2) = {\rm{0011000111000001}},\ \ldots \ R(x,15) = {\rm{0010011000111000}} \end{อาร์เรย์}$$

อนุญาต $A \oบวก B$ แสดงผลลัพธ์ของการดำเนินการ XOR สำหรับสองลำดับของ $l$ บิต ตัวอย่างเช่น, $$0100110001110000 \oบวก 1010010001000010 = 1110100000110010.$$

อนุญาต $H(x)$ หมายถึงจำนวนบิตที่ไม่ใช่ศูนย์ใน $x$ (กล่าวคือ น้ำหนักทุบ ของ $x$).

สมมติว่า $x$ และ $y$ เป็นสตริงสองบิตที่มีความยาวเท่ากัน $l$, อนุญาต $ฉ(x, y)$ หมายถึงองค์ประกอบขั้นต่ำ (จำนวนที่น้อยที่สุด) ในทูเพิล $$\begin{อาร์เรย์}{l} (ส(x \oบวก y),\ H(x \oบวก R(y,1)),\ H(x \oบวก R(y,2)),\ \ldots \ H(x \oบวก R(y,l - 1))). \end{อาร์เรย์}$$

สมมติว่าเรามี TRNG ซึ่งสร้างลำดับของบิตแบบสุ่ม สร้างลำดับของ $L = k \คูณ l$ บิต แยกลำดับนี้เป็น $k$ คำ (ดังนั้นความยาวของคำแต่ละคำคือ $l$): $w_0, w_1, \ldots, w_{k-1}$. จากนั้นคำนวณทูเพิลต่อไปนี้ $T$ จำนวน:

$$\begin{อาร์เรย์}{l} (ฉ({w_0},{w_1}),\ ฉ({w_0},{w_2}),\ \ldots \ ฉ({w_0},{w_{k - 1}}),\ ฉ({w_1},{w_2}),\ ฉ({w_1},{w_3}),\ \ldots \ ฉ({w_1},{w_{k - 1}}),\ ฉ({w_2},{w_3}),\ \ldots \ ฉ({w_{k - 2}},{w_{k - 1}})) \end{อาร์เรย์}$$

กล่าวอีกนัยหนึ่งสำหรับ ใดๆ คำคู่ $(w_i, w_j)$ ดังนั้น $i \neq j$คำนวณที่สอดคล้องกัน $f({w_i},{w_j})$.

คำถามที่ 1: ให้ $k$ และ $l$, วิธีคำนวณ ที่คาดหวัง มูลค่าของ น้อยที่สุด ตัวเลข $M_T$ ใน $T$?

คำถามที่ 2: ให้ $k$ และ $l$, วิธีคำนวณ ที่คาดหวัง มูลค่าของ เฉลี่ย ตัวเลข $A_T$ ใน $T$? นี่เบอร์ $A_T$ คำนวณได้ดังนี้: รวมองค์ประกอบทั้งหมดของ $T$แล้วหารผลรวมด้วยจำนวนองค์ประกอบทั้งหมดใน $T$.

เดอะ ที่คาดหวัง จำนวนในที่นี้หมายถึงจำนวนที่มีความน่าจะเป็นสูงสุดตัวอย่างเช่น จำนวนศูนย์บิตที่คาดหวังในลำดับของ $l$ บิตสุ่มคือ $l/2$.

เนื่องจากคุณบอกว่าสตริงอินพุตเป็นเอาต์พุตของ TRNG ฉันจะใช้แต่ละเงื่อนไขเป็นเวกเตอร์สุ่มที่กระจายอย่างสม่ำเสมอ

คุณกำหนด
$$f(x, y)=\min\{H(x \oplus y),H(x \oplus R(y,1)),\ldots,H(x \oplus R(y,\ell-1 )\} $$ ซึ่งฉันจะจำลองเป็นน้ำหนักแฮมมิ่งขั้นต่ำของชุด $k$ ไบนารีที่เลือกแบบสุ่มอย่างอิสระ $\ell-$สิ่งอันดับ

น้ำหนักแฮมมิ่งแต่ละตัวในชุดนี้มีการกระจายเป็น $\textsf{ทวินาม}(\ell,1/2).$ ดังนั้นเราจึงมี ขั้นต่ำ ของ $k$ ตัวอย่างทวินามที่เป็นกลางบน $\{0,1,\ldots,\ell\}$. ขั้นต่ำเรียกอีกอย่างว่าครั้งแรก สถิติการสั่งซื้อ และปล่อยให้ $F(u)=\mathbb{Pr}[X\leq u]$ ที่ไหน $X$ มีการแจกแจงแบบทวินามตามด้านบน (คุณใช้ $x$ เป็นตัวแปร ดังนั้นการ $u$), เรามี $$ \mathbb{Pr}[f(x,y)\leq x]=1-(1-F(u))^{k} $$

หากสมมติฐานการสุ่มเกิดขึ้น ขั้นตอนต่อไปของคุณจะพิจารณาทั้งหมด $\binom{k}{2}$ คู่ของค่าต่ำสุดเหล่านี้ ดังนั้นคุณจึงกำลังมองหาค่าต่ำสุดของคอลเล็กชันของ $$\binom{k}{2}k$$ ตัวอย่างทวินาม นี่คือ $O(k^3)$ ตัวอย่างและค่าต่ำสุดจะเป็นศูนย์ค่อนข้างเร็ว หากสมมติฐานการสุ่มด้านบนมีไว้ ดังนั้นคุณควรพิจารณา $$ 1-\left[1-(1-F(u))^k\right]^{\binom{k}{2}} $$

จากนี้คำตอบเบื้องต้นของฉันคือ:

คำถามที่ 1: ให้ $k$ และ $l$, วิธีคำนวณ ที่คาดหวัง มูลค่าของ น้อยที่สุด ตัวเลข $M_T$ ใน $T$?

ค่านี้จะใกล้เคียงกับศูนย์สำหรับขนาดใดๆ $k$ เปรียบเทียบกับ $\ell.$ คุณอาจต้องการใช้การประมาณแบบเกาส์เซียนกับทวินามและใช้ฟังก์ชันการแจกแจงแบบสะสมแบบเกาส์เพื่อประเมินค่าประมาณ

คำถามที่ 2: ให้ $k$ และ $l$, วิธีคำนวณ ที่คาดหวัง มูลค่าของ เฉลี่ย ตัวเลข $A_T$ ใน $T$? นี่เบอร์ $A_T$ มีการคำนวณดังนี้: รวมองค์ประกอบทั้งหมดของ $T$แล้วหารผลรวมด้วยจำนวนองค์ประกอบทั้งหมดใน $T$.

ตอนนี้เป็นค่าเฉลี่ยของสถิติการสั่งซื้อแต่ละรายการ แทนที่จะเป็นค่าต่ำสุดของค่าต่ำสุด มันจะเป็นไปได้มากที่จะเทียบได้กับ $$ 1-(1-F(u))^k. $$

สังเกต: หากคุณต้องการใช้การประมาณค่าโดยตรงกับทวินาม คุณสามารถดูคำตอบของฉันสำหรับการคำนวณทางคณิตศาสตร์ต่อไปนี้ คำถาม. โปรดทราบว่าสำหรับทวินาม $\textsf{ทวินาม}(\ell,1/2),$ และสำหรับใดๆ $u \in \{0,1,\ldots,\ell\}$ เรามี $$ 2^{-\ell}\sum_{j\leq u-1} \binom{\ell}{j}\leq F(u)\leq 2^{-\ell}\sum_{j\leq u} \ ทวินาม{\ell}{j} $$