马尔可夫链应用：房间空位的等待时间

这是一个马尔可夫链，状态空间为 {0, 1, 2, 3}，表示房间里的人数。根据题目，我们可以把状态 3 视为吸收状态，因为一旦房间里有 3 个人，就不会再有空位了。

我们可以列出转移概率矩阵 P，其中 P[i][j] 表示从状态 i 转移到状态 j 的概率：

0.5 0.5 0 0 0.25 0.5 0.25 0 0 0.25 0.5 0.25 0 0 0.25 0.75

我们可以进一步将 P 分成两部分，Q 和 R，其中 Q 是 P 的非吸收部分（即从状态 0、1、2 转移到状态 0、1、2 的概率），R 是 P 的吸收部分（即从状态 0、1、2 转移到状态 3 的概率）：

Q = 0.5 0.5 0 0.25 0.5 0.25 0 0.25 0.5

R = 0 0 0 0 0 0 0 0 0 0 0 0.25 0 0 0.75

我们可以进一步求出 Q 的基本矩阵 N，其中 N[i][j] 表示从状态 i 出发首次到达状态 j 的期望步数：

N = (I - Q)^-1 = 2 3 4 3 5 7 4 7 10

最终答案为 N[3][0]，表示从状态 3 出发首次到达状态 0 的期望步数为 4。因此，房间里通常需要等待 4 个人离开才能有空位。