[계산기 사용] 카드를 섞는 가장 간단한 방법은 맨 위 카드를 뽑아 덱의 임의의 위치에 끼워 넣는 것이며, 이를 맨 위 무작위 삽입이라 하고 이것을 반복한다. 처음에 맨 아래에 있던 카드가 맨 위에 도달한 뒤 무작위로 삽입될 만큼 맨 위 무작위 삽입을 충분히 했을 때, 덱이 무작위로 섞였다고 생각하기로 한다. 덱이 장의 카드로 이루어져 있다면, 삽입되는 위치가 처음에 맨 아래에 있던 카드(이 카드를 라 하자) 아래일 확률은 이다. 따라서 가 더 이상 맨 아래에 있지 않게 되기까지 맨 위 무작위 삽입의 기댓값은 n 이다. 한 장의 카드가 아래에 있게 되면 아래에는 두 자리가 있고, 무작위로 삽입된 카드가 아래에 들어갈 확률은 이다. 이런 일이 일어나기까지 맨 위 무작위 삽입의 기댓값은 이다. 이제 아래의 두 카드는 무작위 순서로 놓여 있다. 이와 같은 방식으로 계속하여, 덱이 무작위로 섞였다고 볼 수 있기까지 필요한 맨 위 무작위 삽입 횟수의 기댓값에 대한 공식을 구하세요.
영어 원문 보기
[T] The simplest way to shuffle cards is to take the top card and insert it at a random place in the deck, called top random insertion, and then repeat. We will consider a deck to be randomly shuffled once enough top random insertions have been made that the card originally at the bottom has reached the top and then been randomly inserted. If the deck has cards, then the probability that the insertion will be below the card initially at the bottom (call this card is Thus the expected number of top random insertions before is no longer at the bottom is n. Once one card is below there are two places below and the probability that a randomly inserted card will fall below is The expected number of top random insertions before this happens is The two cards below are now in random order. Continuing this way, find a formula for the expected number of top random insertions needed to consider the deck to be randomly shuffled.
정답·풀이 보기
를 맨 위로 보내기 위한 무작위 삽입 횟수의 기댓값은 이다. 그러면 한 번 더 삽입하여 를 무작위로 다시 끼워 넣는다. 따라서 덱을 무작위로 섞기 위한 섞기 횟수의 기댓값은 이다.
원본 교재 풀이(영어)
The expected number of random insertions to get to the top is Then one more insertion puts back in at random. Thus, the expected number of shuffles to randomize the deck is
한 번 더 — 비슷한 문제OpenStax 2권 · 5.3절 · 48번우리말 번역
확률의 어떤 응용, 예를 들어 집단유전학에서 돌연변이율을 예측하는 이른바 워터슨 추정량에서는 수 를 정확하게 추정하는 것이 중요합니다. 가 감소함을 상기하세요. 를 소수 넷째 자리까지 구하세요. (힌트: .)
다 풀었으면 정답 확인