K*V
发帖数: 192 | 1 This was one question in a pre-interview test. I got about 95% of the way to
an analytic solution.
Flip an unfair coin N = 10 times. p(heads) = 0.6. (p is irrelevant for the 5
%.) You might get:
HHHTHTHHTH
Define a group as consecutive flips leading to the same side. (HHH)(T)(H)(T)
(HH)(T)(H) has N_group = 7.
What is the probability that N_group >= 6? What is the probability that N_
group >= 55 given N = 100? | k*****n
发帖数: 117 | 2 since each toss is independent
let Xi = 0 if ith toss and (i+1)-th toss is same
Xi = 1 if they are different
then X1, X2, ... XN-1 are mutually indep
total number of groups = sum(X1..XN-1) + 1
E[ ] = E[ ] + ... E[ ] + 1 =
sum(...) is a binomial
Now you can carry out the calculation yourself | f****g
发帖数: 207 | 3 Define a group as consecutive flips leading to the same side. (HHH)(T)(H)(T)
(HH)(T)(H) has N_group = 7.
unclear question, not understanding this part.
How is 7 obtained? | K*V
发帖数: 192 | 4 这是求平均group有多少吧？问的是group数大于6的概率？
【在 k*****n 的大作中提到】
: since each toss is independent
: let Xi = 0 if ith toss and (i+1)-th toss is same
: Xi = 1 if they are different
: then X1, X2, ... XN-1 are mutually indep
: total number of groups = sum(X1..XN-1) + 1
: E[ ] = E[ ] + ... E[ ] + 1 =
: sum(...) is a binomial
: Now you can carry out the calculation yourself
| k*****n
发帖数: 117 | 5 just use binomial CDF
【在 K*V 的大作中提到】
: 这是求平均group有多少吧？问的是group数大于6的概率？
| K*V
发帖数: 192 | 6 而且这是个unfair coin
probability of ith toss and (i+1)-th toss is same could be p or 1-p
depending on ith toss.
这怎么用Binomial....
【在 k*****n 的大作中提到】
: just use binomial CDF
| k*****n
发帖数: 117 | 7 given ith toss same as i+1th (Xi=0)
Xi+1 = 0 with prob ...
Xi+1 = 1 with prob ...
given ith diff same as i+1th (Xi=1)
Xi+1 = 0 with prob ...
Xi+1 = 1 with prob ...
thus Xi and Xi+1 are i.i.d Bernoulli r.v.
yes?
Then sum of them is Binomial
【在 K*V 的大作中提到】
: 而且这是个unfair coin
: probability of ith toss and (i+1)-th toss is same could be p or 1-p
: depending on ith toss.
: 这怎么用Binomial....
| K*V
发帖数: 192 | 8 明白了！
真是高手阿！
【在 k*****n 的大作中提到】
: given ith toss same as i+1th (Xi=0)
: Xi+1 = 0 with prob ...
: Xi+1 = 1 with prob ...
: given ith diff same as i+1th (Xi=1)
: Xi+1 = 0 with prob ...
: Xi+1 = 1 with prob ...
: thus Xi and Xi+1 are i.i.d Bernoulli r.v.
: yes?
: Then sum of them is Binomial
| c**e
发帖数: 4439 | 9 好像不独立吧？帮看看我哪错了？
比如看p(x1=0)=p*p+(1-p)*(1-P);
条件概率p(x2=0/x1=0)=P(x1=0,x2=0)/p(x1=0)=(p^3+(1-P)^3)/(p^2+(1-p)^2)
有全概率公式p(x2=0)=p(x2=0/x1=0)*p(x1=0)+P(x2=0/x1=1)*p(x1=1)=p(x1=0)同分布
但是p(x2=0/x1=0)!=p(x2=0) 不独立啊？ | r****y
发帖数: 1 | 10 Could you please explain
why X1, X2, ... Xn-1 independent if p!=0.5?
【在 k*****n 的大作中提到】
: since each toss is independent
: let Xi = 0 if ith toss and (i+1)-th toss is same
: Xi = 1 if they are different
: then X1, X2, ... XN-1 are mutually indep
: total number of groups = sum(X1..XN-1) + 1
: E[ ] = E[ ] + ... E[ ] + 1 =
: sum(...) is a binomial
: Now you can carry out the calculation yourself
| | | m*******7
发帖数: 10 | | m******l
发帖数: 97 | | j******i
发帖数: 244 | 13 Doesn't look right.
Xi=0 => toss_i has p^2/(p^2+q^2): q^2/(p^2+q^2) head to tail odds,
Xi=1 => toss_i has 1: 1 head to tail odds.
in this case p=0.6, so toss_i will be biased toward head when Xi=0.
【在 k*****n 的大作中提到】
: given ith toss same as i+1th (Xi=0)
: Xi+1 = 0 with prob ...
: Xi+1 = 1 with prob ...
: given ith diff same as i+1th (Xi=1)
: Xi+1 = 0 with prob ...
: Xi+1 = 1 with prob ...
: thus Xi and Xi+1 are i.i.d Bernoulli r.v.
: yes?
: Then sum of them is Binomial
| T********g
发帖数: 42 | 14 刚想说这题貌似不难，结果看楼上好几位已经给出答案了。版上还是卧虎藏龙啊！ | b********a
发帖数: 300 | 15 试试扔三次3个group的概率就知道楼上的解法不对 | g******2
发帖数: 234 | 16 The following R code should give you the right probability for P(N_group = k
| n flips).
prob <- function(k, n) {
if (k > 1) {
if (k%%2 == 0) {
nums <- (k/2) : (n-k/2)
p <- sum(sapply(nums, function(x)
choose(2,1)*choose(max(x,n-x)-1, k/2-1) *
choose(min(x,n-x)-1, k/2-1) * 0.6^(n-x) *0.4^x))
return(p)
} else {
nums <- floor(k/2) : ceiling(n-k/2)
p <- sum(sapply(nums, function(x)
choose(max(x,n-x)-1, floor(k/2)) *
choose(min(x,n-x)-1, floor(k/2)-1) * 0.6^(n-x) *0.4^x)) +
sum(sapply(nums[2:(length(nums)-1)], function(x)
choose(max(x,n-x)-1, floor(k/2)-1) *
choose(min(x,n-x)-1, floor(k/2)) * 0.6^(n-x) *0.4^x))
p
}
} else {
0.6^n + 0.4^n
}
} | q***a
发帖数: 26 | 17 my 2 cents
separately consider two initial situations a0=0 and a0=1;
only consider a0=0 here since a0=1 is similar.
There are N_group-1 switchs, if N_group is odd, (N_group-1)/2 0->1 and equal
number 1->0. if N_group is even,, (N_group+1)/2 0->1 and others 1->0
you easily get possibility of each single result that meet above condition.
then consider number of such results.
the rest of coins (N-N_group) need to fill into corresponding interval which
should be leaded with the same side, and any interval can be empty. and
each coin can be either head or tail. for number each division between head
and tail, say n_head + n_tail = N - N_group. then you can sum up for each
division of coin number with the weight of possibility of that number of
heads and tails.
to
5
T)
【在 K*V 的大作中提到】
: This was one question in a pre-interview test. I got about 95% of the way to
: an analytic solution.
: Flip an unfair coin N = 10 times. p(heads) = 0.6. (p is irrelevant for the 5
: %.) You might get:
: HHHTHTHHTH
: Define a group as consecutive flips leading to the same side. (HHH)(T)(H)(T)
: (HH)(T)(H) has N_group = 7.
: What is the probability that N_group >= 6? What is the probability that N_
: group >= 55 given N = 100?
| m**********t
发帖数: 39 | | m**********t
发帖数: 39 | 19 I like R so I checked your R code.
could you double check your R code? using k=n=10,
> prob <- function(k, n) {
+ if (k > 1) {
+ if (k%%2 == 0) {
+ nums <- (k/2) : (n-k/2)
+ p <- sum(sapply(nums, function(x)
+ choose(2,1)*choose(max(x,n-x)-1, k/2-1) *
+ choose(min(x,n-x)-1, k/2-1) * 0.6^(n-x) *0.4^x))
+ return(p)
+ } else {
+ nums <- floor(k/2) : ceiling(n-k/2)
+ p <- sum(sapply(nums, function(x)
+ choose(max(x,n-x)-1, floor(k/2)) *
+ choose(min(x,n-x)-1, floor(k/2)-1) * 0.6^(n-x) *0.4^x)) +
+ sum(sapply(nums[2:(length(nums)-1)], function(x)
+ choose(max(x,n-x)-1, floor(k/2)-1) *
+ choose(min(x,n-x)-1, floor(k/2)) * 0.6^(n-x) *0.4^x))
+ p
+ }
+ } else {
+ 0.6^n + 0.4^n
+ }
+ }
>
> a<-prob(10,10)
> a
[1] 0.001592525
however 0.6^10=0.006047.
did I miss something?
k
【在 g******2 的大作中提到】
: The following R code should give you the right probability for P(N_group = k
: | n flips).
: prob <- function(k, n) {
: if (k > 1) {
: if (k%%2 == 0) {
: nums <- (k/2) : (n-k/2)
: p <- sum(sapply(nums, function(x)
: choose(2,1)*choose(max(x,n-x)-1, k/2-1) *
: choose(min(x,n-x)-1, k/2-1) * 0.6^(n-x) *0.4^x))
: return(p)
| g******2
发帖数: 234 | 20 k=10, n=10 means you have 5 head, 5 tails intermingled -> two patterns
HTHTHTHTHT, or THTHTHTHTH
so the probability is 0.6^5*0.4^5*2=0.001592525
what you calculated is the probability of 10 heads, which is one of the
cases for k=1. | m**********t
发帖数: 39 | 21 Thanks, got it. your codes are very cool. like it.
the question itself is confusing...
【在 g******2 的大作中提到】
: k=10, n=10 means you have 5 head, 5 tails intermingled -> two patterns
: HTHTHTHTHT, or THTHTHTHTH
: so the probability is 0.6^5*0.4^5*2=0.001592525
: what you calculated is the probability of 10 heads, which is one of the
: cases for k=1.
| x*******o
发帖数: 1 | 22 不独立的，每个位置出现head和tail的概率不一样，所以不identical，只会用递推了
。。。 Pr_end_q(n,k) means the sequence ends with q, its length is n and its
group number is k.
Pr_end_q(n,k) = Pr_end_q(n-1,k)*q + Pr_end_p(n-1,k-1)*q; (1)
Pr_end_p(n,k) = Pr_end_p(n-1,k)*p + Pr_end_q(n-1,k-1)*p; (2)
boundary condition
Pr_end_q(n,1) = q^n;
Pr_end_p(n,1) = p^n;
Pr_end_p(0,0) = Pr_end_q(0,0)=1;
Pr_end_p(n,k) = 0 when n
然后就能做了。。可以对(1) 处理得到
Pr_end_q(n,k)/q^n = (q/p)^(floor(k/2)) + [sum(Pr_end_p(i,k-1)/q^i) for i
from k to
n-1]
(2)式子同样处理 然后塞进上边的式子，就能得到Pr_end_q(n,k)的递推式子了，我是
化简不能。。。 |
|
