| doc | licensing amend; doc | |
| other_tests | Initial commit | |
| test_out | Initial commit | |
| GraphExt.py | Initial commit | |
| InsertionSorter.py | Initial commit | |
| README.md | licensing amend; doc | |
| ShortestPathIS.py | Initial commit | |
| ShortestPathIS_run1_CMC_linear.py | Initial commit | |
| ShortestPathIS_run2_CMC_vs_ISMC_linear.py | Initial commit | |
| ShortestPathIS_run2b_CMC_vs_ISMC_linear_as_table.py | Initial commit | |
| ShortestPathIS_run3_ISMC_Rubinstein_example.py | Initial commit | |
| ShortestPathIS_test1.py | Initial commit | |
| ShortestPathIS_test2_CMC.py | Initial commit | |
Importance sampling example
This repository demonstrates the strength of importance sampling for estimating multi-dimensional integrals, here in particular a probability of a rare event (= \int 1_{\omega \in rare event} \d P).
This is in comparison with "naive" random sampling, and in comparison with analytical bounds on the same probability.
The example problem used here is of estimating the probability of obtaining a shortest path length (in a given fixed graph) in excess of a certain prespecified threshold \gamma. (applications in network planning)
This problem setting is from [1], introductory section (page 31). The graph used is
shortest path from S to T. Edges carry weights specified collectively in a vector vec_u.
License
Specific for files, see single files. Documentation files (*.txt) are CC BY-SA 4.0 licensed.
References
[1] Reuven Y. Rubinstein, Dirk P. Kroese: "The Cross-Entropy method". Springer, 2004.
[2] https://github.com/ahojukka5/Dijkstra/blob/master/dijkstra/graph.py