I'm doing an exercise on expected value. In problems that calculate the expected value of the number of steps to do something, the formula f(state) = 1 + sum of (f(next state) * p(next state)) is often used. where state is the current state, the next state is the new state that can be obtained from the current state, p(next state) is the probability of a new state occurring from the current state. But I just memorized it and applied it like a parrot and always wondered how the formula was proven or built.
I've tried to find this recipe internet before, but I haven't been able to find anywhere that goes into detail about it.
Can someone explain it to me.
Thanks for help!!! Sorry for my bad English.
Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).
Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).
Auto comment: topic has been updated by wonderful_trip (previous revision, new revision, compare).
Maybe what you are looking for is Markov Chains?
I think what you're looking for is the definition of expectation. E(X)=sum of P(X=xi)*xi So Expected number of steps where you visit some next states with some probability is. E(state)=1+p(nextstate1)*E(next state 1) +p(next state2)*E(next state 2) and so on. +1 because you'll need one step to go to the next state.
Thank you for your reply, I have also tried to derive the above formula based on the definition but am struggling to know how to turn the formula in the definition of a general nature into a linear formula like the one above.
Think of expected value as a weighted average of all paths then of course the weighted average of a path starting from a= (fraction of paths going from a to the next node)( weighted average of the paths starting from the next node) E(next state) is nothing but the weighted average of all nodes that have been visited from the next node
What will be the change , if for some cases the step is counted with value 1 and for some cases it is counted with value=0, For example,
For example from N=10 if i move to an odd number then i count that stepvalue as 1, if i move to an even number i count that stepvalue=0, and i want to find the expected value of stepvalue after suppose 10 such steps.
Specifically i am confused with this problem : https://mirror.codeforces.com/problemset/problem/518/D
I tried to use the provided definition for expected value in this question, but it doesnt' work ,E[i][j]=1+(p*(E[i+1][j+1]))+(1-p)*(E[i][j+1]); E[i][j], expected number of people when i people are on escalator and j is the number of seconds passed.
I had also been puzzled by this doubt for quite a long time, and with effort I believe the correct proof of this formula is as follows.
Before we start, some clarification for the proposition is needed. Suppose the states are numbered from $$$1$$$ to $$$n$$$. For any state $$$i$$$, it may transfer to one of its successor state $$$j \in nxt(i)$$$ in one step with probability $$$P_{i,j}$$$. Let random variable $$$S_i$$$ denote the number of steps for state $$$i$$$ to transfer to the final state. The formula states that
The proof needs some basic knowledge of conditional expectation. Consider a certain wandering process in which the exact number of steps $$$S_j$$$ for each state $$$j \in nxt(i)$$$ to transfer to the final state is already known. Now we can use the definition of the expected value safely (beacuse we already know the exact value of every $$$S_j$$$)
then by applying the law of total expectation
we have
the last step applies the linearity of the expected value, which conclude the proof.
The drawback of this proof is that it doesn't handle the case that $P_{i,i}>0$ i.e. a state may transfer to itself. I'm also looking forward to a further explanation :)
Thanks for your reply, it helped me understand this formula better!
Sorry I am new to this recipe, can you tell me.
Is your 2nd recipe based on this one?
Where X is Si and y is Sj. And here X is also x, so x in the above formula = 1 + sj, right?
You are right — in my equations the "$$$==y$$$" part in your equation is omitted, since we can use $$$Y$$$ directly in RHS to represent $$$y$$$ without any confusion. So more precisely, the equation above can be rewrited as
which is definitely harder to write and understand, so the convention is used above.
BTW I have rethought this question, and now I believe a complete solution to these kind of recurrence relation between the expected value lies in Markov chains as defiler123 mentioned above. Anyway, we still have a simple but rather useful understanding as Perpetually_Purple mentioned above.