Help needed on a dp problem about probability and expectation

Правка en1, от Gnay_Oahnauhz, 2016-05-05 10:50:22

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 Pf, Pb, Ps = 1 - Pf + Ps respectively, i.e., if you are on x now, the next step you can move to x + 1 with probability of Pf 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, Pf = 0.25, Pb = 0.25, Ps = 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Gnay_Oahnauhz 2016-05-05 19:03:52 244 (published)
en3 Английский Gnay_Oahnauhz 2016-05-05 19:00:09 331 (saved to drafts)
en2 Английский Gnay_Oahnauhz 2016-05-05 10:51:02 14
en1 Английский Gnay_Oahnauhz 2016-05-05 10:50:22 1065 Initial revision (published)