如前所述，大型贝叶斯网络中精确推断的往往是指数级时间复杂度的，但是幸运的是存在许多高效近似推断方法。使用的方法是随机采样算法，也被称为蒙特卡罗算法，它能够提供近似的答案，且准确性取决于生成的样本数。该方法的工作原理是基于贝叶斯网络中的概率生成随机事件并计数这些随机事件中发现的不同答案。有了足够的样本，就可以以任意的精度恢复真实概率分布——只要贝叶斯网络中没有确定性条件分布。
蒙特卡罗算法（模拟退火算法是一个例子）已在许多科学分支中用于估计难以精确计算的量。这里主要关注应用于贝叶斯网络后验概率计算的采样。
直接采样方法
任何采样算法的基本要素都是从已知概率分布中生成样本。从没有相关证据的贝叶斯网络的随机采样过程入手。按照拓扑顺序依次采样每个变量，采样的概率分布取决于已经赋给该变量父节点的值。（由于按拓扑顺序采样，因此可以保证父节点已经有值。）
在任何采样算法中，答案都是通过计数产生的实际样本来计算的。这个符合特定事件的样本与总数的比例在极限意义下收敛于其依据采样概率的期望值，主要是应用伯努利大数定律实现频率与概率的统一。在大样本极限下的估计概率将变得逐渐精确，这样的估计被称为一致的。也就是说，事件的概率可以估计为采样过程所产生的所有完整事件中与部分事件相匹配的比例。
拒绝采样是从给定的易于采样分布中生成难以采样分布样本的通用方法，最简单形式的拒绝采样可以被用于计算后验概率。首先，它从网络指定的先验概率中生成样本。然后，它拒绝所有与证据不匹配的样本。最后，通过计数在剩余样本中的频次得到估计。
拒绝采样能够给出真实概率的一个一致估计，随着更多的样本被采集，这个估计将收敛到真实答案。每个概率估计误差的标准差与$\frac{1}{\sqrt{n}}$成正比，其中$n$是估计中使用的样本数。
现在已经知道拒绝采样收敛到正确的答案，接下来的问题是，收敛速度有多快？更准确地说，在最终的估计值以高概率接近正确答案之前，需要多少个样本？精确算法的复杂性在很大程度上取决于网络的拓扑结构——树形的网络容易，而连接稠密的网络则很难——拒绝采样的复杂性主要取决于被接受的样本的比例。该比例恰好等于证据的先验概率$P(e)$。遗憾的是，对于具有许多证据变量的复杂问题，这一比例极小，也就是说收敛速度非常慢
随着证据变量数量的增加，与证据$e$一致的样本比例将呈指数下降，因此该流程对于复杂问题不可用。对于连续值证据变量也有困难，因为产生与此类证据一致的样本的概率为 0（如果它确实是连续值）或非常小（如果它只是一个有限精度的浮点数）。显然，这可能需要很长时间，这就是拒绝采样的缺点。
重要性采样是一个通用的统计技术，它使用另一个采样于分布$Q$的样本来模拟从分布$P$中采样的结果，并通过在计数每个样本时使用修正因子$\frac{P(x)}{Q(x)}$，也称做权重，来确保答案在极限下是正确的。
在贝叶斯网络中使用重要性采样的原因很简单：希望以所有证据为条件从真实的后验分布中采样，但这通常太难了。因此，从一个简单的分布中采样并进行必要的修正。重要性采样有效的原因也很简单。令非证据变量为$Z$，如果可以直接从采样$P\left( z|e \right) $，可以构造如下的估计：
$$
\hat{P}\left( z|e \right) =\frac{N_P\left( z \right)}{N}\approx P\left( z|e \right)
$$
现在假设从$Q(z)$中采样。在这种情况下，引入修正因子：
$$
\hat{P}\left( z|e \right) =\frac{N_Q\left( z \right)}{N}\frac{P\left( z|e \right)}{Q\left( z \right)}\approx Q\left( z \right) \frac{P\left( z|e \right)}{Q\left( z \right)}=P\left( z|e \right)
$$
因此，无论使用哪个采样分布$Q$，该估计都会收敛到正确的值。（唯一的技术要求是，对任何$P\left( z|e \right) $非零的$z$，$Q(z)$也不应为零。）直观上，修正因子补偿了过采样或欠采样。至于分布$Q$的选择，总是希望它是一个易于采样并且与真实后验$P\left( z|e \right) $尽可能接近的分布，最常用的方法是似然加权，算法伪码如下：
称这个算法产生的采样分布为$Q_{WS}$。如果非证据变量是$Z=\left\{ Z_1,…,Z_{\ell} \right\} $，则有：
$$
Q_{WS}=\prod_{i=1}^{\ell}{P\left( z_i|parents\left( Z_i \right) \right)}
$$
因为每个变量都以其父变量为条件进行采样。为了完成算法，需要知道如何计算每个从$Q_{WS}$生成的样本的权重。根据重要性采样的思想，其权重应为：
$$
w\left( z \right) =P\left( z|e \right) /Q_{WS}\left( z \right) =\alpha P\left( z,e \right) /Q_{WS}\left( z \right)
$$
$$
=\alpha \frac{\prod_{i=1}^{\ell}{P\left( z_i|parents\left( Z_i \right) \right)}\prod_{i=1}^m{P\left( e_i|parents\left( E_i \right) \right)}}{\prod_{i=1}^{\ell}{P\left( z_i|parents\left( Z_i \right) \right)}}
$$
$$
=\alpha \prod_{i=1}^m{P\left( e_i|parents\left( E_i \right) \right)}
$$
因此，权重是证据变量在给定其父变量之后的条件概率的乘积。（证据的概率通常被称为似然，似然加权因此得名。）权重计算是在$Weighted$-$Sample$中增量地实现的，算法在每次遇到一个证据变量时乘以其条件概率，归一化是在最后返回查询结果之前完成的。
总的来说，重要性采样的算法过程为：
1、初始化权重向量，每个可能观测值对应一个权重；
2、进入单次采样，初始权重为$w=1$，按照拓扑排序遍历贝叶斯网络；若当前遍历为证据遍历$e_i$，则更新$w$为$w=w\cdot P\left( E_i=e_{ij}|parents\left( E_i \right) \right) $；否则随机采样一个值构成样本；
3、结束单次采样，更新权重向量对应位置的值，若采样未结束重复步骤 2；否则归一化权重向量并返回。
因为似然加权使用了所有的生成样本，它比拒绝采样更高效。但是，随着证据变量数量的增加，它的性能会下降。这是因为大多数样本的权重都很低，因此加权估计将由赋予证据大于无穷小的可能性的极小部分样本所主导。如果证据变量出现在“下游”，即出现在变量顺序的靠后部分，那么这个问题就会加剧，因为非证据变量在其父变量和祖先变量中没有证据来指导样本的生成。这意味着这些样本将仅仅是纯粹的模拟——与证据所隐含的现实几乎没有相似之处。
通过马尔可夫链模拟进行推断
马尔可夫链蒙特卡罗（$MCMC$）算法的工作方式不同于拒绝采样和似然加权，$MCMC$算法通过随机修改之前的样本来生成样本，而不是从头生成每个样本。可以将$MCMC$算法想象成处于特定的当前状态，该状态为每个变量指定一个值，并通过对当前状态进行随机修改来生成下一状态。
马尔可夫链指产生一系列状态的随机过程。
贝叶斯网络的吉布斯采样算法从一个任意状态出发（证据变量固定为它们的观测值），通过为一个非证据变量$X_i$随机采样一个值来生成下一个状态。给定马尔可夫毯时$X_i$独立于所有其他变量。因此，$X_i$的吉布斯采样意味着以它的马尔可夫毯中变量的当前值为条件进行采样。该算法在状态空间（可能的完整赋值的空间）中游走，每次调整一个变量，并保持证据变量不变。
具体可以描述为，首先随机生成一个符合证据的事件样本；接下来在单次采样中将非证据变量$Z_i$根据用于选择变量的概率分布$\rho \left( i \right) $按照一些随机顺序进行重复采样；选中$Z_i$后依$P\left( Z_i|mb\left( Z_i \right) \right) $采样$Z_i$，最终得到一个事件样本；通过多次采样后归一化样本向量。
其中$mb\left( Z_i \right) $表示$X_i$的马尔可夫毯变量$MB(X_i)$的值，$P\left( Z_i|mb\left( Z_i \right) \right) $的计算方法为：
$$
P\left( x_i|mb\left( X_i \right) \right) =\alpha P\left( x_i|parents\left( X_i \right) \right) \cdot \prod_{Y_j\in Children\left( X_i \right)}{P\left( y_j|parents\left( Y_j \right) \right)}
$$
吉布斯采样实现了后验概率的一致估计。基本的观点是直截了当的：吉布斯采样过程的平稳分布正是基于证据的非证据变量的后验分布。吉布斯采样过程从一个状态转移到另一个状态的特殊方式具有这种非凡的特性。
每个吉布斯采样步骤都涉及对所选变量$X_i$的马尔可夫毯分布的计算，这需要与$X_i$的子变量数量和$X_i$的值域大小成比例的乘法运算数量。这一点很重要，这意味着生成每个样本所需的工作量独立于网络的规模。
吉布斯采样的复杂性比拒绝采样和似然加权更难分析。首先要注意的是，与似然加权不同，吉布斯采样关注下
游证据。信息从证据节点向各个方向传播：首先，证据节点的任何邻居节点的对证据节点中反映了证据的值采样；然后，对它们的邻居采样，等等。因此，当证据主要集中在下游变量时，事实证明，吉布斯采样的表现优于似然加权。
吉布斯采样的收敛速率，即算法定义的马尔可夫链的混合速率，强烈依赖于网络中条件分布的定量性质。如果存在确定性关系，则会打破了收敛要求的遍历性；但是，如果让这个关系是近似确定的，则算法仍能收敛，但收敛的速度可能是任意缓慢的。
有几种修正的方法可以帮助$MCMC$算法更快地混合。一种方法称为块采样：同时采样多个变量。这种情况下，以它们的联合马尔可夫毯为条件，联合采样$Cloudy$和$Rain$。另一种方法是更明智地生成后续状态，即“米特罗波利斯-黑斯廷斯采样”。
米特罗波利斯-黑斯廷斯（$MH$）采样可能是应用最广泛的$MCMC$算法。与吉布斯采样一样，$MH$被设计用来根据目标概率$\pi \left( x \right) $最终生成样本$x$。在贝叶斯网络推断的场景中，希望得到$\pi \left( x \right) =P\left( x|e \right) $。与模拟退火算法相似，$MH$在采样过程的每次迭代中有两个阶段：
1、给定当前状态$x$，从提议分布$q\left( x’|x \right) $中采样一个新状态$x’$。
2、根据接受概率概率性地接受或者拒绝$x’$。如果这个提议被拒绝了，状态维持在$x$：
$$
a\left( x’|x \right) =\min \left( 1,\frac{\pi \left( x’ \right) q\left( x|x’ \right)}{\pi \left( x \right) q\left( x’|x \right)} \right)
$$
$MH$的转移核由这两步过程组成。注意，如果提议被拒绝，那么链将保持相同的状态。顾名思义，提议分布负责提议下一个状态$x’$。例如，$q\left( x’|x \right) $ 可以如下定义：
以$0.95$的概率执行一步吉布斯采样生成$x’$；否则，执行重要性采样算法生成$x’$。
这个提议分布导致$MH$执行大约$20$步吉布斯采样，然后从一个新状态（假设它被接受）“重启”这一过程。这种策略能解决吉布斯采样陷入一部分状态空间而无法到达其他部分的问题。关于$MH$值得注意的是，对于任何提议分布，只要得到的转移核是遍历的，就可以保证收敛到正确的平稳分布。
