# Transfer entropy calculation

My question is about the interpretation of the summation in the formula.

The transfer entropy from process Y to process X can be calculated using the following formula:

$t(x|y) = \displaystyle\sum_{x_{n+1}, x_{n}, y_{n}} p(x_{n+1}, x_{n}, y_{n}) \cdot \log \left( \frac{p(x_{n+1}|x_{n},y_{n})}{p(x_{n+1}|x_{n})} \right)$

For given time series $x, y$ each having $n$ elements, is it correct that the summation comprises $(n-1)$ tuples $(x_{i+1}, x_i, y_i)$ as follows:

$(x_{2}, x_{1}, y_{1}), (x_{3}, x_{2}, y_{2}), \cdots (x_{n}, x_{n-1}, y_{n-1}),$

Or how should I interpret the summation over the states of the two processes?

For given time series $x, y$ each having $n$ elements, is it correct that the summation comprises $(n−1)$ tuples $(x_{i+1},x_i,y_i)$.

Not quite. That sum is actually over the different states of the variables involved. For example, if both $X$ and $Y$ are binary variables, then the summation will have $2^3 = 8$ terms. In general, if $X$ and $Y$ have $k$ possible states, the summation will have $k^3$ terms.

The interpretation of the sum over states is not that different from the usual sum over states when calculating entropy or mutual information. The term $(x_{n+1}, x_n, y_n)$ represents how much information the particular state $y_n$ provides about the particular state $x_{n+1}$ of the future of $X$ when the past state of $X$ is $x_n$. For more information you can read Joe Lizier's work on local information measures.

The source of your confusion could be that if you want to estimate transfer entropy from a given time series, then you (typically) have to loop through the whole time series to estimate $p(x_{n+1}, x_n, y_n)$, usually by counting occurrences of all $(x_{n+1}, x_n, y_n)$ tuples. Then, once you have estimated your PDF, you have to go back to the $t(x|y)$ formula and calculate those $k^3$ terms I mentioned above.

As Pedro says, the TE as defined in your equation has a sum over the possible states of the source, target past and target next value. And as he says, you:

1. loop through all of the time series once to fill out the histograms for the PDF, and then
2. sum over all of the possible states to compute the average log ratio.

What I want to add is that the second step (summing over all possible states) could be done in an alternative fashion by summing over all of the $N-1$ samples (for time series length $N$, and an embedding length 1) as you begin to suggest, and as is done in our 2008 paper that Pedro cites. What is important to realise is that this does slightly change the maths. As Pedro notes, the maths as you have defined above is only correct for summing the log terms over all possible states; as you see for that option you multiply each log term by the probability of that state (as per equation (4) of that paper of ours). Alternatively, if you sum the log terms over the data samples at each time point $n$, then you instead multiply the log term (for each sample) by $1/(N-1)$ (where $N-1$ is the total number of samples you have from a time series of length $N$ when using an embedding history length of 1). The multipliers are different because you have several data points corresponding to each possible state combination. We show how to map between the first option (your equation above) and the second option (my equation following) in equations (5)-(8) of our paper above.

$$T_{Y \rightarrow X} = \sum_{n=1}^{N-1}{ \frac{1}{N-1} \log_2{\frac{p(x_{n+1}|x_n,y_n)}{p(x_{n+1}|x_n)}}}$$

Another key point is that only discrete/discretised/symbolic estimators allow you to do the first option (summing log terms over configurations) in code (and you could do the second option for them if you wanted to). But for continuous valued data (e.g. with kernel estimator or KSG), you do it in code by summing over every sample (the second option, but not the first). I clarified this in section 2.2.3 of my thesis.