随机算法的概率空间 ·(SAx,Prob): SA.x ={ClC is a computation of A on x; Prob is a distribution over Sax, Probax(C):it is 1/2 to the power of the number of random bits asked in C. Prob(A(x)=y),is the sum ofall Proba(C),where Coutputs y.随机算法的概率空间 • 𝑆𝐴,𝑥, 𝑃𝑟𝑜𝑏 : • 𝑆𝐴,𝑥 = 𝐶 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴 𝑜𝑛 𝑥 ; 𝑃𝑟𝑜𝑏 𝑖𝑠 𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛 𝑜𝑣𝑒𝑟 𝑆𝐴,𝑥, • 𝑃𝑟𝑜𝑏𝐴,𝑥 𝐶 : 𝑖𝑡 𝑖𝑠 1 2 𝑡𝑜 𝑡ℎ𝑒 𝑝𝑜𝑤𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑎𝑛𝑑𝑜𝑚 𝑏𝑖𝑡𝑠 𝑎𝑠𝑘𝑒𝑑 𝑖𝑛 𝐶. • Prob(A(x) = y), is the sum of all ProbA,x (C), where C outputs y