교체가 적용된 임의의 임의 선택

한쪽에 1-100의 숫자가있는 카드 100 장이 있다고 가정 해 보겠습니다. 카드를 선택하고 번호를 기록한 다음 카드를 교체하고 셔플하고 반복하십시오.교체가 적용된 임의의 임의 선택

질문 # 1 : 같은 카드를 두 번이나 그려야하는 카드는 평균 몇 개나 선택해야합니까? 왜?

질문 2 : 모든 카드를 한 번 이상 가져 오려면 평균 몇 장의 카드를 선택해야합니까? 왜? 당신이 충돌 문제 섹션에서 보듯이 Birthday paradox problem

와 관련된다 :

2012-01-17 Jimmy

절대! 젠장, 나는 확률을 가르쳐 봤어 :) 단지 내 새로운 전략이 얼마나 효과적인지 알고 싶고 어디서 볼 것인지 기억하고 싶지는 않지만 효과적인 SO 응답을 좋아할 것입니다! – Jimmy

하지만 이중 개가 있다면, 이미 알아서 대답을 게시하십시오.) – Jimmy

Q2는 [쿠폰 수집가의 문제입니다] (http://en.wikipedia.org/wiki/Coupon_collector%27s_problem) – AakashM

는 Q1 (덕분에, 그것은 말하자면, 임의 음악 재생 목록과 셔플을 반복하지 않도록 옵션을 함께 할 수있다) (위키피디아 링크에서) 귀하의 질문은 정확하게 매핑됩니다. 다음 충돌 문제로

캐스트

생일 문제가 일반화 될 수있다 : 범위 이산 균일 분포로부터 그려 주어진 N 랜덤 정수 [1 D] (N 확률 P 무엇이고; d) 적어도 두 개의 숫자가 같은 것입니까? (d = 365는 일반적인 생일 문제를 나타냅니다.)

임의 카드를 선택할 수있는 범위가 [1,100]입니다. 충돌 (선택된 두 개의 카드가 동일)의 확률 (P)로 주어진다 (N, d) = ...

을 더 내려, 우리

Q와 같은 선택의 평균/예상 번호 (위한 수식을 100)이 답을줍니다.

2012-01-17 02:20:47

ack, 나에게 1/e 쓰레기라고 말하고있는거야? 나는 답이 지금 어디 있는지 알고있다. 고마워. – Jimmy

그러나 나는 그 질문에 답을 믿지 않는다. ... – Jimmy

나는 그것에 대해 생각한다. 생일은 동시에 비교되는 카드의 묶음에 관한 것이고, 나의 것은 연속적인 선택이다 (교체가있다!). 나는하지 않는다. 그것이 어느 질문 에라도 동일시 될 수 있다고 생각합니다 ... – Jimmy

답변