Prove it - Ep2: Another random walk

In the second episode of Prove It, we present another intriguing probability puzzle involving a random walk. To make it more interesting, we've included a fun twist that adds to the complexity of the problem. So dive in and start solving.
Don't forget to submit your solutions to the puzzle via the link below. Good luck!
optiver.com/pr...
---
Prove it is an interactive problem-solving series designed for maths enthusiasts of all ages looking to elevate their skills. You don't need to be a mathematician to dive in - all you need is your curiosity, creative thinking, and a basic understanding of probability.
At Optiver, we use maths, science, and technology to create innovative solutions for real-world problems in our day-to-day.
Curious to discover how you can apply your maths skills outside of the classroom? Jump into a world of probability and maths with Prove It!
#maths #probability #puzzle

[@vicente3j]

optiver i watched the whole video can i get an internship

[@parthkumar6196]

😂

[@billyb5225]

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.

[@entropekomiko]

I used gambler's ruin time + wald's equation😅

[@infinity624]

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

[@infinity624]

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.

[@madhuragrawal5685]

Wow that's very clever! Very cool ​@@infinity624

[@vahidnaghshin6455]

We're still waiting for this month prove it. Any update?

[@sagnikbiswas3268]

for k, it’s (k-1)^2. So it’s 16. Very textbook problem

[@Munnu-hs6rk]

for real hehe

[@janisaiad9505]

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

[@peizhengwang]

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. 😢

[@gqp3185]

fuck me,you read me like a book,i just used the MC

[@jasonzhou3314]

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!!

[@raihansojib6370]

Full scam 😮