Project Euler Forum

karabonev wrote: Tue May 10, 2022 8:21 am I've been struggling with this problem for a while.
My answer for P is right but PP is a bit off.

Let P(x) be the chance to croak P on jump x.
P(1) = 119/300
I assume that the chance to hear PP is P(1) * P(2).
Previous posts suggest that the probability for PP is 173/1125 so I expect P(2)=692/1785.
However, I get P(2)=149/375.

Can anyone confirm if my assumption is correct?

If I'm understanding your definition for P(x) correctly, then your assumption is most definitely incorrect. And if I'm not, then your calculation is incorrect.

Edit: I was able to reproduce your value of P(2) and can confirm your assumption is indeed wrong. Probability is tricky like that.

karabonev wrote: Tue May 10, 2022 8:21 am I assume that the chance to hear PP is P(1) * P(2).
...
Can anyone confirm if my assumption is correct?

This is a different phrasing of m4rius' question

is it right to assume that the events "nth croak equals Xn", where Xn in {P, N}, are stochastically independent?

and the answer is the same: the previous croaks convey partial information about where the frog is, and hence the probability of the jump landing on a prime.

neverforget wrote: Wed May 11, 2022 5:19 am Edit: I was able to reproduce your value of P(2) and can confirm your assumption is indeed wrong. Probability is tricky like that.

Thank you for confirming that.
I still don't understand why it is wrong though.

My other idea was to check the chance of croaking PP for every possible combination of two jumps.
This produced 230/1497 which is still a bit off.

karabonev wrote: Wed May 11, 2022 12:22 pm My other idea was to check the chance of croaking PP for every possible combination of two jumps.
This produced 230/1497 which is still a bit off.

Not every combination of two jumps are equally likely. For example, starting at 1 then going to 2 is twice as likely as starting at 2 and going to 3. Seems like you are treating these as equally likely, which is not so.

I still don't understand why it is wrong though.

I thought it counted as hint which is why I didn't say why, but pjt33 pretty much stated the reason directly. So to explain even more clearly: what is going on is that unconditional event probabilities can only be multiplied to find conjunctive probability if the events are independent. With your idea to check every possible paths, you can easily verify that the (unconditional) probability that frog will croak P at step 2 is not the same (conditional) probability that frog will croak P at step 2 given it croaks P at step 1.

neverforget wrote: Wed May 11, 2022 5:59 pm

karabonev wrote: Wed May 11, 2022 12:22 pm My other idea was to check the chance of croaking PP for every possible combination of two jumps.
This produced 230/1497 which is still a bit off.

Not every combination of two jumps are equally likely. For example, starting at 1 then going to 2 is twice as likely as starting at 2 and going to 3. Seems like you are treating these as equally likely, which is not so.

I eventually came to this conclusion, tweaked my algorithm and solved the problem.
Thank you for the clarifications.
Probability can be tricky indeed.