o****e
发帖数: 80 | 1 Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
expected number of keypresses to
open the door. Suppose my password is a two-digit number (no repeats), and
suppose a light goes on once
I've hit the correct first digit.
E(X)=? |
r*******y
发帖数: 290 | 2 isn't it 10? do you have to enter 2 digits every time even if you hit
the wrong first digit? do you have to enter the correct first digit every
time?
【在 o****e 的大作中提到】
: Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
: expected number of keypresses to
: open the door. Suppose my password is a two-digit number (no repeats), and
: suppose a light goes on once
: I've hit the correct first digit.
: E(X)=?
|
r*****2
发帖数: 156 | 3 for hit the first digit right and the light on E(x1)=3
If you knew the first light, to get the second digit right, E(x2) = 5,
so it is 3+5-1 = 7 ? |
o******e
发帖数: 1001 | 4 Let Y be the number of key presses to hit one right number. We have,
E(X)=1/5(1+E(Y))+4/5(1+E(X))
E(Y)=3
E(X)=8
【在 o****e 的大作中提到】
: Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
: expected number of keypresses to
: open the door. Suppose my password is a two-digit number (no repeats), and
: suppose a light goes on once
: I've hit the correct first digit.
: E(X)=?
|
i*****e
发帖数: 159 | 5 is there any better way to come up with E(Y) = 3 then simple induction like
E(Y) = 1/5+4/5*(1+1/4*1+3/4*(1+1/3*1+2/3*(1+1/2*1+1/2*(1+1))))?
If the two digits are "no repeats", the probabilities in your equation
should be 1/4 and 3/4?
【在 o******e 的大作中提到】
: Let Y be the number of key presses to hit one right number. We have,
: E(X)=1/5(1+E(Y))+4/5(1+E(X))
: E(Y)=3
: E(X)=8
|
g******e
发帖数: 352 | 6 Assume first pressing key 1 for the first digit, if the light is not on,
then you will press key 2 for the first digit and so on. So if the first
digit is n, you will need n presses till the light is on.
E(Y) = E(first digit) = sum(1+2...+5)/5 = 3
like
【在 i*****e 的大作中提到】
: is there any better way to come up with E(Y) = 3 then simple induction like
: E(Y) = 1/5+4/5*(1+1/4*1+3/4*(1+1/3*1+2/3*(1+1/2*1+1/2*(1+1))))?
: If the two digits are "no repeats", the probabilities in your equation
: should be 1/4 and 3/4?
|
c*********g
发帖数: 154 | 7 The correct answer should be 10. We have three states here and the
transition matrix is:
4/5 1/5 0
0 4/5 1/5
0 0 1
with the third state an absorbing state.
Let Q=[4/5 1/5; 0 4/5], inv(I-Q)=[5 5; 0 5]. And we start from the first
state, so the expectation time that we arrive at the absorbing state is 5+5=
10 |
c*********g
发帖数: 154 | 8 Sorry, I missed "no repeats" in the problem.
Now the transition matrix is
4/5 1/5 0
0 3/4 1/4
0 0 1
And inv(I-Q)=[5 4; 0 4]. Then the expectation time is 5+4=9
5=
【在 c*********g 的大作中提到】
: The correct answer should be 10. We have three states here and the
: transition matrix is:
: 4/5 1/5 0
: 0 4/5 1/5
: 0 0 1
: with the third state an absorbing state.
: Let Q=[4/5 1/5; 0 4/5], inv(I-Q)=[5 5; 0 5]. And we start from the first
: state, so the expectation time that we arrive at the absorbing state is 5+5=
: 10
|
t***h
发帖数: 46 | 9 let x=expected key presses
let y=expected key presses after the first digit is found
x=4/5(1+x)+1/5(1+y)
y=1/4+3/4(1+y)
x=9
y=4
【在 o****e 的大作中提到】
: Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
: expected number of keypresses to
: open the door. Suppose my password is a two-digit number (no repeats), and
: suppose a light goes on once
: I've hit the correct first digit.
: E(X)=?
|
w********0
发帖数: 1211 | 10 我觉得问题不明确，关键在于你第一下按的数字如果和密码的第一位不一样的话，你按
的第二下是否无论是什么都不会有反应，所起的作用只是使得该锁的记忆清零，然后才
能重新尝试第一位密码？还是说你第二下如果和密码的第一位一致，仍然亮灯？
比如，如果正确的密码是34， 你第一下按了1，随后再按34，锁会开吗？还是得在1后
按一下任意别的数x，使它认为1x 不等于34，然后才能重头开始？
【在 o****e 的大作中提到】
: Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
: expected number of keypresses to
: open the door. Suppose my password is a two-digit number (no repeats), and
: suppose a light goes on once
: I've hit the correct first digit.
: E(X)=?
|
|
|
l******8
发帖数: 32 | 11 This is NOT Markov chain because remote states count.
E[second try] = 4 but it is obtained differently as
E = (1/4)(1) + (1/4)(3) + (1/4)(5) + (1/4)(7) = 4
【在 t***h 的大作中提到】
: let x=expected key presses
: let y=expected key presses after the first digit is found
: x=4/5(1+x)+1/5(1+y)
: y=1/4+3/4(1+y)
: x=9
: y=4
|
c*********g
发帖数: 154 | |
M*****y
发帖数: 666 | 13 i like this solution, especially minus 1
why no one agree?
【在 r*****2 的大作中提到】
: for hit the first digit right and the light on E(x1)=3
: If you knew the first light, to get the second digit right, E(x2) = 5,
: so it is 3+5-1 = 7 ?
|
s****i
发帖数: 216 | 14 are we allowed to pick same number sequentially?
the result is different in two cases
【在 o****e 的大作中提到】
: Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
: expected number of keypresses to
: open the door. Suppose my password is a two-digit number (no repeats), and
: suppose a light goes on once
: I've hit the correct first digit.
: E(X)=?
|
s****i
发帖数: 216 | 15 Two cases,
one is that you memorise the result, once you crack the 1st bit, you only
have to deal with 2nd bit.
The expected number is E[x] = (1+2+3+4+5)/5 + 2*((1+2+3+4+5)/5)- 1 = 8
The other is just randomly choosing 1 from 5.
let p1(k) be the probability that succeed in round k,
p2(k) be the probability that pass 1st bit in round k,
p3(k) be the probability that fail in round k
suppose you randomly pick from the 5 numbers.
p1(k) = p2(k-1)* 1/5
p2(k) = p3(k-1) * 1/5
p3(k) = p2(k-1)*4/5 + p3(k-
【在 s****i 的大作中提到】
: are we allowed to pick same number sequentially?
: the result is different in two cases
|
f***a
发帖数: 329 | 16 X: 2 3 4 5 6 7 8 9
p(x): 1/20 2/20 3/20 4/20 4/20 3/20 2/20 1/20
E(X)=5.5 |
c*********n
发帖数: 86 | 17 第一次是五个key的情况，E[Y]=(1+2+3+4+5）/5=3；
第二次如果记住了前一次的输入，就相当于四个key的情况，E[Z]=(1+2+3+4)/4=2.5,
所以E[X]=E[Y]+E[Z]=5.5?
is there anything i missed?
【在 o****e 的大作中提到】
: Assume I have a 5 button keypad, with numbers 1-5 on it. Define E(X) =
: expected number of keypresses to
: open the door. Suppose my password is a two-digit number (no repeats), and
: suppose a light goes on once
: I've hit the correct first digit.
: E(X)=?
|
f***a
发帖数: 329 | 18 my solution:
The task can be divided into two step:
step 1: get the 1st digit correctly (light goes on)
step 2: get the 2nd digit correctly
let n1: number of keypresses to complete step 1
n2: number of keypresses to complete step 2
n1 can be 1,2,..,5 with corresponding probability 1/5 for each
n2 can be 1,2,3,4 with corresponding probability 1/4 for each (because no
repeats)
thus n=n1+n2 and n can be 2,...,9 with corresponding probability listed
above.
You can draw a tree to understand this |
j*****4
发帖数: 292 | 19 maybe you need to reinput the first key in the trial for the second.
I feel the problem is not clear on rules to open the lock.
【在 c*********n 的大作中提到】
: 第一次是五个key的情况，E[Y]=(1+2+3+4+5）/5=3；
: 第二次如果记住了前一次的输入，就相当于四个key的情况，E[Z]=(1+2+3+4)/4=2.5,
: 所以E[X]=E[Y]+E[Z]=5.5?
: is there anything i missed?
|
h**i
发帖数: 431 | 20 i cannot see anything wrong with this answer...
【在 c*********n 的大作中提到】
: 第一次是五个key的情况，E[Y]=(1+2+3+4+5）/5=3；
: 第二次如果记住了前一次的输入，就相当于四个key的情况，E[Z]=(1+2+3+4)/4=2.5,
: 所以E[X]=E[Y]+E[Z]=5.5?
: is there anything i missed?
|
f***a
发帖数: 329 | 21 n=n1+n2
since n1, n2 are actually independent (they seems not but they are)
we can derive
E(n)=/sum_n1/sum_n2 {(n1+n2)P(n1,n2)}
=/sum_n1/sum_n2 {(n1+n2)P(n1)P(2)}
=/sum_n1/sum_n2 {n1P(n1)P(2)}+/sum_n1/sum_n2 {n2P(n1)P(2)}
=/sum_n1 {n1P(n1)}+/sum_n2 {n2P(2)}
=E(n1)+E(n2)
【在 c*********n 的大作中提到】
: 第一次是五个key的情况，E[Y]=(1+2+3+4+5）/5=3；
: 第二次如果记住了前一次的输入，就相当于四个key的情况，E[Z]=(1+2+3+4)/4=2.5,
: 所以E[X]=E[Y]+E[Z]=5.5?
: is there anything i missed?
|
