4
$\begingroup$

Take for example a walk such as:

["school", "work", "home", "kindergarten", "home", "school", ...]

# or simply
[1, 2, 3, 4, 3, 1, ...]

What's the correct way of computing its entropy?

My current approach is to just count how many times each unique step is taken, compute the step-probabilities by normalizing, and then plug that into the Shannon entropy equation. Here's a small Python example:

import numpy as np
from collections import Counter

def time_correlated_entropy(walk):
    counter = Counter(zip(walk[:-1], walk[1:]))
    P = np.array(counter.values(), float) / np.sum(counter.values())
    return - sum(P * np.log2(P))

It gives sensible results, but I have no idea whether this is the right way, because I have no literature to hold it up against.

Improve this question
$\endgroup$
8
  • $\begingroup$ "Right way" must be understood with respect to a purpose: what are you hoping this calculation will tell you about a "walk"? $\endgroup$
    – whuber ♦
    Commented Mar 29, 2016 at 13:40
  • $\begingroup$ Thanks for asking @whuber. Say, the walk belongs to a man, and I would like to measure how geospacially unpredictable this man is based on the stops he make. The chronological list of stops is his walk. $\endgroup$
    – Ulf Aslak
    Commented Mar 29, 2016 at 13:42
  • $\begingroup$ I would be concerned about the possibility that your calculations give arbitrary results. Two aspects of the walk description suggest this is a risk: (1) it does not appear to distinguish the lengths of segments, so a very short segment (of little "geospatial" consequence) would be treated as the same as a very long one and (2) it depends on the detail or resolution with which you describe the walk: as the amount of detail increases, so does the entropy of the description. Are you sure that entropy is a good measure of "unpredictability" in your application? $\endgroup$
    – whuber ♦
    Commented Mar 29, 2016 at 13:49
  • $\begingroup$ Valid point. What I expected to capture by treating state-transitions as states with a probability, was low entropy for the "home" -> "school" -> "home" -> "school" type people, and high entropy for the people with complex state-transition patterns. $\endgroup$
    – Ulf Aslak
    Commented Mar 29, 2016 at 13:55
  • $\begingroup$ Provided you are clear about the definition and interpretation, it's an interesting approach. I recall answering a related question at stats.stackexchange.com/questions/25235 . By taking some care to weed out unrelated questions, a search of this site turns up a few promising answers. $\endgroup$
    – whuber ♦
    Commented Mar 29, 2016 at 14:16

1 Answer 1

Reset to default
6
$\begingroup$

The unpredictability in your problem is very much related to the entropy rate generated by the state transitions. I suggest you have a look at the topic "computational mechanics", which addresses information-theoretic questions in stochastic processes (see e.g. http://arxiv.org/abs/cond-mat/0102181)

Think of it in the following way: a random sequence of length $L$ has entropy $H(L)$, thus the entropy rate is $h=\lim_{L\rightarrow \infty} H(L)/L$. In this case, your walker generates $h$ bits of information per step.

If you want to be a bit more fine-grained, compute also the excess entropy, which is $\lim_{L\rightarrow \infty} H(L)-h L$ which captures the amount of information you need to acquire in order to synchronize with the process.

Your example of a predictable walker gives $h=0$ and $E=1$, because as soon as you have one bit (home or work) you are fully synchronized with him, and he becomes fully predictable.

Sorry that I don't write the code. I'm still learning...

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.