I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula.
I have the next case:
In a lake there are $n$ fish, let's say that fish $i$ has probability $a_{ij}$ of eating fish $j$. Accordingly, fish j has probability $a_{ji}$ of eating fish $i$.A fish cannot eat itself so we will consider $a_{ii}=0$.
In one day it is known that only two fish will meet and at the end, one of them will be eaten.The probability of each other pair meeting is the same.
Let's say that we have a day in which we are certain that fish $i$ will be one of those two fish.
What is the probability that fish $i$ will come out eaten at the end of that day?
I initially thought that the formula would be: $$p=\frac{1}{n-1}\cdot\sum_{t=1}^{n}a_{ti}$$
But I was proven wrong and it seems that the formula is: $$p=\frac{2}{n(n-1)}\cdot\sum_{t=1}^{n}a_{ti}$$
My logic was:
Since there is an equal chance for fish $i$ of meeting any other fish, fish $i$ has a probability of $\frac{1}{n-1}$ of meeting fish $t$ and in case that happens fish $t$ has a probability of $a_{ti}$ of eating fish $i$.
I can't, however, understand where I am wrong and how is the second formula right.
I would be very grateful if anyone could help.
In fact your formula $\displaystyle p = \frac{1}{n-1}\sum_{t=1}^n a_{ti}$ does give the probability that fish $i$ will be eaten, given that fish $i$ is one of the pair of fish that meet. The other probability, $\displaystyle p = \frac{2}{n(n-1)}\sum_{t=1}^n a_{ti}$ is the probability that fish $i$ will be eaten, without any prior knowledge about which fish will meet today.