นักเรียนจัดกลุ่มความน่าจะเป็นเพื่อเพิ่มความคาดหวังสูงสุด

Aug 18 2020

ให้ $3n$ คนที่ $i^{\text{th}}$ คนสามารถผ่านการทดสอบด้วยความน่าจะเป็น $p_i$ตอนนี้คุณต้องแบ่งมันเป็น $n$ กลุ่มที่แต่ละกลุ่มมี $3$คน. คะแนนของกลุ่มหนึ่งเท่ากับ$1$ ถ้าอย่างน้อยสองคนผ่านการทดสอบ $0$มิฉะนั้น. เพื่อเพิ่มความคาดหวังของคะแนนรวมคุณจะจัดกลุ่มอย่างไร

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

คำตอบ

2 RobPratt Aug 20 2020 at 08:56

คุณสามารถแก้ปัญหาผ่านการเขียนโปรแกรมเชิงเส้นจำนวนเต็มโดยใช้สูตรการแบ่งชุดต่อไปนี้ ปล่อย$S=\{1,\dots,3n\}$ เป็นกลุ่มนักเรียนแล้วปล่อยให้ $$T=\{(i,j,k)\in S\times S\times S: i < j < k\}$$เป็นชุดนักเรียนสามเท่า สำหรับ$(i,j,k)\in T$ให้ตัวแปรการตัดสินใจไบนารี $x_{i,j,k}$ ระบุว่าสาม $(i,j,k)$ถูกกำหนดให้กับกลุ่ม ถ้า$x_{i,j,k}=1$ความน่าจะเป็นในการส่งผ่านของกลุ่มนั้นคือ \begin{align} P_{i,j,k}&:=p_i p_j p_k+(1-p_i) p_j p_k+p_i (1-p_j) p_k+p_i p_j (1-p_k)\\ &=p_i p_j + p_i p_k + p_j p_k - 2 p_i p_j p_k. \end{align} ปัญหาคือการทำให้เกิดประโยชน์สูงสุด $$\sum_{(i,j,k)\in T} P_{i,j,k} x_{i,j,k} \tag1$$ขึ้นอยู่กับ\ begin {align} \ sum _ {(i, j, k) \ in T: \\ s \ in \ {i, j, k \}} x_ {i, j, k} & = 1 && \ text {สำหรับ$s\in S$} \ tag2 \ end {align}ฟังก์ชันวัตถุประสงค์$(1)$คือคะแนนรวมที่คาดไว้ ข้อ จำกัด$(2)$ กำหนดให้นักเรียนแต่ละคนเป็นกลุ่มเดียว

การทดลองเชิงตัวเลขสำหรับขนาดเล็ก $n$ และกระจายอย่างสม่ำเสมอ $p_i$ยืนยันสัญชาตญาณของคุณเกี่ยวกับความน่าจะเป็นสองขนาดใหญ่และหนึ่งขนาดเล็กต่อกลุ่ม ในความเป็นจริงความน่าจะเป็นที่น้อยที่สุดจะปรากฏขึ้นโดยมีขนาดใหญ่ที่สุด 2 ตัวความน่าจะเป็นที่น้อยที่สุดจะปรากฏขึ้นพร้อมกับความน่าจะเป็นที่น้อยที่สุดสองค่าที่น้อยที่สุดถัดไปและความน่าจะเป็นที่น้อยที่สุดถัดไปและอื่น ๆ ตัวอย่างเช่นหากมีการระบุชื่อนักเรียนใหม่ตามลำดับที่เพิ่มขึ้น$p_i$ (โดยไม่สูญเสียลักษณะทั่วไป) จากนั้น $n=6$ ให้กลุ่ม $$\{\{1,17,18\},\{2,15,16\},\{3,13,14\},\{4,11,12\},\{5,9,10\},\{6,7,8\}\}.$$

อัปเดต : นี่คือตัวอย่างขนาดเล็กที่มี$n=2$. ใช้$p=(0,0,0.1,0.6,0.8,0.8)$. แล้วจัดกลุ่ม$\{\{1,2,3\},\{4,5,6\}\}$ ให้คะแนนที่คาดหวัง $0.832$ในขณะที่กลุ่ม $\{\{1,5,6\},\{2,3,4\}\}$ ให้คะแนนที่คาดหวังน้อยกว่า $0.7$.

OscarCunningham Oct 18 2020 at 20:07

นี่คือวิธีที่จะทำให้ปัญหาง่ายขึ้น ปล่อย$p_i = x_i + 1/2$. จากนั้นเราต้องการขยายนิพจน์ให้ใหญ่ที่สุด

\begin{align*} &\sum_{(i,j,k)\in T}p_ip_jp_k+(1-p_i)p_jp_k+p_i(1-p_j)p_k+p_ip_j(1-p_k)\\ =&\sum_{(i,j,k)\in T}\frac12+\frac12(x_i+x_j+x_k)-2x_ix_jx_k\\ =&N/2 +\frac12\sum_{i<3N}x_i-2\sum_{(i,j,k)\in T}x_ix_jx_k \end{align*}

ซึ่งคำสุดท้ายเท่านั้นที่ขึ้นอยู่กับพาร์ติชัน $T$. ดังนั้นเราจึงทำให้ปัญหาง่ายขึ้นในการค้นหาไฟล์$T$ ซึ่งจะลดผลรวมของผลิตภัณฑ์ของไฟล์ $x$s ในแต่ละกลุ่มสามคน

$$\sum_{(i,j,k)\in T}x_ix_jx_k$$