S1E2:Is this the correct equation? Why is there no prior?

[FrancisLau098]

位置：Session 1练习题Exercise 2: The equation currently being used for confidence is 1-(1/E)^n, where E is the number of edges in the graph, and n is the number of trials run. Is this the correct equation? Why is there no prior?

问题：题干中提到所用的表达式1-(1/E)^n与示例Graph 1不符？Graph 1的图有15条边，第一次互动时confidence显示为6.67%，即1/15。但是如果代入E=15,n=1于表达式中，结果为14/15。

我认为置信度应该为1-（1-1/E）^n。首先，代入E=15,n=1后结果为1/15，与互动结果相符；其次，这是对最狡猾的骗子prover的估计，假若骗子prover只有1条边是不符合规范的（颜色相同），其他的边都符合规范（颜色不同），那么连续n次都欺骗成功的概率是(1-1/E)^n，所以prover不是最狡猾的骗子的概率应该为1-P(连续n次都欺骗成功)即1-（1-1/E）^n。

另一方面，假若有一个拙劣的骗子prover，他只有1条边是符合规范的（颜色不同），其他的边都不符合规范（颜色相同），那么连续n次都欺骗成功的概率是(1/E)^n，那么prover不是拙劣的骗子的概率应该为1-P(连续n次都欺骗成功)即1-(1/E)^n，即题干中的表达式。

综上，我认为以拙劣的骗子作估计并不合适，宜改用最狡猾的骗子作估计。我说的对吗？

[vio1etus]

我认为你说的是对的, 我也存在这个疑问, 然后找了一些资料验证了一下, 认为置信度应该为 $1-(1-1/E)^n$。

解释:

首先，我检查了一下有15条边的 Graph 1，其前15轮的置信度变化，发现其就是公式 $1-(1-1/E)^n$, python 代码如下:

def f(n):
    result = 1-(1-1/15)**n
    return f"{100*result:.2f}%"
for i in range(1, 16):
    print(f"f({i}):{f(i)}", end="\t")

Output：

f(1):6.67%      f(2):12.89%     f(3):18.70%     f(4):24.12%     f(5):29.18%     f(6):33.90%     f(7):38.30%     f(8):42.42%     f(9):46.26%     f(10):49.84%   f(11):53.18%    f(12):56.30%    f(13):59.22%    f(14):61.94%    f(15):64.47%    %                                                              

其次，我找到了其他讲义资料验证，分别为:
cmu lecture23.pdf
cornell lecture18.pdf

摘抄的解释（详见上述讲义）:
一个最狡猾的骗子至少有一条边 $e_{i,j}$ 连接两个顶点的颜色是相同的, verifier 发现这条边的概率是 1/E。
Prob(verifier picks $e_{i,j}$） = 1/E
Prob(verifier return reject) >= Prob(verifier picks $e_{i,j}$） = 1/E
则，Prob(verifier returns accept）<= 1-1/E
那么 n 次测试之后，Prob(verifier returns accept）<= (1-1/E)^n
也就是 n 次测试之后， soundness error 被减小到了 (1-1/E)^n， 那么在 n 次测试返回 accept 后，可以信任 prover 确实拥有 secret 的置信度 = 1-soundness_error = 1-(1-1/E)^n