# How to use Markov Chain to calculate attribution worth of a state?

I am trying to model a user's behavior through an app and have come across the idea of Markov Chains to do the modeling. A similar problem in marketing seems to be the multi-channel attribution problem. What I don't quite understand is how to attribute the positive outcome's result to each node along the way since my paths can be bidrectional.

In the image above, how do I attribute the purchase conversion to the Notification Center with markov chains? I've tried to see if there was a removal effect, but since the node itself doesn't touch the conversion path directly, it doesn't seem to change. Is the attribution of it just 0 then?

• Just a question to clarify what you mean by "attribution": The attribution of the Store in this would be 10% and the the attribution of Social would be 5%, is that correct? – Denwid Mar 23 '18 at 7:20
• Right, landing in Store results in a 10% purchase conversion. So all traffic driven into Store, no matter the path, culminates in a 10% purchase conversion worth x dollars. The question I have is now how do I go another step back and try to attribute Notification Center (NC). If I use the traffic driven into the Store directly from NC and attribute it proportionally, I feel like I lose attributing any traffic that the NC might drive to Social and then finally back to the Store. How to deal with these and bidrectional loops is what confuses me. – cvax Mar 23 '18 at 7:25

To calculate the attribution of a node $N$ one can calculate the Removal Effect, i.e. the probability of a Purchase if the node $N$ "didn't exist" (= Exit note). This can be done by

1. setting the outgoing transition probabilities of $N$ to 0 except for the transition to Exit, which is set to 1: $P(\text{Exit}|N) = 1$.
2. calculate the resulting probability to purchase $P(\text{Purchase}|\text{Open App})$
3. and comparing with the case where the node operates normally.

Let's do this...

The node transition matrix $\underline{P}$ now looks as follows:

$$\scriptsize{ \begin{matrix} {} & Open App & Social & Store & Notification Center & Exit & Purchase \\ Open App & 0.0 & 0.00 & 0.0 & 0.0 & 0.0 & 0.0 \\ Social & 0.5 & 0.00 & 0.4 & 0.0 & 0.0 & 0.0 \\ Store & 0.5 & 0.30 & 0.0 & 0.0 & 0.0 & 0.0 \\ Notification Center & 0.0 & 0.15 & 0.1 & 0.0 & 0.0 & 0.0 \\ Exit & 0.0 & 0.50 & 0.4 & 1.0 & 1.0 & 0.0 \\ Purchase & 0.0 & 0.05 & 0.1 & 0.0 & 0.0 & 1.0 \\ \end{matrix} }$$

Calculate resulting probability of a purchase

Define $\vec \pi$ as the initial state vector (100%, 0, 0, 0, 0, 0) in the order of the above columns, i.e. at the start all the money is in the Open App node. Then we calculate the probabilities after a long time has passed (e.g. 1000 times steps). This yields $$\vec\pi \underline P^{1000} = (0, 0, 0, 0, 0.0, 88.6\%, 11.4\%)$$

Compare with default case This without sending everything from Notification Center directly to Exit, the chain yields $$\vec\pi \underline P_{default}^{1000} = (0, 0, 0, 0, 0.0, 86.3\%, 13.7\%)$$

Accordingly, we can now argue that out of 100\$that could potentially be spent in purchases, 2.3\$ would "get lost" if the Notification Center didn't exist (13.7\$minus 11.4\$).

• Thanks @Denwid. I've been reading around this literature too. It seems the Removal Effect makes a pretty strong assumption that traffic going one way would strictly be redirected to the exit. In reality though, through a user journey through the app, if they were going to a certain node that doesn't exist, I would expect them to just go somewhere different in the app as opposed to going strictly to the exit. Seems like a really big assumption being made, but I guess this is still better than nothing. – cvax Mar 24 '18 at 8:02
• I you believe a weaker assumption would be better, you could just replace the Notification Center column in P accordingly, e.g. set Exit to only 50pct and distribute the other 50pct evenly among the other nodes: pi = (0, 0.5/3, 0.5/3, 0, 0.5, 0.5/3). – Denwid Mar 24 '18 at 10:33

Since the attribution to the Store is the probability P(Purchase|Store), the corresponding attribution for the Notification Center is P(Purchase|Notification Center) and with the chain rule this can be decomposed as P(Purchase|Store)*P(Store|Notification Center) + P(Purchase|Social)*P(Social|Notification Center).

Plugging in the numbers thus yields 0.1*0.35+0.05*0.55 which is 0.0625 or 6.25%.

The nice things about Markov chains is exactly that you don't have to worry about loops, since the probabilities are always depending only on the previous state.

• So the chain rule you used is adding these paths: NC --> Store --> Purchase, NC --> Social --> Purchase. Somehow these paths are baked into that probability too? NC --> Store --> Social --> Purchase, NC --> Social --> Store --> Purchase – cvax Mar 23 '18 at 8:03
• Yes. That's the Markov property. Once you're at Store your probability to end up at Purchase is always the same (0.1). – Denwid Mar 23 '18 at 8:07
• Makrov Property intuitively says it doesn't matter where you came from or looped a 1000 times before. – Denwid Mar 23 '18 at 8:10
• Okay, to clarify, if we put dollar values to it. 10% Store purchase conversions, 5% Social conversions totalling $100. Store = 0.1 / (0.1 + 0.05) *$100 = $66.67. Social = 0.05 / (0.1 + 0.05) *$100 = $33.33. NC = .0625 / (0.1 + 0.05) *$100 = $41.67? – cvax Mar 23 '18 at 8:13 • Unfortunately you can't propagate it back this way. Dividing 6.25% by 0.15 doesn't yield anything useful. The 6.25% simply tell you the probability of a purchase once the user is in the Notification Center. Sorry I didn't get that you wanted to propagate 100$ back through the chain. – Denwid Mar 23 '18 at 10:19