content_image/398329.jpg content_image/398335.jpg content_image/398336.jpg
<img src='content_image/398329.jpg'>

between paths in each bin i randomly in proportion to the path weights. This has the same effect on average of discarding the relatively unlikely paths and sharing out the weights of the relatively more likely paths; such that statistics over a given bin are not dominated by a few highly weighted paths and also such that computa- tional effort is not wasted on highly unlikely paths which contribute almost nothing to the statistics. 

Here we give a non-mathematical introduction to the procedure (see fig. 1, where symbols stand for configu- rations and lines indicate path segments) and then we motivate the method further in II D. 

Initially, configurations in each bin i with non-zero number of occupying configurations are selected with equal probability as starting points for the n 0 i paths from that bin (in the example of fig. 1 with probability 1 for the single circle in bin 1 at time=0; and probability 1/2 for each of the two circles in bin 2 at time=0). Subsequently, we take into account from which bin i a configuration in j originates (the number of branches extending from the configurations in i determines the weight of their end- points in j .) In fig. 1, the left triangle in bin 2 stems from a path with weight 1/2 (1 state divided by 2 branches), while the right triangle stems from a path with weight 1 (2 states by 2 branches). Hence, when selecting starting configurations for new shots, the left triangle in bin 2 is chosen with half the probability of the right triangle. 

We bias the sampling of trajectories towards rare events by adapting the number of shots n t i from a bin i at a time t such that sufficient statistics are produced for rare transitions (eqn. 1). However, we do not bias within a bin: when we select a sample of n t i configura- tions from the path endpoints in a given bin as starting points for new shots, we do not apply any bias. 

Selecting configurations without bias does not imply that they are drawn with equal probabilities. On the contrary, as the total number of shots n t i varies betwen bins, pathways that arrive in a bin j from different bins i, j, k . . . have different statistical weights (according to the respective values of n t − τ i , n t − τ j , n t − τ k . . . ). These 

## D. Motivation of Sampling Strategy 

weights need to be taken into account when selecting starting configurations for new shots. We now provide a detailed explanation of the procedure to do this. 

We define P $^{t}$( i ) as the proportion of configurations in bin i at time t assuming infinitely many configurations. We call the estimate of P $^{t}$( i ) from a finite number of configurations d t $_{i}$. Similarly, we define P $^{t}$( j | i ) as the pro- portion of pathways from bin i which end in j in the case of infinitely many trajectories, and its estimate as M t $_{i,j}$. As in the example of fig. 1, we begin at time t = 0 by picking configurations in bin i with equal probability as starting configurations for shots. At time t = τ we count N τ i,j pathways that went from i to j . Each of these path- ways has an equal weight P $^{τ}$( i, j ) /N τ $_{i,j}$, because they each had the same chance to be selected for shots from bin i . For the next step, we would like to pick configurations from bin j such that the probability of a configuration s τ j being picked is proportional to the weight of its path P (select : s τ $_{j}$) ∝ P $^{τ}$( i, j ) /N τ $_{i,j}$. To conveniently compute this we normalize by P ( j ) and write: 

<img src='content_image/398335.jpg'>

During the course of the simulation we do not know the values of P $^{τ}$( j | i ) and P $^{τ}$( i ). However, we do have the es- timates M τ i,j and d τ $_{i}$. As we sample within a bin without bias, the errors in d τ i (and M τ $_{i,j}$) relative to P $^{τ}$( i ) (and P $^{τ}$( j | i )) are zero-mean. Therefore all products and ratios of different errors are also zero-mean. And hence the laws of conditional probability can be applied to the estimated probabilities without introducing any bias. Therefore an estimate of the optimal P (select : s τ $_{j}$) can be defined as a function of M τ i,j and d τ $_{i}$, without introducing any bias: 

Selecting configurations for shots using P (select) in- stead of P (select) is perfectly acceptable: in a large number of repeated experiments each configuration will be selected a number of times proportional to its true P (select), and correct average properties will be ob- served. 

The central trick of the algorithm is that although the trajectories which enter a given bin do not have an equal statistical weight; those which leave a given bin do have an equal statistical weight, because their selection for shots is determined by an unbiased estimate of P (select). For this reason, the selection formula (2) can be applied at every timestep without explicitly considering the his- tories of trajectories more than one timestep into the past. 

<img src='content_image/398336.jpg'>

