Susan has a prime frog.
Her frog is jumping around over 500 squares numbered 1 to 500. He can only jump one square to the left or to the right, with equal probability, and he cannot jump outside the range [1;500].
(if it lands at either end, it automatically jumps to the only available square on the next move.)When he is on a square with a prime number on it, he croaks 'P' (PRIME) with probability 2/3 or 'N' (NOT PRIME) with probability 1/3 just before jumping to the next square.
When he is on a square with a number on it that is not a prime he croaks 'P' with probability 1/3 or 'N' with probability 2/3 just before jumping to the next square.Given that the frog's starting position is random with the same probability for every square, and given that she listens to his first 15 croaks, what is the probability that she hears the sequence PPPPNNPPPNPPNPN?
Give your answer as a fraction p/q in reduced form.
My idea is this:
First calculate $P_n$ = $P\text{("frog sits on a prime after }n\text{ jumps")}$, which can be done by some basic combinatorics + evaluating the "ribbon". I got
\begin{equation} P_0 = 19/100 = 95/500, P_1 = 24/125, P_2 = 571/3000, \dots \end{equation}
which should be ok.
Next, for $n=0,\dots,14$ calculate
\begin{equation} Q_n = P_n \cdot P(\text{"sits on $P$ and croaks }X_n\text{"}) + (1 - P_n) \cdot P(\text{"sits on $N$ and croaks }X_n\text{"}) \end{equation}
where $(X_n)_{n=0\dots14} = PPPPNNPPPNPPNPN$ is our croaking sequence and
\begin{equation} P(\text{"sits on $X$ and croaks }Y\text{"})=\begin{cases} 1/3, & \text{if $X\dot{\lor}Y$}.\\ 2/3, & \text{else}. \end{cases} \end{equation}
That is, $Q_n$ should exactly be $P(\text{"}n\text{th croak equals }X_n\text{"})$ and the product of the $Q_n$ should be the solution. But it's not, so where am I wrong? Are the $Q_n$ not stochastically independent? Whether the frog croaked $P$ or $N$ after $n$ steps should not affect the probability for him to croak $X_{n+1}$ next!?
My results are
\begin{equation} 119/300\text{ for $X = P$ (should be correct)}\\ 17731/112500\text{ for $X = PP$ (should actually be $173/1125$ I think)}\\ \dots \end{equation}
I checked your $P_n$ calculation for $n=0,1$, so let's assume it's correct. Your main error is that the events "frog sits on a prime after n jumps" and therefore the event $Q_n$ describes are highly correlated for consecutive $n$.
After all, if the frog is on a prime number after n steps, this is highly likely an odd number. After one more jump it is then higly likely on an even number, which in turn is highly likely not $2$, so not a prime number. So the frog being on a prime before and after a jump is highly unlikely (just $2 \leftrightarrow 3$)
You approach might work if it was an "odd/even" Frog, that croaks differently based on if the number it's on is odd/even. Then you know for a fact that the Frog will alternate beween an odd and an even postition. But with prime numbers and their irregurities, you cannot hope to describe the differences between how prime numbers are distributed near one prime and another.