文献：Song C, Qu Z, Blumm N, et al. Limits of predictability in human mobility. Science, 2010, 327(5968): 1018-1021.
地址：Limits of predictability in human mobility
A range of applications, from predicting the spread of human and electronic viruses to city planning and resource management in mobile communications, depend on our ability to foresee the whereabouts and mobility of individuals, raising a fundamental question: To what degree is human behavior predictable? Here we explore the limits of predictability in human dynamics by studying the mobility patterns of anonymized mobile phone users. By measuring the entropy of each individual’s trajectory, we find a 93% potential predictability in user mobility across the whole user base. Despite the significant differences in the travel patterns, we find a remarkable lack of variability in predictability, which is largely independent of the distance users cover on a regular basis.
1. 计算user的熵率
$X_i$是随机变量，表示在时间$i$时，user所在位置。Entropy定义为
$$
S=-\sum_{x\in X}P(x)log_2p(x)
$$
$p(x)=Pr\lbrace X=x\rbrace$。
给定$X$，随机变量$Y$的条件概率熵为
$$
S(Y|X)\equiv \sum_{x\in X}p(x)S(Y|X=x)
$$
假设$h_n$是n个locations序列的随机变量。对于平稳随机过程$\mathcal{X}={X_i}$,熵率可表示为
$$
\begin{split}
S &\equiv \lim_{n\to \infty}\dfrac{1}{n}S(X_1, X_2, \cdots, X_n)\
& = \lim_{n\to \infty}\dfrac{1}{n}\sum_{i=1}^{n}S(X_i|h_{i-1})\
& = \lim_{n\to \infty} \dfrac{1}{n}\sum_{i=1}^{n}S(i)
\end{split}
$$
如果下一时刻所处位置与当前位置无关，则有$S=-\sum_{i}p_i\log_2p_i$, $p_i$表示在位置$i$的概率。
- $S_i$: user i的真实的熵，同时包含时间和空间模式
- $S^{unc}=-\sum_{i=1}^np_i\log_2p_i$: 不考虑时间相关性
- $S^{rand}=\log_2N$: 随机熵。
显然有, $0\leq S \leq S^{unc} \leq S^{rand} \le \infty $.
2. 估计真实的熵$S$
基于Lempel-Ziv数据压缩的估计，
$$
S^{est}=\left(\dfrac{1}{n}\sum_i\Lambda_i \right)^{-1}\ln n
$$
$\Lambda_i$是从位置$i$出发的最短子串的长度，且该子串在位置1到位置$i-1$中没有出现过。当$n\to \infty$时，$S^{est}$收敛于真实熵。
应用公式（4）估计实际位置序列的熵时，获得的值依赖于序列中未知位置的比例q
序参量$\sigma(q’)\equiv \ln\dfrac{S(q’)}{S^{unc}(q’)}$, 为了准确估计$S_i=S_i(q=0)$, 采用如下的算法：
- 对于一个未知位置为$q$的序列，选择$\Delta q$的已知位置，并将其位置标记为“未知”。
- 记$q’=q + \Delta q$， $\Delta q=0, 0.05, 0.10, 0.15, \cdots, 0.9-q$, 计算序参量$\sigma(q’)\equiv \ln\left(s^{eff}(q’)\right)= \ln\dfrac{S(q’)}{S^{unc}(q’)}$ 。其中，$S(q’)$利用Lempel-Ziv算法计算，$S^{unc}(q’)$由随机打乱之后的序列，通过Lempel-Ziv算法计算。
$\sigma(q’)$与 $q’$之间存在线性关系，可以计算当 $q=0$时 $\sigma_{est}$，则 $S^{est}=e^{\sigma_{est}}S^{unc}$.
$sin{x-2y}=0$