기대치를 극대화 할 확률 그룹 학생

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$$피사체 \ 시작 {정렬} \ 합 _ {(난, J, K) T에서 \ \\ S \에서 \ {I, J, K \}} X_ {I, J, K} = 1 && \ 텍스트 {에 대한$s\in S$} \ tag2 \ end {align} 목적 함수$(1)$예상 총점입니다. 강제$(2)$ 각 학생을 정확히 하나의 그룹에 할당합니다.

소규모에 대한 수치 실험 $n$ 균일하게 분포 $p_i$그룹당 두 개의 크고 작은 확률에 대한 직감을 확인합니다. 사실, 가장 작은 확률은 가장 큰 두 개로 나타나고 다음으로 가장 작은 확률은 다음 두 개로 나타납니다. 예를 들어, 학생이 오름차순으로 레이블을 다시 지정하는 경우$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$$