The Kitchen Sink and Other Oddities

Atabey Kaygun

Collisions in random walks

Description of the problem

Imagine we have a directed graph in which each edge connecting a vertex a to another vertex b is labelled by the probability of jumping from a to b. 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 n?

An Unsatisfactory Solution

Assume we have m possible states labelled by 1,,m, and let pij denote the probability of jumping from state i to step j. If I form the transition matrix P=(pij) the entries of Pn=(aij) calculate the probability of jumping from state i to state j in n-steps. Then the probability of having a collision at step n at a state k is aikajk if one particle starts at state i and the other starts at j. If I would consider only the collision probability then pn(i,j)=k=1maikajk where, again, (aij) denote Pn the entries of the n-th power of the transition matrix. A better way of writing the same equality goes through the observation that pn(i,j)=k=1maikajk=k=1maikakjt where we use (aijt) to denote the entries of the transpose (Pt)n. In other words pn(i,j) is the (i,j)-th entry in the matrix Pn(Pt)n. 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 pn of a collision at step n is the sum of all entries of the matrix Pn(Pt)n divided by m2: pn=1m2i,j,kaikaik Division by m2 happens because I assume all initial positions are assumed to be equally likely.

In most cases, Pn stabilizes as n goes to , and therefore the probability pn also stabilizes. As Pn stabilizes, the rows of the stabilized matrix become the 1-eigen vector of P. If that vector is $ < u_1,,u_m> $ then the stable collision probability is i=1mui2. 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 n, and does not care if we have a collision before the step n. 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 A and B in V, and let us try to find the probability of jumping from the combined state A to the combined state B. Recall that pij is a conditional probability: the probability of jumping to state j given that we are at state i. So, the conditional probability of jumping to state B from state A is iAjBp(i)pijiAp(i) where p(i) stands for the proability of being at state i. If we assume that p(i)=1m, that is, every state is equally likely, then pAB=1mjBiApijAm=1AiAjBpij Now, observe that for a pair of particles, the product pi1j1pi2j2 measures the conditional probability of the pair jumping respectively to the states i2 and j2 from states i1 and j1. Then the conditional probability of jumping into a collision state from a collision state is P(CC)=1mi1=j1i2=j2pi1i2pj1j2=1mi,jpij2 From a non-collision state to a collision state

For notational simplicity, I will use Ψ for P(CNC) and Φ for P(CC). Then the probability of jumping from a collision state to a non-collision state P(NCC)=1P(CC)=1Φ and finally from a non-collision state to a collision state P(NCNC)=1P(CNC)=1Ψ Let qn denote the probability of seeing our first collision at step n. Then qn=(11m)(1Ψ)n1Ψ Then the expected number of steps before we see our first collision is n1nqn=(11m)Ψn1n(1Ψ)n1 The last terms should be familiar from your calculus classes: it is the derivative of the power series n=0xn=11x evaluated at x=1Ψ. This is 1Ψ2, and therefore, the expected number of steps for seeing a first collision is (11m)1Ψ

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 hn to denote probability of that happening at step n. This is the conditional probability of seeing the first collision at step n given that we start with a collision state. For n=1 we have h1=P(CC)=Φ. And for n2 hn=(1Φ)(1Ψ)n2Ψ Then the expected number of steps between two collision becomes E=(1Φ)Ψn2(n1)(1Ψ)n2=(1Φ)Ψn1n(1Ψ)n1 Again the series is the derivative of the function 11x evaluated at 1Ψ. Then E=(1Φ)Ψ

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 n regardless of seeing previous collisions. The second row lists the probabilities of seeing our first collisions at step n. 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 n=0.

 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.

 P = np.matrix([[0.5, 0.5, 0.0, 0.0, 0.0, 0.0],
               [0.0, 0.0, 0.5, 0.5, 0.0, 0.0],
               [0.0, 0.0, 0.5, 0.0, 0.0, 0.5],
               [0.0, 0.0, 0.0, 0.5, 0.5, 0.0],
               [0.5, 0.0, 0.0, 0.0, 0.5, 0.0],
               [0.5, 0.0, 0.0, 0.0, 0.0, 0.5]])

Let me calculate the probabilities of a collision from n=0 to n=20.

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 n stabilizes as expected, at 0.1837 after about 15 steps. On the other hand, the probability of seeing our first collision at step n 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.