Help needed on a dp problem about probability and expectation
Difference between en1 and en2, changed 14 character(s)
The problem is like this:↵
You are on the origin of a number axis, each time, you can move forward, backward or stay with probability $P_f, P_b, P_s=1-P_f+P_s$ respectively, i.e., if you are on $x$ now, the next step you can move to $x+1$ with probability of $P_f$ and etc.↵
And the question is: after n steps, what's the mathematical expectation of the maximal number you have reached.↵

Here's an example when $n = 2, P_f = 0.25, P_b = 0.25, P_s = 0.5$:↵
~~
~~~↵
maximal number: 1↵
fs: 0.25*0.5 = 0.125↵
sf: 0.5*0.25 = 0.125↵
fb: 0.25*0.25 = 0.0625 (since you have arrived at number 1, even if you go back, you will have maximal number 1)↵
~~~
~~↵
~~


~~~↵
maximal number: 2↵
ff: 0.25*0.25 = 0.0625↵
~~~
~~

since you are on the origin, all other path will have maximal number equal to 0↵

Thus the expectation is: 1*(0.125+0.125+0.0625)+2*0.0625=0.4375↵



There is a dp solution on the problem, but I just can't quite figure out why, perhaps you can just think it over first before I give the answer.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Gnay_Oahnauhz 2016-05-05 19:03:52 244 (published)
en3 English Gnay_Oahnauhz 2016-05-05 19:00:09 331 (saved to drafts)
en2 English Gnay_Oahnauhz 2016-05-05 10:51:02 14
en1 English Gnay_Oahnauhz 2016-05-05 10:50:22 1065 Initial revision (published)