birthday paradox hint

(몸풀기 문제) 2 명이 1 에서 5 사이 수를 임의로 선택할 때 같은 수를 선택할  확률(p)은 얼마일까?

(방법1)

• 첫 번째 사람이 1 을 선택하고 두 번째 사람이 1 을 선택할 확률은 1/5 * 1/5
• 첫 번째 사람이 2 을 선택하고 두 번째 사람이 2 을 선택할 확률은 1/5 * 1/5
• ...
• 첫 번째 사람이 5 을 선택하고 두 번째 사람이 5 을 선택할 확률은 1/5 * 1/5

1/5*1/5 * 5 = 1/5

(방법2) 여 확률을 이용하는 방법

1 - p(두 명이 다른 숫자를 선택할 확률)

p(두 명이 다른 숫자를 선택할 확률)

• 첫 번째 사람이 1 을 두 번째 사람이 2 를 선택할 확률은 : 1/5 * 1/5 = 1/25
  이런 경우가 ₅P₂ = 20 가지가 있으므로 20 * 1/25 = 4/5
• 1 - p(두 명이 다른 숫자를 선택할 확률) = 1 - 1/5*1/5*5*4 = 1 - 1*4/5

(방법3)

p(두 명이 다른 숫자를 선택할 확률) 첫 사람이 임의의 수를 선택 한 후 두 번째 사람이 이 수를 제외한 수를 선택 할 확률

1 - 1 * 4/5

(진짜 문제) 3 명이 1 에서 5 사이 수를 임의로 선택할 때 적어도 두 명이  같은 수를 선택할  확률(p)은 얼마일까?

(방법1. 여 확률을 이용)

1 - p(모두 다른 번호를 선택할 확률)

p(모두 다른 번호를 선택할 확률)

• 첫 번째 사람이 1 , 두 번째 사람이 2 , 세 번째 사람이 3 을 선택할 확률 : 1/5*1/5*1/5
• 첫 번째 사람이 1 , 두 번째 사람이 2 , 세 번째 사람이 4 을 선택할 확률 : 1/5*1/5*1/5
• ..

이런 경우가 ₅P₃가 존재.

1/5*1/5*1/5*5*4*3 = 1 * 4/5 * 3/5

1 - 1 * 4/5 * 3/5 = 13/25

(방법2.)

첫 번째 사람이 한 수를 임의의 수를 선택했다고 하자. 두 번째 사람은 첫 번째 사람이 선택 한 수를 제외한 수를 선택하고 다음 세 번째 사람은 앞 두 사람이 선택한 수를 제외한 수를 선택할 확률

1 - 1 * 4/5 * 3/5

birthday paradox 란?

일년이 365 일 인데 23 명만 모이면 이 중 같은 생일이 있을 확률이 1/2 을 넘는다는 이상한 이야기가 생일 역설입니다. 언뜻 생각하면 뭔가 이상하지만 위에서 보듯이 맞는 애기 입니다.

이는 해싱에서 365 개의 버킷이 존재하는 경우 23 개의 키에서 충돌(collision)이 발생할 수 있는 확률이 0.5 를 넘어가는 것으로 이해할 수 있습니다.