A frog is randomly placed with equal probability for each integer from 0 to 999 included. There is a wall at 1000, each second the frog jumps, on the kth jump, frog jumps a distance 2^(k+1) equally likely in both directions left and right. What is the expected time for frog to land on or cross the wall at 1000?
No idea how to approach, recursion is too messy
#Expected Value Combinatorics
raven pier
true hedgeBOT
A frog is randomly placed with equal probability for each integer from 0 to 999 ...
- Do not ping the Moderators, unless someone is breaking the rules.
- Do not ping the Helper Moderators, unless there is a conflict between helpers.
- Do not ping other members randomly for help.
- Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
- Wait patiently for a helper to come along.
- If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:
+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:
eternal dew
your current score is a random sum of the form sum (-1)^n 2^{n+1}
presumably the jumps are independent of each other
$$P{X_n = 2^{n+1}} = P{X_n = -2^{n+1}} = \frac{1}{2}$$
opaque obsidianBOT
aL
eternal dew
now you want to know how many jumps are you expected to make for the score to be at least 1000
eternal dew
I tried few recursion ideas
recursion is the go to method for this type of random walk problem
raven pier
But it's not working
eternal dew
show attempt
raven pier
I mean like
Just think
This problem would need
1000 states
To model
How are you gonna do it via recursion
eternal dew
show attempt
raven pier
For 999 998 ans is 2
I did this as follows
For 999 998 proglem is equivalent to
Expected time to take a right
Which is just 2
Since it doesnt matter how many lefts we take the moment we take first right for 998 and 999
We will cross or hit 1000
But a similar logic does NOT hold true for values lesser than 998
eternal dew
would you be able to solve it if it was +- 1 instead?
raven pier
would you be able to solve it if it was +- 1 instead?
Yes then answer is trivially infinity
eternal dew
im sorry what?
raven pier
Lmao
Wrong
IT certainly is
Say
We are at x is 0
And we want to calculate
Exp3cted time to reach 1
eternal dew
you have some misunderstandings about random walks so let me explain
raven pier
Given that we move
50 50 with 1 unit
This is the standard random walk
Very easy to prove expected time to hit 1 as infinite
And by similar logic for all values 0 to 999
It will be infinite
eternal dew
suppose we consider the +-1 case.
Let m_n be the mean nr of steps to reach state n+1 after reaching state n for the first time.
We want to calculate m1 + ... + m999
apply markov property, whence 2(m_n -1) = m(n-1) + m_n
conclude m_n = 2n+1
hence your expected number of moves is 10^6
eternal dew
now modify it to your situation, apply the markov property and conclude your result
raven pier
We are at x is 0
.
What do you think expected time to hit 1 is
In this case
?? Bruh
Reply
Dude where have you disappeared
I'm telling you it's infinity
eternal dew
im trying to see why but no dice
there's nothing special about 1000 or 100
you'd be saying the expected time to hit 5 is infinity
eternal dew
eternal dew
yes i am, i'd advise you to revise what you know
raven pier
yes i am, i'd advise you to revise what you know
Lmao
This process is a martingale
Right?
raven pier
The process of this random walk
Counting
For
A single
Object performing a random walk
On a number line
Equal probability 1/2
+-1
The variable X representing it's position
It is a martingale correct?
eternal dew
alright, lets suppose it is
raven pier
Right then instead of me having to explain the entire proof
Just read this
Read the solution here
It explains the expected steps in such a random walk to reach either a or -b assuming we start at 0
We extend that argument by taking b to infinity which is equivalent to our case en
Rn
eternal dew
the solution is correct with a finite expected value
eternal dew
are we reading the same thing?
raven pier
https://math.stackexchange.com/questions/4328318/expected-value-of-steps-taken-t...
Read it bruv
You are literally just confidently incorrect
The case of +1-1 is infinite
Anyways back to the original problem
The case of +1 -1 doesnt help us one but
Bit
eternal dew
in one case you assume unbounded walk and in another, a bounded one
I'll assume your walk is unbounded then
raven pier
I'll assume your walk is unbounded then
Yea ofc
eternal dew
$$E \min {n \mid \sum ^n X_k \geqslant 1000} = \frac{1}{256} \left ( 24 + \sum _{k=1}^\infty (8+k)\cdot \frac{253}{2^k} \right)$$
opaque obsidianBOT
aL
eternal dew
assuming we start from 0
you're right, it does get messy
the initial placement is not that big of a deal, it results in a compound variable and you can apply law of total expectation to calculate its mean
the trouble is the exponentially growing step size, I can't think of a way to somehow quickly calculate the result
raven pier
exactly
queen rampartBOT
@raven pier
queen rampartBOT
@eternal dew The user still needs help with this help request.