EDIT 2
After thinking for a while, it seems to me that part of the problem you're actually struggling with is how to state and specify the "real life" problem
that you want to solve, rather than actually solving it. One way to state and solve the problem is addressed below, here I'd like to discuss about other ways to specify the problem.
In short, you may want to have a look at Markov chains, or even hidden Markov chains.
One way to see Markov chains, is that you have a system that can evolve between certain states, with a certain probability. Here for example, person $A$ could be your system, and its state could be which city $A$ is currently in. You can make things non uniform by specifying the probabilities with which the system can transition from one state to another.
Want to include $B$? Make the system pairs of cities. Don't want to make the decision of $A$ and $B$ independent? That's already built-in with the probability to transition from one state to another. Want to have time play a role? One transition can be equivalent to one time unit, and a state can transition into itself to simulate that $A$ and $B$ do not move.
Want to simulate a 2-day vacation to another city (staying 2 days somewhere, coming back to hometown)? Make a special state that can only transition back to the state it came from...
I think you get the idea. To conclude, the approach below could be modeled by a Markov chain, but it would probably be very annoying. The more "natural" thing to do with Markov chain would be to have $N$ and $M$ as random variables, enforcing them to be constant would probably be annoying?
(Not sure, I haven't done any Markov chain in ages.)
Original answer
You need to specify in some way what the probabilities are when $A$ and $B$ move around...
For instance for $A$, is $N$ fixed or a random variable?
Assuming $N$ is fixed, $A$ will visit $N+1$ points, let $T_i$ be the number of days $A$ stay at the $i$-th point.
Can the $i$-th point and the $(i+1)$-th point be the same? I'll assume that they must be distinct.
I'll also assume that $T_i\ge 1$ for every $i$, and that every $T_i$ is an integer.
Just looking at the $T_i$, there is $364\choose N$ possible choices of them.
This corresponds to all the ways $A$ can choose to move around, without specifying where.
When looking at the locations, $A$ can choose between $P-1$ destinations, so if we disregard the "when", we have a choice between $(P-1)^N$ trajectories. I ignored the starting point, but if this is also a variable make that $(P-1)^{N+1}$.
If you put those together, there are ${364\choose N}(P-1)^N$ ways for $A$ to move around in the span of one year. Are all of these ways equally probable? Or is there some specific process for $A$ to choose when and where he moves?
Unless you specify this information, it will be difficult to solve your problem.
Ps: if $A$ and $B$ start on the same point, they will obviously be together on the same point on day 1... you may want to revise your problem statement.
EDIT 1
Nick G was faster than me, but I want to add a few remarks to his approach
(read his answer first).
When $A$ and $B$ move simultaneously, there are indeed $(p-1)^2$ possible pairs of destination, but only $p-2$ outcomes where $A$ and $B$ meet. Indeed $A$ can move to $p-1$ points, but that number includes the point where $B$ is currently at. Because they cannot meet there, only $p-2$ cities (and outcomes) remain.
So the probability that they do not meet right after they both move is
$$\frac{(p-1)^2-(p-2)}{(p-1)^2}$$
When $X=k$, the probability they do not meet during the course of one year then becomes
$$
P(\text{$A$ and $B$ do not meet}\mid X=k)=
\left(\frac{p-2}{p-1}\right)^{N+M-2X}\times \left(\frac{(p-1)^2-(p-2)}{(p-1)^2}\right)^X
$$
The last remaining problem is how to determine $X$.
Let $T^A_i$ be the number of days $A$ stays in the $i$-th city he visits, likewise for $T^B_i$. Given the values of $T^A_i$ and $T^B_i$ it is possible to compute $X$. You didn't provide any information on the probability of having one set of $T^A_i$, $T^B_i$ over another, so I'll just assume uniform distribution. Also dealing with the durations of the stay is annoying, so instead let $U^A_i$ be the night when $A$ travels from the $i$-th city to the $(i+1)$-th city.
The sequence $(U^A_i)_{1\le i\le N}$ is strictly increasing and has integer values between $1$ and $364$ (inclusive).
We have likewise a sequence $(U^B_i)_{1\le i\le M}$ for $B$.
Without loss of generality assume $N\le M$. For an integer $k$, $0\le k\le N$,
we want to compute
$P(X=k)$,
the probability that $X$ is equal to $k$. Because we assume uniform distribution, it is the number of ways to draw both
$(U^A_i)$ and $(U^B_i)$ such that they share exactly $k$ identical night values divided by the total number of ways to draw
$(U^A_i)$ and $(U^B_i)$.
There are $364\choose k$ ways to choose $k$ distinct nights on which $A$ and $B$ both move. Following this, $A$ still move $N-k$ times on the remaining $364-k$ nights, while $B$ move $M-k$ times. However, those
$(N-k)+(M-k)$ nights must be distinct, there are
$364-k\choose N+M-2k$ ways to chose the nights they move on, and
${N+M-2k\choose N-k} = {N+M-2k\choose M-k}$ ways to decide whether $A$ or $B$ is the one moving during those nights.
In the end there are
$$
{364\choose k}\times{364-k\choose N+M-2k}\times{N+M-2k\choose N-k}
=\frac{364!}{k!\,(364-N-M+k)!\,(N-k)!\,(M-k)!}
$$
different ways to draw the nights $(U^A_i)$ and $(U_i^B)$ so that $A$ and $B$ move the same night exactly $k$ times.
In total, there are ${364\choose N}\times{364\choose M}$ ways to draw the nights (without constraints). This means we can compute
$P(X=k)$.
To conclude,
$$
P(\text{$A$ and $B$ do not meet})
=\sum_{k=0}^N P(X=k)\times P(\text{$A$ and $B$ do not meet}\mid X=k)
$$
and you want to take $1$ minus the above to answer your problem.
I have no clue whether there is a nice simplification of the various formula, but at least a computer can do the work for you.
Also note that the assumption in this model are not very "realistic".
As TMM pointed out, most people should have some kind of pattern when travelling. Uniform distribution on the $(U^A_i)$ and $(U^B_i)$ also means
the below situations have the same likelihood:
- $A$ visits one city per day $N$ days in a row then do not move the rest of the year
- $A$ stays $365/(N+1)$ days in each city he visits
- anything in between
- and let's not forget it's the same for $B$
- the model also assumes that $(U^A_i)$ and $(U^B_i)$ are independant by the way
Depending on the circumstances, those may not be desirable properties...
Best Answer
Assume that you have just finished talking about one topic. Let's assume we have $n$ people.
If we model the number of seconds the $i^{th}$ person typically takes to start a new conversation as a continuous random variable $S_i$, what we need to compute is the probability that, in a sample of these n random variables, the first two happen within 1 second of each other.
A natural assumption is that each of the $S_i$ is exponentially distributed, and that everyone takes on average the same time to start a new topic (probably not true, but let's keep it simple for now). This means: $$p(S_i = x) = \lambda e^{-\lambda x}$$
The parameter $\lambda$ is the inverse of the average time a single person takes to come up with a new topic. In order to simplify things let's think about a version where there are only 2 people speaking, you want $p(|S_1 - S_2|) < 1$, which is $p(S_2 \in [S_1, S_1+1]) + p(S_1 \in [S_2, S_2+1])$ This is equivalent to:
$$\int_0^{\infty} \int_{s_1}^{s_1+1} p(S_1=s_1) \cdot p(S_2=s_2) ds_2 ds_1 + \int_0^{\infty} \int_{s_2}^{s_2+1} p(S_1=s_1) \cdot p(S_2=s_2) ds_1 ds_2 $$
Since the probability distributions for $S_1$ and $S_2$ are the same, we have:
$$2 \cdot \int_0^{\infty} \int_{s_1}^{s_1+1} p(S_1=s_1) \cdot p(S_2=s_2) ds_2 ds_1$$
Replacing the probability density function:
$$ 2 \cdot \int_0^{\infty} \lambda e^{-\lambda s_1} ds_1 \int_{s_1}^{s_1+1} \lambda e^{-\lambda s_2} ds_2$$
It is easy to integrate the exponential pdf (try it!) and the result is $1 - e^{-\lambda}$. Without surprise, the probability that two people start a topic at almost the same time grows with $\lambda$. A large $\lambda$ means that people take little time to start a new topic on average, so the probability of collision increases.
If you want to model this for two people that come up with a new topic at different rates, you can use two different distributions with $\lambda_1$ and $\lambda_2$. This time you have to compute the two original integrals. Computing this yields: $$\frac{(1-e^{-\lambda_2})\lambda_1 + (1-e^{-\lambda_1})\lambda_2}{\lambda_1 + \lambda_2}$$
Again, as the $\lambda$ increase the probability of getting two people talking at the same time increases. You can check the heatmap below to see its shape. The x-axis represents the average time the first person takes to initiate a new topic ($\lambda_1^{-1}$) and the y-axis the same for the second person ($\lambda_2^{-2}$).
So, now that we have solved this for the case of 2 people how can we solve it for the case of $n$? I think it's probably easier if we try to compute the probability of the opposite event: that a single person comes up with the topic alone, which means everyone else would have come up with a new topic more than 1 second later.
The probability that the first person comes up with a new topic alone is: $$\prod_{i=2}^n p(S_i > S_1 + 1)$$
The probability that any person comes up with the topic alone is the sum of the above for each person: $$\sum_{i=1}^n \prod_{j \neq i} p(S_j > S_i + 1)$$
Let's assume again that $S_i$ has an exponential distribution with parameter $\lambda_i$. Let us first determine what is the integral for $p(S_j > S_i + 1)$:
$$\int_0^{\infty} \int_{s_1+1}^{\infty} p(S_i=s_i) \cdot p(S_j=s_j) ds_j ds_i$$
Solving this integral yields:
$$\frac{\lambda_i e^{-\lambda_j}}{\lambda_i + \lambda_j}$$
Therefore the probability that two people initiate a new topic at "the same time" is:
$$1 - \sum_{i=1}^n \prod_{j \neq i} \frac{\lambda_i e^{-\lambda_j}}{\lambda_i + \lambda_j} $$
If everyone takes the same time $\lambda^{-1}$ on average to start a new topic, the above becomes:
$$ 1 - \sum_{i=1}^n \prod_{j \neq i} \frac{\lambda e^{-\lambda}}{2 \lambda} = 1 - \sum_{i=1}^n \frac{e^{-(n-1)\lambda}}{2^{n-1}} = 1 - n \frac{e^{-(n-1)\lambda}}{2^{n-1}}$$
Just as a sanity check, if you take $n$ to be 2, the above simplifies to our original formula $1 - e^{-\lambda}$ =)