search

standupmaths / frog_problem

Here is the frog problem code I wrote in an Edinburgh pub.
17 stars 15 forks source link

@dewittpe's solution and write up for @standupmaths's frog_problem #2

Open dewittpe opened 5 years ago

illustromancer commented 5 years ago

Something in your final calculation isn't correct, as a direct calculation of the probability of being in the final state using each of the P^n intermediate transition matrices yields a final answer of 2.92896825. The same is true if (I-Q)^-1 is calculated directly in google sheets/excel for n=10.

See this google sheet for two separate methods of calculating the expected number of steps, one from first principles, and the second using the same method in your solution.

https://docs.google.com/spreadsheets/d/1HzawT8I5YjbughzTNrJ_v3MBvNMAylTHwS2-dtKFSQI/edit?usp=sharing

illustromancer commented 5 years ago

Having looked into it a bit more, you are adding 1/11 to your answer for the n=10 case, which you shouldn't be as no jump has a 1/11 probability.

dewittpe commented 5 years ago

Having looked into it a bit more, you are adding 1/11 to your answer for the n=10 case, which you shouldn't be as no jump has a 1/11 probability.

@illustromancer, thank you for looking over the solution I posted. It is always good to have some review. I'm wondering if our interpretation of the problem is slightly different. for the n = 10 case I look at that as there are 10 pads between the frog and the opposite bank. The bank would be the p + 1 pad. With equal probability of jumping to any pad or the bank each transition probability would be 1/11 as there are eleven possible next states.

The full transition probability matrix T should have dimension (p +2) x (p + 2), for the p pads the and the two banks. The matrix Q would then have dimension (p + 1) x (p + 1) for the transitions from the starting bank of the pond to each of the pads; omitting the transition to the final bank. In the google sheet you shared it appears that there are only 10 columns in the Q matrix, which, for the way I interpreted the problem, would be the case of n = 9 pads between the two banks.

illustromancer commented 5 years ago

No worries at all.

Thats the difference then. The problem as stated in the video is that the river is of width 10 (9 lilypads and the opposite bank, or 10 possible landing places), which is stated in the video description, whereas your writeup has 11 possible landing places for n=10 (10 lilypads between the two banks).

It would be worth clarifying that in your writeup.

dewittpe commented 5 years ago

Would you mind looking at the first page of the .pdf file where I defined the problem? Is there any detain there which you like to see added? Thanks.