l*****y
发帖数: 317 | 1 1. x1, x2...xn uniformly distributed on [0, 1]. S1 = x1, S2 = x1 + x2...Sn =
x1 + x2 +...+ xn. What is the expected index T that makes ST >= 1?
2. Consiser a series of real numbers. Define local maximum variable as: if x
(n) > x(n-1) && x(n) > x(n+1), then x(n) is a local maximum variable. On
either side of the series, it just needs to be greater than its neighbouring
element. The question is: what is the expected number of local maximum
variable? |
c**********e
发帖数: 2007 | |
x********o
发帖数: 519 | 3 how do you approach the second one?
【在 c**********e 的大作中提到】
: 1. e.
: 2. (n+1)/3.
|
c**********e
发帖数: 2007 | 4 As they are real numbers, the chance of being equal is 0. The 1st one and
the last one each has chance of 1/2 being a local maximum, while others each
have chance of 1/3 being local maximum.
【在 x********o 的大作中提到】
: how do you approach the second one?
|
x********o
发帖数: 519 | 5 nice
each
【在 c**********e 的大作中提到】
: As they are real numbers, the chance of being equal is 0. The 1st one and
: the last one each has chance of 1/2 being a local maximum, while others each
: have chance of 1/3 being local maximum.
|
g********t
发帖数: 11 | 6 2：Assuming that the first one and the last one are not local maximum.
If all numbers are independent of each other, for any three numbers x(n-1),
x(n), x(n+1), Event {x(n-1) < x(n)} and event {x(n+1) < x(n)} are
independent
and the probability is 1/2 each. Therefore, the probability is 1/4 for x(n)
to
be a local maximum.
You could use a recursion formula to prove that the answer is (n-2)/4 for
above assumption.
=
x
neighbouring
【在 l*****y 的大作中提到】
: 1. x1, x2...xn uniformly distributed on [0, 1]. S1 = x1, S2 = x1 + x2...Sn =
: x1 + x2 +...+ xn. What is the expected index T that makes ST >= 1?
: 2. Consiser a series of real numbers. Define local maximum variable as: if x
: (n) > x(n-1) && x(n) > x(n+1), then x(n) is a local maximum variable. On
: either side of the series, it just needs to be greater than its neighbouring
: element. The question is: what is the expected number of local maximum
: variable?
|
c**********e
发帖数: 2007 | 7
,
This is not right. If {x(n-1) < x(n)}, then {x(n+1) < x(n)} has a
probability 2/3. So x(n) being local maximum is 1/2 * 2/3 = 1/3.
)
【在 g********t 的大作中提到】
: 2：Assuming that the first one and the last one are not local maximum.
: If all numbers are independent of each other, for any three numbers x(n-1),
: x(n), x(n+1), Event {x(n-1) < x(n)} and event {x(n+1) < x(n)} are
: independent
: and the probability is 1/2 each. Therefore, the probability is 1/4 for x(n)
: to
: be a local maximum.
: You could use a recursion formula to prove that the answer is (n-2)/4 for
: above assumption.
:
|
j*****4
发帖数: 292 | 8 The two events are not independent. careerchange's answer is right.
Just think about this simple problem: A, B, C are iid U[0,1]
P(A>B,C>B)=1/3 (Draw a 3D cube to derive the number easily).
For generall distribution,it's also 1/3 by symmetry.
This recalls me another problem, two random numbers are given, make a
winning strategy to guess which is bigger.
,
)
【在 g********t 的大作中提到】
: 2：Assuming that the first one and the last one are not local maximum.
: If all numbers are independent of each other, for any three numbers x(n-1),
: x(n), x(n+1), Event {x(n-1) < x(n)} and event {x(n+1) < x(n)} are
: independent
: and the probability is 1/2 each. Therefore, the probability is 1/4 for x(n)
: to
: be a local maximum.
: You could use a recursion formula to prove that the answer is (n-2)/4 for
: above assumption.
:
|
l*****y
发帖数: 56 | 9 Why the answer for the first one is e?
I thought E(T)=\sum_k=1 k*Pr(Sk>=1|index=k),
and Pr(Sk>=1|index=k)=1-1/k!. If this is correct, E(T) is infinity.
Please correct me if I were wrong.
在 liftway (liftway) 的大作中提到: 】
x2...Sn =
if x
neighbouring |
s*******j
发帖数: 9 | 10 e = E(\sum_i=1^\infty 1_{S_i<1}) + 1
and P(S_i<1) = 1/i!
【在 l*****y 的大作中提到】
: Why the answer for the first one is e?
: I thought E(T)=\sum_k=1 k*Pr(Sk>=1|index=k),
: and Pr(Sk>=1|index=k)=1-1/k!. If this is correct, E(T) is infinity.
: Please correct me if I were wrong.
: 在 liftway (liftway) 的大作中提到: 】
: x2...Sn =
: if x
: neighbouring
|
|
|
l*****y
发帖数: 56 | 11 Thanks. I guess I misunderstood the question.
Btw, I think e = E(\sum_i=1^\infty 1_{S_i<1}).
【在 s*******j 的大作中提到】
: e = E(\sum_i=1^\infty 1_{S_i<1}) + 1
: and P(S_i<1) = 1/i!
|
C*O
发帖数: 389 | 12 How did you figure out Pr(S_i < 1) = 1/i!?
Any reference?
【在 s*******j 的大作中提到】
: e = E(\sum_i=1^\infty 1_{S_i<1}) + 1
: and P(S_i<1) = 1/i!
|
x******a
发帖数: 6336 | 13 看绿皮书吧
i＝2是三角形
i＝3是三棱锥
i＝4。。。by induction
【在 C*O 的大作中提到】
: How did you figure out Pr(S_i < 1) = 1/i!?
: Any reference?
|
C*O
发帖数: 389 | 14 多谢了
绿皮书这么强大啊
【在 x******a 的大作中提到】
: 看绿皮书吧
: i＝2是三角形
: i＝3是三棱锥
: i＝4。。。by induction
|
x******a
发帖数: 6336 | 15 这个不就是一个多重积分吗
【在 C*O 的大作中提到】
: 多谢了
: 绿皮书这么强大啊
|
C*O
发帖数: 389 | 16 你整整..
【在 x******a 的大作中提到】
: 这个不就是一个多重积分吗
|
x******a
发帖数: 6336 | 17 肯定整过了。。。
【在 C*O 的大作中提到】
: 你整整..
|
C*O
发帖数: 389 | 18 P(Y>X,Y>Z) = \int_0^1 dx \int_0^1 dz \int_max(x,z)^1 dy
\int_0^1 dx \int_^1 max(x,z) = 2/3.
=> P(Y>X,Y>Z) = 1/3
,
)
【在 g********t 的大作中提到】
: 2：Assuming that the first one and the last one are not local maximum.
: If all numbers are independent of each other, for any three numbers x(n-1),
: x(n), x(n+1), Event {x(n-1) < x(n)} and event {x(n+1) < x(n)} are
: independent
: and the probability is 1/2 each. Therefore, the probability is 1/4 for x(n)
: to
: be a local maximum.
: You could use a recursion formula to prove that the answer is (n-2)/4 for
: above assumption.
:
|
x********i
发帖数: 10 | 19 1. I guess the statement is mistaken. It should be "What is the expected
index T that makes ST <= 1?" Or else the answer is infinity. First we can
get P(S_i<=1)=1/i!. Basically it can be proved by inductive reasoning. The
derivation is a bit complicated (refer to the problem of 'sum of random
variables' in Chapter 4 of the book by Xinfeng Zhou). Then E(T)=\Sum_i=1_to
_\Inf(i*P(S_i<=1))=\Sum_i=1_to_\Inf((i-1)!)=e (to see this evaluate the
Taylor expansion of e^x at x=1)
2. I think the answer should be (n+2)/4. Several previous posts use
conditions in Problem #1, but they are separate. If n=2, there is only one
local maximum. When n increases by 1, we assume the extension occurs on the
right side of the existing series. There are only four results with equal
probabilities: (1) x(n)>x(n-1) and x(n+1)>x(n): no maximum added; (2) x(n)>x
(n-1) and x(n+1)x
(n): 1 maximum added; (4) x(n)
from n to n+1 the number of local maximum variables increases by 1/4. The
answer is (n+2)/4
Please comment if you disagree. Thanks!
=
x
neighbouring
【在 l*****y 的大作中提到】
: 1. x1, x2...xn uniformly distributed on [0, 1]. S1 = x1, S2 = x1 + x2...Sn =
: x1 + x2 +...+ xn. What is the expected index T that makes ST >= 1?
: 2. Consiser a series of real numbers. Define local maximum variable as: if x
: (n) > x(n-1) && x(n) > x(n+1), then x(n) is a local maximum variable. On
: either side of the series, it just needs to be greater than its neighbouring
: element. The question is: what is the expected number of local maximum
: variable?
|
w******g
发帖数: 313 | 20 我今天面试面到第二个题了，的确是(n+1)/3.
can
The
to
one
the
【在 x********i 的大作中提到】
: 1. I guess the statement is mistaken. It should be "What is the expected
: index T that makes ST <= 1?" Or else the answer is infinity. First we can
: get P(S_i<=1)=1/i!. Basically it can be proved by inductive reasoning. The
: derivation is a bit complicated (refer to the problem of 'sum of random
: variables' in Chapter 4 of the book by Xinfeng Zhou). Then E(T)=\Sum_i=1_to
: _\Inf(i*P(S_i<=1))=\Sum_i=1_to_\Inf((i-1)!)=e (to see this evaluate the
: Taylor expansion of e^x at x=1)
: 2. I think the answer should be (n+2)/4. Several previous posts use
: conditions in Problem #1, but they are separate. If n=2, there is only one
: local maximum. When n increases by 1, we assume the extension occurs on the
|
|
|
x******a
发帖数: 6336 | 21 today is sunday...
【在 w******g 的大作中提到】
: 我今天面试面到第二个题了，的确是(n+1)/3.
:
: can
: The
: to
: one
: the
|
w******g
发帖数: 313 | 22 国内的面试
【在 x******a 的大作中提到】
: today is sunday...
|
r********n
发帖数: 7441 | 23 啊，啥是绿皮书啊？
【在 x******a 的大作中提到】
: 看绿皮书吧
: i＝2是三角形
: i＝3是三棱锥
: i＝4。。。by induction
|
p********6
发帖数: 1802 | 24 Just a simple permutation.
【在 C*O 的大作中提到】
: P(Y>X,Y>Z) = \int_0^1 dx \int_0^1 dz \int_max(x,z)^1 dy
: \int_0^1 dx \int_^1 max(x,z) = 2/3.
: => P(Y>X,Y>Z) = 1/3
:
: ,
: )
|
p********6
发帖数: 1802 | 25 2.Are the four results equal probabilities?
can
The
to
one
the
【在 x********i 的大作中提到】
: 1. I guess the statement is mistaken. It should be "What is the expected
: index T that makes ST <= 1?" Or else the answer is infinity. First we can
: get P(S_i<=1)=1/i!. Basically it can be proved by inductive reasoning. The
: derivation is a bit complicated (refer to the problem of 'sum of random
: variables' in Chapter 4 of the book by Xinfeng Zhou). Then E(T)=\Sum_i=1_to
: _\Inf(i*P(S_i<=1))=\Sum_i=1_to_\Inf((i-1)!)=e (to see this evaluate the
: Taylor expansion of e^x at x=1)
: 2. I think the answer should be (n+2)/4. Several previous posts use
: conditions in Problem #1, but they are separate. If n=2, there is only one
: local maximum. When n increases by 1, we assume the extension occurs on the
|
f*******g
发帖数: 79 | 26 For second problem，you can deform the serie to a circle by connect the
begining to the end， after insert an integeral number smaller than any known number
between the begin and end。 then the number of local maximum equals to the
old problem， but we have good symmetry。 now we can proceed to consider
average by pick up any intergral。 |
L**********u
发帖数: 194 | 27 第一题应该是写错了。否则，级数不收敛。
应该是 S_n<=1。 |
