取球涂色问题
有N个颜色各不相同的球，每次随机地从这N个球中取出两个球，然后给第一个取出的球涂上与第二个取出的球的颜色相同的颜色（整句所描述的可定义为一次操作）。
当所有的球都被涂上相同的颜色时，所需的操作数的期望是多少？
英文原题：
You have N balls with N different colors. Randomly you draw two at a time, then painting the first ball to match the second. What is the expected number of drawings before all balls are the same color?
当所有的球都被涂上相同的颜色时，所需的操作数的期望是多少？
英文原题：
You have N balls with N different colors. Randomly you draw two at a time, then painting the first ball to match the second. What is the expected number of drawings before all balls are the same color?
- 上一篇：取火柴问题
- 下一篇：只能看不能读的文字 赵元任《施氏食狮史》
回复列表
想问一下,将第二个球涂完颜色以后,两个球都要放入原来的箱子,是吗?
如果涂完后在放入盒子里那就没完没了吧？
我的答案是不放入盒子就是N/2次。
我的答案是不放入盒子就是N/2次。
肯定要放进去啊.要不怎么可能最后所有的球的颜色都一样啊.
也不会没完没了,因为每执行完一次操作,球的颜色数要么不变,要么就变为N-1,只会越来越少.
也不会没完没了,因为每执行完一次操作,球的颜色数要么不变,要么就变为N-1,只会越来越少.
如果是放进去的话，只有三个答案n-1次或者n+1次，还有一种可能就是无限次（这时，只能是自己倒霉，因为取出的球的颜色又再次涂回去了，几率很低啊）
涂完后，要放回去的，否则，只要把剩下的N-2个球随便取出来1个，继续涂成前面2个的颜色，只要N-1次就可以了。
那么这里有几个问题：
第一：有效操作（就是每次取的第一个都是与最早取出来那个球颜色相同）的几率是：
{(2/N)*{(N-2)/(N-1)}}*{(3/N)*{(N-3)/(N-1)}}*……*{{（N-1)/N}*{1/(N-1)}}=(N-1)!(N-2)!/{(N(N-1))^(N-2)}=A
第二：无效操作（就是又取了原先放进去的那2个相同颜色的球，或者后来3个甚至更多相同颜色中的2个，此种情况涂色，为无用功）的几率是：
{（2/N）*（1/（N-1））}*{(3/N)*(2/(N-1))}……*{（N/N）*((N-1)/(N-1))}=N!*(N-1)!/{(N(N-1))^(N-1)}=A
第三：反操作（就是第一次取的是不同于初始取的球的颜色，第二次取的却是初始取的球的颜色）的几率是：
（未完待续）
那么这里有几个问题：
第一：有效操作（就是每次取的第一个都是与最早取出来那个球颜色相同）的几率是：
{(2/N)*{(N-2)/(N-1)}}*{(3/N)*{(N-3)/(N-1)}}*……*{{（N-1)/N}*{1/(N-1)}}=(N-1)!(N-2)!/{(N(N-1))^(N-2)}=A
第二：无效操作（就是又取了原先放进去的那2个相同颜色的球，或者后来3个甚至更多相同颜色中的2个，此种情况涂色，为无用功）的几率是：
{（2/N）*（1/（N-1））}*{(3/N)*(2/(N-1))}……*{（N/N）*((N-1)/(N-1))}=N!*(N-1)!/{(N(N-1))^(N-1)}=A
第三：反操作（就是第一次取的是不同于初始取的球的颜色，第二次取的却是初始取的球的颜色）的几率是：
（未完待续）
