예상 된 동전 수

Question

앨리스와 밥 게임을합니다. Bob은 $ M= 4999 $ $ n= 4999 $ 녹색을 가지고 있습니다.카드.갑판의 카드의 각 순열은 똑같이 가능성이 있습니다.Alice는 Bob에 대한 규칙을 설정했습니다.

• 밥은 흰색 카드를 뒤집을 때마다 하나의 동전을 얻습니다. 그렇지 않으면 하나의 동전을 잃습니다.언제든지 (처음에도) 밥은 게임을 멈추고 그가 가지고있는 동전 수를 유지할 수 있습니다.
• 게임 중에 Bob이 부정적 일 수있는 동전의 균형을 연주합니다.

Bob이 최적으로 재생되면 Bob의 예상되는 양은 무엇입니까?

어떤 시체가 나에게 아이디어를 주거나 힌트를 해결하는 방법을 제공 할 수 있습니다.

Answer 1

$ w (a, b) $ $ a $ 긍정적 인 카드가있는 예상 이익이되게하십시오및 $ b $ 음의 카드.그런 다음 $ w (0,0)= 0 $ 및 $$ W (a, b)=max \ bigl (0, \ tfrac {a} {a + b} (w (a-1, b) + 1) + \ tfrac {b} {a + b} (w (A, B-1) - 1) \ BIGR). $$ 사실, 우리가 즉시 게임을 멈추면 이익은 0입니다.그렇지 않으면 $ \ tfrac {a} {a + b} $ 을 사용하여 긍정적 인 카드를 꺼내 $ \ tfrac {b} {a + b} $ , 우리는 부정적인 카드를 꺼냅니다.

이 재발을 사용하면 $ W (4999,4999) $ 을 쉽게 계산할 수 있습니다.내 랩톱에서는 두 번째 미만이 걸렸습니다.