注意：您不必了解近似算法即可回答此问题>
你好。我需要使用期望值来证明算法近似值。该算法采用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。有人可以帮助计算吗？
注意：您不必了解近似算法即可回答此Hello。我需要使用期望值来证明算法近似值。该算法采用{0,1,2}中的x_i \，使得i \ ...
您可以证明每个x_i在{0，1，2}上均匀分布，并且通过归纳成对独立。基本情况（n = 2）是立即发生的，归纳步骤是基于这样一个事实，即给您x_i独立于x_j（j 由于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。