문제:

There are 100 noodles in a bowl. At each step, you randomly select two noodle ends from the bowl and tie them together. What is the expectation on the number of loops formed?


솔루션이


ac5939a7001bb940a1f1c6bb11f11a39606aebf977c13d9df7




케이스 1과 2의 확률은 이해가 가는데요 recursive 한 기댓값이 헷갈려서요 

이 기댓값에 막상 값을 대입해보면


E[X_2] = 1/3 + 2/3*E[X_1] = 1/3 + 2/3 = 1 이렇게 되는거 아닌가요?

그렇기에 E[X_n] = 1이구요?? 


그리고 제일 마지막줄 합은 어떻게 근사치를 낸건가요 ㅠㅠㅠ