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.
|
|
