b***k 发帖数: 2673 | 1 ☆─────────────────────────────────────☆
orion (M42) 于 (Mon Oct 29 13:50:58 2007) 提到:
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?
Here is what I found so far:
# of balls ------ E(# of drawings)
2 ------ 1
3 ------ 4
4 ------ 9
N ------ (N-1)^2 ???
Any hints or clues?
☆─────────────────────── | f******y 发帖数: 2971 | 2 I googled a better solution to this problem. Is it right?
We just analyze one color, looking at the cases where it
"wins". After any draw and replacement ( a turn,) the urn
is in a state i with i red balls. Of course, red (say) "wins"
if i = N, and "loses" if i=0. We note that the probablity
of going from i -> i+1 ( i>0>N ) is always equal to the
probability of i -> i-1, and this value is i*(N-i)/(N-1)/N.
So, we can treat this as a random walk starting from 1
with absorbtion at i=0 and i=N. Howe
【在 b***k 的大作中提到】 : ☆─────────────────────────────────────☆ : orion (M42) 于 (Mon Oct 29 13:50:58 2007) 提到: : 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? : Here is what I found so far: : # of balls ------ E(# of drawings) : 2 ------ 1 : 3 ------ 4 : 4 ------ 9
| m*******s 发帖数: 758 | 3
pls give the link , thanks.
【在 f******y 的大作中提到】 : I googled a better solution to this problem. Is it right? : We just analyze one color, looking at the cases where it : "wins". After any draw and replacement ( a turn,) the urn : is in a state i with i red balls. Of course, red (say) "wins" : if i = N, and "loses" if i=0. We note that the probablity : of going from i -> i+1 ( i>0>N ) is always equal to the : probability of i -> i-1, and this value is i*(N-i)/(N-1)/N. : So, we can treat this as a random walk starting from 1 : with absorbtion at i=0 and i=N. Howe
| f******y 发帖数: 2971 | | m*******s 发帖数: 758 | 5 After struggling for several days, I can give the general formula
Suppose the initial state is
n balls , k kinds of colors.
for i=1,...,k
there are ai number of balls with the i-th color
then , the expected steps to reach absorbing state: all n balls have the
same color
is
\sum_{i=1}^k t_{ai} ai / n
where
t_1 = (n-1)^2
t_m = t_1 - n(n-1)/m * sum_{i=2}^m (m-k+1)/(n-k+1)
simulations confirm this and analytical formula needs to solve
tri-diagonal matrix equation.
the key idea has been dem
【在 m*******s 的大作中提到】 : : pls give the link , thanks.
|
|