Vitcoin 복권: 기대가치 수식 도출 과정
1. 기본 설정
- $n$개의 티켓이 있습니다.
- 각 티켓 $i$는 가치 $w_i$와 앞면이 나올 확률 $p_i$ (0 < $p_i$ < 1)를 가집니다.
- 티켓을 선택하는 순서를 $\pi(1), \pi(2), ..., \pi(n)$이라고 합니다.
2. 각 단계의 기대값 도출
2.1 첫 번째 티켓 $\pi(1)$의 기대값
첫 번째 티켓은 항상 선택되므로:
$E[\pi(1)] = w_{\pi(1)}$
2.2 두 번째 티켓 $\pi(2)$의 기대값
두 번째 티켓은 첫 번째 티켓의 동전이 앞면일 때만 선택됩니다:
$E[\pi(2)] = w_{\pi(2)} \cdot P(\text{첫 번째 동전이 앞면})$
$E[\pi(2)] = w_{\pi(2)} \cdot p_{\pi(1)}$
2.3 세 번째 티켓 $\pi(3)$의 기대값
세 번째 티켓은 첫 번째와 두 번째 티켓의 동전이 모두 앞면일 때 선택됩니다:
$E[\pi(3)] = w_{\pi(3)} \cdot P(\text{첫 번째와 두 번째 동전이 모두 앞면})$
$E[\pi(3)] = w_{\pi(3)} \cdot p_{\pi(1)} \cdot p_{\pi(2)}$
2.4 일반화: $i$번째 티켓 $\pi(i)$의 기대값
$i$번째 티켓은 이전의 모든 동전이 앞면일 때 선택됩니다:
$E[\pi(i)] = w_{\pi(i)} \cdot P(\text{이전의 모든 동전이 앞면})$
$E[\pi(i)] = w_{\pi(i)} \cdot p_{\pi(1)} \cdot p_{\pi(2)} \cdot ... \cdot p_{\pi(i-1)}$
$E[\pi(i)] = w_{\pi(i)} \cdot \prod_{j=1}^{i-1} p_{\pi(j)}$
3. 총 기대값 계산
총 기대값은 각 단계의 기대값의 합입니다:
$E[\text{총 이익}] = \sum_{i=1}^n E[\pi(i)]$
$E[\text{총 이익}] = w_{\pi(1)} + w_{\pi(2)}p_{\pi(1)} + w_{\pi(3)}p_{\pi(1)}p_{\pi(2)} + ... + w_{\pi(n)}p_{\pi(1)}p_{\pi(2)}...p_{\pi(n-1)}$
이를 수학적 기호로 간단히 표현하면:
$E[\text{총 이익}] = \sum_{i=1}^n w_{\pi(i)} \cdot \prod_{j=1}^{i-1} p_{\pi(j)}$
여기서 $\prod_{j=1}^{0} p_{\pi(j)} = 1$로 정의합니다 (첫 번째 티켓의 경우).
4. 기하급수와의 관계
위 수식에서 확률의 곱 부분을 보면:
$1, p_{\pi(1)}, p_{\pi(1)}p_{\pi(2)}, p_{\pi(1)}p_{\pi(2)}p_{\pi(3)}, ...$
이는 기하수열의 형태를 띠고 있습니다. $i$번째 항을 $a_i$라고 하면:
$a_i = \prod_{j=1}^{i-1} p_{\pi(j)}$
이는 공비가 매번 변하는 일반화된 기하수열로 볼 수 있습니다.
이러한 구조 때문에, 이 문제의 해결 방법이 기하급수와 관련이 있다고 말할 수 있습니다.
Vitcoin 복권: 최적 전략 도출 과정
앞서 우리는 총 기대값을 계산했습니다. 이제 이 기대값을 최대화하는 최적의 선택 순서를 찾아야 합니다. 이를 위해 $v_i = \frac{w_i}{1-p_i}$ 공식을 유도하고, 이 값으로 티켓을 정렬하는 것이 최적 전략임을 보이겠습니다.
1. 인접한 두 티켓의 교환 고려
인접한 두 티켓 $i$와 $j$의 순서를 바꾸는 것을 고려해 봅시다. 이 교환이 총 기대값에 미치는 영향을 분석합니다.
2. 부분합 계산
$i$를 먼저 선택하고 $j$를 나중에 선택하는 경우의 부분합:
$S_1 = w_i + w_j \cdot p_i$
$j$를 먼저 선택하고 $i$를 나중에 선택하는 경우의 부분합:
$S_2 = w_j + w_i \cdot p_j$
# Vitcoin 복권: 부분합 계산 도출 과정
부분합 계산은 인접한 두 티켓의 순서를 바꿨을 때 전체 기대값에 미치는 영향을 분석하는 데 중요합니다. 여기서는 두 가지 경우의 부분합을 계산하고 그 의미를 설명하겠습니다.
## 1. 기본 설정
- 티켓 $i$의 가치: $w_i$
- 티켓 $i$의 성공 확률(앞면): $p_i$
- 티켓 $j$의 가치: $w_j$
- 티켓 $j$의 성공 확률(앞면): $p_j$
## 2. 경우 1: $i$를 먼저 선택하고 $j$를 나중에 선택하는 경우
부분합 $S_1$은 다음과 같이 계산됩니다:
$S_1 = w_i + w_j \cdot p_i$
### 도출 과정:
1. $w_i$: 티켓 $i$의 가치는 항상 얻습니다.
2. $w_j \cdot p_i$: 티켓 $j$의 가치는 티켓 $i$의 동전이 앞면일 때만 얻습니다.
- $w_j$: 티켓 $j$의 가치
- $p_i$: 티켓 $i$의 동전이 앞면일 확률
## 3. 경우 2: $j$를 먼저 선택하고 $i$를 나중에 선택하는 경우
부분합 $S_2$는 다음과 같이 계산됩니다:
$S_2 = w_j + w_i \cdot p_j$
### 도출 과정:
1. $w_j$: 티켓 $j$의 가치는 항상 얻습니다.
2. $w_i \cdot p_j$: 티켓 $i$의 가치는 티켓 $j$의 동전이 앞면일 때만 얻습니다.
- $w_i$: 티켓 $i$의 가치
- $p_j$: 티켓 $j$의 동전이 앞면일 확률
## 4. 부분합의 의미
이 부분합들은 두 티켓만을 고려했을 때의 기대값을 나타냅니다. 전체 순서에서 이 두 티켓의 상대적 위치만 바꾸고 나머지는 그대로 둔다고 가정할 때, 이 부분합들의 비교는 어떤 순서가 더 큰 기대값을 가져다주는지 판단하는 기준이 됩니다.
## 5. 최적 순서 결정
$S_1 \geq S_2$일 때, 티켓 $i$를 티켓 $j$보다 먼저 선택하는 것이 유리합니다. 이 조건은 다음 단계에서 최적의 정렬 기준을 도출하는 데 사용됩니다.
3. 최적 조건 도출
총 기대값을 최대화하기 위해서는 $S_1 \geq S_2$여야 합니다.
이를 식으로 나타내면:
$w_i + w_j \cdot p_i \geq w_j + w_i \cdot p_j$
4. 부등식 변형
위 부등식을 다음과 같이 변형할 수 있습니다:
$w_i - w_i \cdot p_j \geq w_j - w_j \cdot p_i$
$w_i(1-p_j) \geq w_j(1-p_i)$
5. 최종 비교 기준 도출
위 부등식의 양변을 $(1-p_i)(1-p_j)$로 나누면:
$\frac{w_i}{1-p_i} \geq \frac{w_j}{1-p_j}$
6. 최적 전략 정의
따라서, $v_i = \frac{w_i}{1-p_i}$로 정의하고, 이 값이 큰 순서대로 티켓을 선택하는 것이 최적의 전략입니다.
7. 직관적 해석
$v_i = \frac{w_i}{1-p_i}$의 의미:
- $w_i$: 티켓의 즉시 가치
- $1-p_i$: 실패 확률 (게임이 끝날 확률)
- $v_i$: 실패 위험 대비 기대 가치
이 전략은 "실패 위험 대비 가장 큰 가치"를 주는 티켓부터 선택하는 것입니다.
8. 결론
티켓을 $v_i = \frac{w_i}{1-p_i}$의 내림차순으로 정렬하여 선택하는 것이 총 기대값을 최대화하는 최적의 전략입니다. 이는 각 단계에서 가장 효율적인 선택을 보장하며, 전체적으로 가장 높은 기대 수익을 얻을 수 있게 해줍니다.