独家 | 使用python马尔科夫链方法建模星巴克等待时长

作者：Piero Paialunga

翻译：陈超

校对：和中华

本文约4200字，建议阅读11分钟

本文使用马尔科夫链的方法对星巴克购买咖啡的等待时长进行建模。

以下内容关于如何使用马尔科夫链计算你在星巴克咖啡的等待时长。

 

图片来自Unplash， Jon Tyson摄

我来自意大利，可以肯定的说，咖啡就是信仰。我们喝咖啡来社交，在早上喝来唤醒我们，在午餐、晚餐后也会喝咖啡。如果好久未见某个朋友，我们会说

“Vieni a prenderti un caffè”

意思是

“来喝杯咖啡吧”

我住在美国，美国人喝咖啡的方式完全不同。我上班的时候会选择将咖啡带走喝。在工作的时候喝咖啡。看电影的时候喝咖啡。美国人不喝“意式浓缩”，但是他们很享受花很长的时间喝一大整杯。此外：他们有很多种咖啡！

走进星巴克你可能会看到上百种咖啡。有黑咖啡，黑塔玛奇朵，拿铁或者星冰乐，或者是其他很多我叫不上名字的品类。

这里有很多容易制作的，也有很多复杂的咖啡。假设你在星巴克排队点咖啡，如果前面有三个人都点了黑咖啡，那你可能需要3分钟拿到你的咖啡。

然而，如果他们点了“额外鲜奶油加糖屑肉桂豆浆的焦糖玛奇朵”……那你的等待时长可能会加倍，或者至少你得多等几分钟。

所以问题是……

“我要等多久才能拿到咖啡，在此期间我可以写篇关于我要等多久才能拿到咖啡的文章吗？”

当然，我们无法获知其他人要点什么，所以这是一个概率问题（或者如果你想要一个随机过程）。所以我们该如何解决它呢？

一个可行的方法是建立马尔科夫链。或者说，我们需要一个时间依赖的马尔科夫链。

让我们来解决问题吧！

1. 理论介绍

让我们从问题的理论背景介绍和纠正错误开始。

先从最简单的例子开始。我们进入星巴克开始点单。用数学语言来说，我们可能有三种状态。

第一种状态（O）是我们点咖啡。第二种状态（M）我们已经点完了咖啡并在等待。M状态导致他们帮你做咖啡。然后你拿到咖啡并转移到离开状态（L)。这意味着你的咖啡已经做好了你也可以走了。

 

图片来自作者

好的。现在，可能的转移状态有哪些？

1） 你从点单到制作（O到M）

2） 也能从M到M（持续等待）

3） 最后你从M到L

 

图片来自作者

我们如何将其形式化呢？

1.1 关于马尔科夫链

马尔科夫链的假设是什么？具体如下：

“处入下一状态的概率仅依赖于当前状态”

例如：

在t=5的时候处入离开状态L的概率仅仅依赖于你在t=4时处于制作状态M中。

让我们将其形式化：

 

图片来自作者

在上述符号系统当中，我们在时间t时状态的概率，在空间s_t (O, M, L) 里仅依赖于我们在t-1时的状态。

在实验中我们还需要记住的是，t时刻的概率也是时间依赖的。因为，如果你已经等了5分钟，在下一分钟离开的概率就比只等待1分钟后离开的概率更大。

这意味着：

 

图片来自作者

这就是文章开头提到过的概念。

当然，星巴克不仅有我们在，也有很多其他顾客在！所以我们马上会把这个设置复杂化。但上述是一切的起点。

接下来我们正式开始！

2. 一顾客一饮品的例子

让我们从最简单的情况开始。我们知道要喝什么并且我们是咖啡店唯一的顾客。

假设我们想要一杯焦糖玛奇朵。allrecipes食谱网站说做一杯需要5分钟。假设我们需要30秒来点单和支付。所以总共等待时间可能有5分30秒。但是让我们更进一步，5分钟只是平均制作时间，一般要用4-6分钟：