# Random walks and marketing optimization

Here is a little ‘proof’ of that you increase conversion of customers if you increase the connectivity of your product and/or purchase pages.

The idea is that touchpoints are nodes in a graph and links correspond to transitions. The adjacency matrix $A_{ij}$ is also a Markov chain but this fact is not needed for the proof.

Let $p_i(t)$ be the probability that the visitor is at vertex i at time t. The probability of moving to vertex j is $1/k_j$ with $k_j$ the degree of the vertex j:

$\displaystyle p_i(t) = \sum_j \frac{A_{ij}}{k_j}p_j(t-1)$

or in matrix form

$\displaystyle p(t) = AD^{-1}\,p(t-1)$

with $p, A, D$ being the probability vector, the adjacency matrix and the diagonal matrix of degrees respectively. This equation can also be written as

$D^{-1/2} p(t) = (D^{-1/2}A D^{-1/2})(D^{-1/2}p(t-1))$

and you have to note that the matrix $H = (D^{-1/2}A D^{-1/2})$ is symmetric one. This form is similar to a standard discrete dynamical system with Hamilatonian H. In the limit of infinite time $p = p(\infty)$ we have

$p = AD^{-1}\,p$

or

$(I- AD^{-1})p = (D-A)D^{-1}\,p= \Delta D^{-1}\,p= 0$

which means that the probability vector at infinity is an eigenvector of the Laplacian with eigenvalue zero. On a one-component network there is only a single eigenvector of the Laplacian with eigenvalue zero. This zero-eigenvector is a constant vector and hence

$D^{-1}\,p = a.1$

or equivalently

$p_i = a.k_i.$

With the constant a normalizing the probability you can thus write

$p_i = \frac{k_i}{\sum_j k_j}$

and this says that the probability to find the random walker at any particular vertex is proportional to its degree. Increase the degree and you increase the chance that arbitrary usage of touchpoints leads to conversion.

There are some assumptions and remarks to make:

• the graph needs to be connected (i.e. only a single component) otherwise the statement about the unique zero-valued eigenvector is not true
• if you have isolated vertices you have degree zero and this means that $D^{-1}$ does not exist
• customers are not truly random walkers, they have some momentum towards a purchase or alike. So, the validity remains true only for the vertices within the scope of the motion. That is, the walker has an horizon (car. light-cone) corresponding to the momentum. In as far as this subset of vertices is connected the conclusion remains valid.
• the result is really what common sense would tell you but this little demonstration is part of a larger body or research related to random walks on graphs and not everything in this domain is so obvious
• how much time does it take to reach a given vertex? This is the so-called mean first-time question and there are various great results I’ll highlight in another article.
Tags: