permutation entropy

Basic code

We calculate the permutation entropy of a time series by first decomposing the series into its dynamic elements. Specifically, for each moving block of length D, we characterize the block as one of D! possible sequences, using the function ordinal-idx. This function ranks the elements of the blocks. For example, a block of length D=5 would be ranked as follows:

(ordinal-idx [0 0 4 1 3]) => (0 1 3 4 2)

The output indicates that the first and second elements have the lowest state value within the block. The third value (of index 2) is the largest value within the block. The ordinal-idx output sequence is then used as a bin, and we count the number of blocks in the original time series that fall within each of the D! bins:

(defn permutation-count
  "Returns a map of the ordinal sequences of length `D` and their
  count; note that the offset is fixed at 1"
  [D ts]
  (let [subs (partition D 1 ts)]
    (frequencies (map ordinal-idx subs))))

Note that the blocks are defined as the partitions of the time series of length D, where the window advances by one element to define a new block. If there are T periods, for example, there will be T - D + 1 blocks. We map the ordinal-idx across this sequence of blocks, and the permutation-count function will return a Clojure map that associates the bin (indexed by an ordinal sub-sequence) to the number of blocks that fall within that bin. There are D! key-value pairs in the returned map:

(permutation-count 5 random-ts) => {(0 1 2 3 4) 5, (0 1 2 4 3) 6, ... }

After this, we extract the values (the frequencies) from the returned map, and use them in the final, compound function:

(defn permutation-entropy
  "Normalized permutation entropy based on the Shannon entropy
  distribution"
  [D ts]
  (let [pi-seq (to-freq (vals (permutation-count D ts)))
        scale-by (* -1 (/ 1 (i/log2 (i/factorial D))))]
    (* scale-by
       (reduce + (map log-fn pi-seq)))))

This function sums the scaled the frequencies from the permutation-count map, and then scales the summed value by the normalization factor to return the normalized Shannon entropy value.

Application to the Dow Jones Industrial Average

We have data on the Dow Jones Industrial Average (DJIA) for each day between May 26, 1896 and March 4, 2013 for a total of 29,253 observations. The normalized permutation entropy with D = 4 based on permutation-entropy is 0.9238. The raw time series is plotted below.

Suppose, now, that we split the raw time series into 365-day blocks, offset by one day. There are 28,889 blocks of 365 days within this time series. We can then apply the same function permutation-entropy with D = 4 to each of these 28,889 partitions:

The code runs in about 5 seconds. The results provide some insight into broad trends in US fiscal policy. The turmoil in the stock market during the depression is apparent, as is the steady demand for manufactured products during World War I. The deregulation during the Reagan administration in the 1980s, and during the second Bush administration is also apparent.