The aim of this project is to develop a faster (random) algorithm to approximate the Gibbs measure of a BRW.
Given a sample of the branching random walk of depth
- start from the root
- consider the
$2^M$ descendents of the root at level$M$ - choose one of the descendents according to a Gibbs measure with inverse temperature
$\beta$ supported on these$2^M$ descendents - set the chosen descendent as the new root and start from step 1.
The algorithm described above will generate a probability measure
- Sample all the agents starting from the same node together. After they reach the M-th descendants, they become independent. Then we can continue the parallel computation.
- Save the sampled weights on disk via h5py for example. To do this, we may need to represent the tree by key-value pairs.
Use python3 to execute the following programs:
KL_simulation.pysimulates the trend of KL when we change the parametersempirical.pysimulates the empirical behavior of the algorithm described before.empirical_parallel.pyhas the same purposeempirical.pybut for N and M extremely large.
- Numpy
- Anytree: Node, PreOrderIter, LevelOrderIter, RenderTree
- Multiprocessing: Pool, cpu_count
- Matplotlib.pyplot
May require
- h5py for saving the tree