随机的是算法的选择
在计算复杂度语境中，蒙特卡洛算法（Monte Carlo algorithm）是允许有错概率的随机算法范式：运行时间有给定界，输出则以规定概率正确。一次运行使用随机位来决定抽样、分支或其他操作。分析一般固定任意合法输入，再对算法的随机选择取概率。
这与平均情形分析不同，后者通常对输入分布作假设。不能把“多数测试样本上正确”替代“对每个输入错误概率有界”。与之相对，拉斯维加斯算法保证返回的答案正确，但运行时间受随机性影响，通常研究其期望时间或尾部概率。
单边和双边的含义
对是非判定问题，单边错误表示某一类输入绝不会被误判。例如算法对否实例总回答否，而对是实例至少以一半概率回答是。此时一旦回答是就有确定性意义；全部回答否却可能只是没找到所需见证。将是、否互换，可以得到相反方向的单边保证。
双边错误允许两类输入都被误判。典型有界错误设置要求每个输入上的正确率至少为2/3或3/4，而不是仅略高于1/2却不给出可用的优势界。具体常数通常可通过重复改进，但该改进依赖已证明的单次保证与独立性条件。
参考：[1]
重复何时能提高可信度
对于上述单边情形，独立运行k次，只要一次回答是便接受。否实例仍不会误收；是实例被连续漏掉的概率至多为(1/2)的k次方。若改成只要一次回答否就拒绝，反而可能放大漏报，因此重复的汇总方式必须与错误方向相配。
双边情形可取奇数次独立结果的多数票。作一个直接计算：若每次错误率都是1/3，独立运行三次，多数出错概率为三次中恰有两错或三错之和，即7/27，低于1/3。更一般地，固定的正确率优势可配合独立重复降低多数票错误率。重复使用同一随机选择，或各次错误高度相关，都不能直接套用独立乘法和多数票分析。
概率保证不是绝对证明
有限次运行都未发现反例，只能在算法与随机模型的前提下给出剩余风险界，不能把非零概率变成逻辑上的不可能。固定输入下的错误上界，也不是对未知输入类别的后验概率；把输出解释成“此结论有多少概率为真”还涉及另外的统计假设。
蒙特卡洛积分等数值方法同样借助抽样，但通常关心估计值与真实积分之间的偏差、方差或置信范围，而非一个是非答案是否判错。讨论实际实现时还须区分抽样误差、伪随机序列的性质和数值舍入。共同使用随机性，不意味着这些问题可以采用完全相同的正确性定义。