由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Quant版 - [合集] 问个概率题
相关主题
[合集] an interview question【Stats】问个经典概率题
[合集] 问个空间切割问题问个数学题
[合集] 问个数列求和[合集] 问两个概率的题目
an interview question confused me.[合集] interview questions
A probability problem[合集] Brainteaser question
问一道面试题[合集] 请教两个概率题
[合集] 问个概率题 (转载)[合集] 伦敦跟纽约比起来是不是税高,收入低,消费高,排外?
问个likelihood以及无偏估计的问题。弱问。[合集] 明天电话面试高盛, 第二页加结果
相关话题的讨论汇总
话题: balls话题: drawings话题: what话题: color话题: any
进入Quant版参与讨论
1 (共1页)
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
4
http://www.math.niu.edu/~rusin/known-math/00_incoming/walk

【在 m*******s 的大作中提到】
:
: pls give the link , thanks.

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.

1 (共1页)
进入Quant版参与讨论
相关主题
[合集] 明天电话面试高盛, 第二页加结果A probability problem
[合集] 量子力学和finance有什么关系问一道面试题
[合集] brainteaser question(math)[合集] 问个概率题 (转载)
[合集] brain test (safe sex)问个likelihood以及无偏估计的问题。弱问。
[合集] an interview question【Stats】问个经典概率题
[合集] 问个空间切割问题问个数学题
[合集] 问个数列求和[合集] 问两个概率的题目
an interview question confused me.[合集] interview questions
相关话题的讨论汇总
话题: balls话题: drawings话题: what话题: color话题: any