李雅普诺夫函数与均衡
李雅普诺夫函数与均衡
核心观念：如果能够为模型构建一个李雅普诺夫函数，那么模型必定会达到均衡。
$$
给定一个离散时间动态系统，它的转移规则由x_{t+1}=G(x_{t})组成。
$$
$$
对于实值函数F(x_{t})，如果对于所有的x_{t}，都有F(x_{t})≥M，而且存在一个A>0，那么
$$
$$
有F(x_{t+1})\leq F(x_{t})-A，如果G(x_{t})\ne x_{t}，如果对于G,F是一个李雅普诺夫函数，
$$
$$
那么从任何x0开始，必定存在一个t^，使G(x_{t^})=x_{t^*}，
即该系统会在有限时间内达到均衡
$$
逐底竞争博弈 (Race to the Bottom Game)
有N个博弈参与者，每个博弈参与者在每个时期都要提出一个支持水平，其取值范围为{0,1, …， 100}。提出了最接近平均支持水平2/3的博弈参与者可以获得那个期间的奖励。
局部多数模型
我们将局部多数模型中的李雅普诺夫函数定义为总体中的总不一致性(total disagreement)，即与相反状态的元胞相邻的所有元胞数量的总和。为了证明这个模型必定会达到均衡，我们必须先证明，如果一个元胞改变了自己的状态，那么总不一致性至少会下降一个固定的数量。
自组织活动模型
这个模型中由一群人和每个人可以选择去做的活动的集合组成。这个模型的关键假设是，每个人都更偏好不那么拥挤的活动，例如，更少人参加同一项活动意味着在健身房不用等待、在面包店和咖啡店不用排队。
定义：一个城市里，有A种活动可以参加，每一天都由L个时间段组成。在人口规模为M的城市中，每个人都要选定一个日程安排。在这里，日程安排是指这个人在L个时间段内分配L种活动（从一个更大的K种可能性的集合中）。一个人要面对的拥挤水平则设定为等于同时选择同一种活动的其他人的数量。
为了证明这个模型是收敛的，我们要证明总拥挤度(total congestion)，也就是整个人群拥挤水平的总和满足李雅普诺夫函数的条件。
⚠️ 生活的智慧：错峰出行。
纯交换经济
纯交换经济由一个消费者集合组成，每个消费者都有自己的商品禀赋和偏好。我们要先证明，总幸福感(total happiness)总是按固定数量增加并具有最大值。根据假设，任何时候，只要双方完成交易，他们的幸福水平至少会提升与交易成本相当的数量。此外，由于每个人都拥有固定的商品禀赋，因此总幸福感有一个最大值。
外部性的存在意味着我们不能直接说系统是不是会达到均衡。例如，假设伊拉克与巴基斯坦达成协议，用自己的石油去交换巴基斯坦的核武器，那么这两个国家的领导人可能会因此而觉得更加幸福，但是从全球的角度来衡量，总幸福感肯定会下降，世界上其他国家可能会对伊拉克建立核武器库深感不安。其他国家的人所感受到的这种影响被称为负外部性(negative externality)。当市场上的交易包含了负外部性时，交易就不一定能提高总幸福感了。
⚠️ 李雅普诺夫函数在交易环境中是否存在，取决于负外部性的大小。
此外，我们无法构建李雅普诺夫函数，并不意味着模型或系统肯定不能达到均衡。一个著名的例子是所谓的“取一半或乘三加一法则”(HOTPO)，它也被称为考拉兹猜想(Collatz conjecture)。对于任何一个不到2^64的数字，“取一半或乘三加一法则”都会止步于均衡。然而，没有人能够证明“取一半或乘三加一法则”是不是最后总能达到均衡。
[!NOTE] 小结
李雅普诺夫函数不仅可以帮助我们证明一个系统或模型能不能达到均衡，还可以告诉我们达到均衡的速度有多快。即便构建李雅普诺夫函数的努力遭到了失败，这种尝试也是有意义的。我们不能构建一个总是减少或总是增加的全局变量，因此，无法保证这些过程能够达到均衡。
回顾一下模型的7大用途——推理、解释、设计、沟通、行动、预测和探索，我们就会发现李雅普诺夫函数在每个用途上都有所帮助。如上所述，利用李雅普诺夫函数，我们可以推断出系统走向均衡的原因，还可以解释系统收敛到均衡的速度、设计信息系统（例如迪斯尼世界所采取的分时段游览的预约系统）、采取行动（例如对办公桌进行交易是不可取的）、沟通系统如何达到均衡的途径、预测系统达到平衡的时间以及进行探索。我们可以尝试提出假设和构建模型来解释一些令人惊讶的现象，例如自组织的城市。
马尔可夫模型
马尔可夫模型用来刻画以一定概率在一组有限的状态之间不断转换的系统。在马尔可夫模型中，状态之间转移发生的概率是固定的。如果系统可以通过一系列过渡从任何一个状态转换为任何其他状态，并且不存在简单的循环，那么马尔可夫模型就可以达到唯一的统计均衡(statistical equilibrium)。在统计均衡中，单个实体可以继续在各种状态之间移动，但是各种状态之间的概率分布仍然是固定的。
任何一个马尔可夫模型，只要状态集是有限的、不同状态之间的转移概率是固定的、在一系列转移后能够从任何一个状态变换为任何其他状态，而且状态之间不存在固定的循环，就必定会收敛到唯一的统计均衡。
这个定理意味着，如果满足这四个假设，那么改变初始状态、历史和干预措施，都不能改变长期中的均衡。
⚠️ 如果主流的政治意识形态的变动满足上述四个假设，那么历史也不能影响意识形态的长期分布。
佩龙-弗罗宾尼斯定理 (Perron-Frobenius Theorem)
一个马尔可夫模型必定收敛于一个唯一的统计均衡，只要它满足如下四个条件：
- 状态集有限：S={1, 2, …, K}。
- 固定转换规则：状态之间的转移概率是固定的，即在每个周期中，从状态A转换为状态B的概率总是等于P(A,B)。
- 遍历性（状态可达性）：系统可以通过一系列转换从任何状态到达任何其他状态。
- 非循环性：系统不会通过一系列状态产生确定的循环。
需要强调的是，从佩龙-弗罗宾尼斯定理中得出的结论不应该说明历史是不重要的，而应该是：如果历史确实是重要的，那么必定会违背模型的其中一个假设。有两个假设，即状态集有限和非循环性，几乎总是成立的。遍历性通常也能成立。状态之间的转移概率是固定的这个限制是最有可能被违背的假设。
因此，这个模型表明，如果历史确实是重要的，那么必定存在某种潜在的结构因素改变了转移概率（或者改变了状态集）
销量-耐久性悖论 (sales-durability paradox)
产品或创意的流行程度与其说取决于它们的相对销量，不如说取决于它们的耐久性。
只需要将拥有某种类型商品的人的比例设定为状态，就可以用马尔可夫模型来解释这个悖论。
销量-耐久性悖论背后的逻辑，也可以用来解释市场份额与品牌忠诚度（某人改用其他品牌的产品的可能性）之间的正相关关系。在马尔可夫模型中，更低的品牌忠诚度在均衡状态时必然意味着更低的市场份额，因为忠诚度所起的作用就像耐久性一样。这种经验规律有时也被称为“祸不单行法则”(double jeopardy law)。如果一个企业的产品的品牌忠诚度较低，那么其销售量往往也较低。
一对多的马尔可夫模型
我们可以用马尔可夫模型对身体健康演变的轨迹进行建模，方法是将不同的健康类别（如优秀、中等和糟糕等）设定为不同状态。这样的模型可以用来评估药物治疗、行为改变和手术等健康干预措施如何转移概率和均衡分布。那些能够产生更好均衡的健康干预措施是值得追求的。
马尔可夫模型还可以用于识别国际危机的不同模式，并能够用于区分会导致战争的过渡与会带来和平的过渡。
这种通过马尔可夫模型将不同模式区分出来的方法，还可以用来辨别书籍或文章的作者。只要事先已经确定了某个作者的某些已知著作，就可以估计出一个词之后出现另一个词的概率。
模型不一定能给出准确的答案。但是，这些模型确实生成了知识。我们要依靠自己的智慧做出判断：对这个模型与其他模型或直觉结论，该如何进行权衡。
网页排名(PageRank)算法
万维网由链接连接起来的网站组成，为了估计出每个站点的相对重要性，可以计算一个站点连入和接出的链接数量。
网页排名算法将每个站点都视为马尔可夫模型中的一个状态。如果两个站点共享一个链接，那么就在这两个站点之间分配一个正的转移概率。
Google公司的算法，加入了一点 - 从任何站点都能够以一个很小的随机概率移动到任何其他站点，解决了两个问题：
- 无法遍历：某些网页之间可能没链接
- 循环：某些网页之间可能互相链接
网页排名可以看作随机游走与马尔可夫模型的组合。如果将网页排名视为一种算法，就会发现可以用它来生成任何网络的排名。
[!NOTE] 小结
马尔可夫模型描述了以固定的转移概率在不同状态之间转换的动态系统。如果再假设这个过程能够在任何两个状态之间转移，并且这个过程不会产生循环，那么马尔可夫模型就可以得到唯一的统计均衡。在均衡中，人或实体在各个状态之间移动，但是各个状态的概率分布不会发生改变。由此可见，当一个过程接近均衡时，概率的变化就会减弱。用曲线图表示，就表现为曲线的斜率走平。
在应用马尔可夫模型解释现象或预测趋势时，建模者对状态的选择至关重要。状态的选择决定了这些状态之间的转移概率。
当然，并不是每个动态系统都满足马尔可夫模型的假设。在不满足马尔可夫模型假设的情况下，历史、干预政策和事件都可能会产生长期影响。
马尔可夫决策模型 (Markov decision model)
马尔可夫决策模型是对马尔可夫模型的一种修正，方法是将行动包括进来，行动会带来回报，而回报则以状态为条件，还会影响状态之间的转移概率。考虑到行动对转移概率的影响，最优行动并不一定是能够最大化即时回报的那个行动。
将一个决策问题表达为一个马尔可夫决策模型，可以告诉我们更好的行动是什么。通过考虑行动对状态的影响，我们会做出更明智的选择。