Imagine we have a directed graph in which each edge connecting a
vertex to another vertex is labelled by the probability of
jumping from to . This precludes the condition that the
sum of the labels of all outgoing edges is 1.
So, here is what I would like to consider today: if I have two
particles moving between the states designated by the vertices of a
directed graph according to the probabilities assigned to each edge,
what is the probability of collision at step ?
An Unsatisfactory Solution
Assume we have possible states
labelled by , and let
denote the probability of
jumping from state to step . If I form the transition matrix the entries of calculate the probability
of jumping from state to state
in -steps. Then the probability of having a
collision at step at a state
is if one particle starts at
state and the other starts at
. If I would consider only the
collision probability then where, again, denote the entries of the -th power of the transition matrix. A
better way of writing the same equality goes through the observation
that where we use to denote the entries of the
transpose . In other words
is the -th entry in the matrix . If the situation calls for
checking existence of a collision regardless of where each particle
starts then we must add all probabilities. Thus the total probability
of a collision at step is the sum of all entries of the matrix
divided by : Division by happens because I assume all initial
positions are assumed to be equally likely.
In most cases, stabilizes as
goes to , and therefore the probability
also stabilizes. As stabilizes, the rows of the
stabilized matrix become the 1-eigen vector of . If that vector is $ < u_1,,u_m>
$ then the stable collision probability is . This phenomenon will
occur below in the examples I will use.
A More Suitable Solution
The solution I gave above checks if we have a solution at step , and does not care if we have a
collision before the step . If the
setup requires that we stop in the event of a collision then I must
modify the solution.
We start with a different problem first: assume we have two subsets of
vertices and in , and let us try to find the probability
of jumping from the combined state to the combined state . Recall that is a conditional probability: the
probability of jumping to state
given that we are at state . So,
the conditional probability of jumping to state from state is where stands for the proability of being
at state . If we assume that , that is, every state is
equally likely, then Now, observe that for a pair of
particles, the product measures the
conditional probability of the pair jumping respectively to the states
and from states and . Then the conditional probability of
jumping into a collision state from a collision state is From a non-collision state to a
collision state
For notational simplicity, I will use for and for . Then the probability of jumping
from a collision state to a non-collision state and finally from a non-collision state to a collision
state Let denote the
probability of seeing our first collision at step . Then Then the
expected number of steps before we see our first collision is The last terms should be
familiar from your calculus classes: it is the derivative of the power
series evaluated at . This is , and therefore, the
expected number of steps for seeing a first collision is
A Small Variation
What if I would like to calculate the expected number of steps
between two collisions? That is, I am going to have two particles
starting at the same position and then wait until they collide again.
What is the expected number of steps until that happens? I will use
to denote probability of that
happening at step . This is the
conditional probability of seeing the first collision at step given that we start with a collision
state. For we have . And for Then the expected number of steps between
two collision becomes Again the series is the derivative of the function evaluated at . Then
Implementation
import numpy as np
import math
def see(P,n):
if n < 0:
res = 0
else:
res = (P**n)*(P.transpose())**n
return res.flatten().sum()/P.size
def c2c(P):
return np.matrix([x**2 for x in P.flat]).sum()/math.sqrt(P.size)
def nc2c(P):
m = math.sqrt(P.size)
return 1/(m-1)*( (P*P.transpose()).sum()/m - c2c(P) )
def collision(P,n):
if n < 0:
res = 0
elif n == 0:
res = 1/math.sqrt(P.size)
else:
psi = nc2c(P)
res = (1.0 - 1.0/math.sqrt(P.size))*( 1.0 - psi )**(n-1)*psi
return res
def total(P,N):
res = 0
if N > -1:
for i in range(N):
res += collision(P,i)
return res
def firstCollision(P):
psi = nc2c(P)
m = math.sqrt(P.size)
return (1.0 - 1.0/m)*(1.0/psi)
def betweenCollisions(P):
psi = nc2c(P)
phi = c2c(P)
m = math.sqrt(P.size)
return (1.0-phi)/psi
Now, let me consider a very simple setup
The corresponding transition matrix is
P = np.matrix([[0.5, 0.5],
[0.5, 0.5]])
and the corresponding collision probabilities are
n = 0
n = 1
n = 2
n = 3
n = 4
n = 5
n = 6
n = 7
n = 8
n = 9
n = 10
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.25
0.125
0.0625
0.0313
0.0156
0.0078
0.0039
0.002
0.001
0.0005
The first row lists the probabilities of seeing a collision at step
regardless of seeing previous
collisions. The second row lists the probabilities of seeing our first
collisions at step . The
probability of seeing a collision within 10 steps is 0.999. The expected
number of steps before we see our first collision is 1.0 and the
expected number of steps between two collisions is 1.0.
Now, let me work with a setup in which collisions are impossible
except at step .
P = np.matrix([[1.0, 0.0],
[0.0, 1.0]])
and the corresponding collision probabilities are
n = 0
n = 1
n = 2
n = 3
n = 4
n = 5
n = 6
n = 7
n = 8
n = 9
n = 10
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.5
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
Now, let me consider the graph and the probabilities I gave at the
beginning.
Let me calculate the probabilities of a collision from to .
n = 0
n = 1
n = 2
n = 3
n = 4
n = 5
n = 6
n = 7
n = 8
n = 9
n = 10
n = 11
n = 12
n = 13
n = 14
n = 15
n = 16
n = 17
n = 18
n = 19
n = 20
0.1667
0.1806
0.1875
0.1927
0.189
0.1841
0.1818
0.1821
0.1833
0.1842
0.1842
0.1839
0.1836
0.1835
0.1836
0.1837
0.1837
0.1837
0.1837
0.1837
0.1837
0.1667
0.0972
0.0859
0.0759
0.067
0.0592
0.0523
0.0462
0.0408
0.036
0.0318
0.0281
0.0248
0.0219
0.0194
0.0171
0.0151
0.0134
0.0118
0.0104
0.0092
In this situation seeing a collision at step stabilizes as expected, at 0.1837 after
about 15 steps. On the other hand, the probability of seeing our first
collision at step decreases to
zero, as it should. And the total probability of seeing a collision
during the first 20 steps is about 0.9211 . The expected number of steps
before we see our first collision is 7.1429 and the expected number of
steps between two collisions is 4.2857.