Exercise 2: You can derive a recurrence relation for the sequence {a_k} on by assuming the formula E_0n = a_k + E_kn. In the fair coin example, a_k = k^2. In this case, the prob of going back is 2/3 and forward is 1/3. Applying the EV recurrence to house k you get E_kn = 2/3 * [E_k-1n + 1] + 1/3 * [E_k+1n + 1] and by E_kn = E_0n - a_k, then rearranging for E_0n you get E_0n = 3 - 2a_k-1 + 3a_k + E_k+1 = a_k+1 + E_k+1, netting a_k+1 = 3 - 2a_k - 1 + 3a_k or a_k = 3a_k-1 - 2a_k-2 + 3 Solving this, you need to assume a_k is a linear combination of A*r^k where r is a root of the characteristic polynomial. Substituting this gets the characteristic polynomial r^2 - 3r+2 which has roots 1 and 2. But since the basis term 1^k i.e. constant is already present in the recurrence relation, we need to add a k term. So we assume a_k is in the form a_k = A*2^k + B + Ck. You can derive that a_1 = 1, a_2 = 6, a_3 = 19, and solving for A, B, C in 3 simultaneous eqns gets the final answer of a_k = 4*2^k - 3k - 4. In the end the expected number of blocks to go from house 0 to n is E_0n = 2^[n+2] - 3n - 4.
Guys this is a very easy problem no need to solve equations or do anything just give me like and pray I get into Optiver. Here is the one liner, instead of the reflection think your friends' house is on -4 and +4 u start from 0. u stop when u reach 4 or -4. u need expected stopping time of a symmetric random walk. That is 4*4= 16
for those who aren't aware of this result E(S_n^2-n)=E(S_0^2-0) since that quantity is a martingale where S_n = X1+...+Xk. and E(S_n)=0 from there u get S_n^2 = (4^2+4^2)/2=N.
everyone that manipulated random walks for once should get a good answer, wrong people will use markov chains and absorbing states and it's a big red flag to do so in an interview
Hi. May I ask how to solve this question not using markov chain? The first thing came to my mind is using martingale. But I feel like this is not a martingale because it has an upward trend. Dont know how to solve it. 😢
optiver i watched the whole video can i get an internship
😂
hell no
Exercise 2: You can derive a recurrence relation for the sequence {a_k} on by assuming the formula E_0n = a_k + E_kn. In the fair coin example, a_k = k^2. In this case, the prob of going back is 2/3 and forward is 1/3.
Applying the EV recurrence to house k you get E_kn = 2/3 * [E_k-1n + 1] + 1/3 * [E_k+1n + 1] and by E_kn = E_0n - a_k, then rearranging for E_0n you get
E_0n = 3 - 2a_k-1 + 3a_k + E_k+1 = a_k+1 + E_k+1, netting a_k+1 = 3 - 2a_k - 1 + 3a_k or a_k = 3a_k-1 - 2a_k-2 + 3
Solving this, you need to assume a_k is a linear combination of A*r^k where r is a root of the characteristic polynomial. Substituting this gets the characteristic polynomial r^2 - 3r+2 which has roots 1 and 2. But since the basis term 1^k i.e. constant is already present in the recurrence relation, we need to add a k term. So we assume a_k is in the form a_k = A*2^k + B + Ck.
You can derive that a_1 = 1, a_2 = 6, a_3 = 19, and solving for A, B, C in 3 simultaneous eqns gets the final answer of a_k = 4*2^k - 3k - 4.
In the end the expected number of blocks to go from house 0 to n is E_0n = 2^[n+2] - 3n - 4.
I put it in OEIS. thanks for letting me know "charasteristic polynominal"
@@linyidai9076 would you mind sending the link to it :)
@@linyidai9076 are you able to share the link to the contribution pls :)
These are great! More please :)
We're still waiting for this month prove it. Any update?
Guys this is a very easy problem no need to solve equations or do anything just give me like and pray I get into Optiver. Here is the one liner, instead of the reflection think your friends' house is on -4 and +4 u start from 0. u stop when u reach 4 or -4. u need expected stopping time of a symmetric random walk. That is 4*4= 16
for those who aren't aware of this result E(S_n^2-n)=E(S_0^2-0) since that quantity is a martingale where S_n = X1+...+Xk. and E(S_n)=0 from there u get S_n^2 = (4^2+4^2)/2=N.
Wow that's very clever! Very cool @@infinity624
Quite right!
for k, it’s (k-1)^2. So it’s 16. Very textbook problem
for real hehe
everyone that manipulated random walks for once should get a good answer, wrong people will use markov chains and absorbing states and it's a big red flag to do so in an interview
Hi. May I ask how to solve this question not using markov chain? The first thing came to my mind is using martingale. But I feel like this is not a martingale because it has an upward trend. Dont know how to solve it. 😢
fuck me,you read me like a book,i just used the MC
I used gambler's ruin time + wald's equation😅
I think there is a mistake the +1 should be on the other side. E(X_1) + 1 = 1/2E(X_0) + 1/2E(X_2) OPTIVER I THOUGHT YOU WERE a good firm!!