algorithm - 近似算法-使用期望

Question

注意:你不需要理解近似算法来回答这个问题

你好。
我需要用期望来证明一个算法的近似。
该算法取x_i \in {0,1,2}这样 i\in 1,...n+2并且有常量 c_i \in 0,1,2这样 i\in 1,...,n并希望找到对变量的赋值，使得 x_i +x_(i+1)+x_(i+2) != 0 \mod(3)对于所有 i这样的索引数量 x_i +x_(i+2) = c_i \mod(3)被最大化。
它执行以下操作:
选择x_1 , x_2 \in 0,1,2独立且随机地一致，然后
每个i\in 3,...,n+2给出 x_(i-2),x_(i-1) 的值分配给 x_i {b\in 0,1,2 | x_(i-1)+x_(i-2)+b != 0 \mod(3)} 中的两个值之一均匀随机。
分配给每个x_i对所有人都是独立的x_j这样的j<i-2 .

我需要证明这个算法给出了 1/3对所描述问题的近似，使用期望(意味着证明对于我们分配给这个问题的一些 X 随机变量，E[X]=1/3)
我正在努力定义这样的 X 并计算它，我一直得到 2\3 而不是 1\3。
谁能帮忙计算一下？

Answer 1

您可以通过归纳证明每个 x_i 均匀分布在 {0, 1, 2} 上并且成对独立。基本情况 (n=2) 是直接的，归纳步骤遵循这样一个事实，即您给出的 x_i 独立于 x_j(j < i-2)，以及一个简单的案例枚举。

结果随即而来，因为 P(x_i + x_{i+2} = c_i) 是 1/3，并且根据线性期望，E[X] = n/3。

澄清最后一个陈述:如果 x_i + x_{i+2} = c_i，设 V_i 是一个随机变量，使得 V_i 为 1。否则，V_i 为 0。则 X = sum(V_i i=1..n)，并且 E[X] = sum(E[V_i] i=1..n) 通过线性期望。然而，E[V_i] = P(x_i + x_{i+2} = c_i) = 1/3。