Abstract
Statistical Model Checking (SMC) becomes imprac-tical for hazards with probabilities as small as 10−9. Importance Sampling (IS) can help, but its effectiveness hinges on a good sampling distribution. We present a symbolic-simulation method that constructs such a distribution for Discrete-Time Markov Chains (DTMCs) used in model-based safety assessment. First, we partition all first-passage executions to the hazard into Path-Influence Regions (PIRs), repair-aware classes induced by minimal critical failure mode sets. For each PIR, we encode cut sequences with Bounded Model Checking (BMC) and use Opti-mization Modulo Theories (OMT) to synthesize two probabilistic extremal witnesses (most and least likely). We then solve a convex fitting problem over locally normalized IS weights to equalize (or tightly bound) the likelihood ratios on these extremals, which by affinity controls the entire PIR and is sufficient for computing the optimal distribution. The resulting estimator is unbiased and, under mild conditions, enjoys Bounded Relative Error (BRE) for which we provide a proof sketch and rare-event preliminaries. In experiments on nine benchmarks, our method improves accuracy, reduces relative error, and increases robustness compared to IS baselines (PLASMA and PathZVA), especially for large models and long horizons.