*Developed in collaboration with Andrew Curtis;
Schlumberger Cambridge Research, Cambridge CB3 0EL, England; curtis@cambridge.scr.slb.com*

The oct-tree importance sampling algorithm gives accurate, efficient and
complete mapping of earthquake location *PDF*s in 3D space (x-y-z).

Advantages:

- Much faster than grid-search (factor 1/100)
- More global and complete than Metropolis-simulated annealing
- Simple, with very few parameters (initial grid size, number of samples)

Drawbacks:

- Results are weakly dependant on initial grid size - the method may not identify narrow, local maxima in the PDF.
- Attempts to read full 3D travel-time grid files into memory, thus may run very slowly with large number of observations and large 3D travel-time grids

The oct-tree method uses recursive subdivision and sampling of cells in 3D space (*below*) to generate a
cascade of sampled cells, where the density of sampled cells follows the *PDF*values of the cell centre.

The probability that the earthquake location is in a given cell *i* is approximately,

* P _{i}*=

where *V _{i}* is the cell volume and x

The core of the method is an ordered list *L _{P}* of
probability values

The oct-tree sampling procedure is initialised by a global sampling of the full search space on a coarse,
regular grid (**B** *below*). The misfit value *g _{i}*(x) at the centre of each grid cell is
determined, the probability

Next the following steps are repeated (**C-E** *below*) until a predetermined number of evaluations of the forward problem or other termination criterion has been reached:

- The cell
*C*with the largest probability_{max}*P*(red squares_{max}*below*) is obtained from the ordered list*L*_{P} *C*is divided into 8 child-cells_{max}- The misfit and probability
*P*are calculated for each of the 8 child-cells_{i} - The 8 new cells are inserted into the ordered list
*L*according to their_{P }*P*_{i} - Repeat

This recursive procedure converges rapidly, producing an oct-tree structure of cells specifying
location PDF values in 3D space (**F** *above*). This oct-tree structure will have a larger number of
cells in the regions of higher *PDF* (lower misfit) and thus gives approximate importance sampling of
the *PDF* (**A** above).

Finally, samples in 3D drawn from the oct-tree structure (*below*) give a useful and compact representation
of the *PDF*.

The example below is illustrated by 2D projections of such 3D samples.

An exhaustive grid-search (*below, left*) shows the complete *PDF *for the location;
this *PDF *shows two distinct regions of high probability at different depths. The oct-tree
method (*right*) identifies both solution volumes and is thus more complete than a
Metropolis-simulated annealing approach (*centre*), which identifies only the deeper solution.
Both of these methods are about 100 times faster than the grid search, but only the oct-tree method
produces an image of the solution *PDF* that is nearly identical to that of the exhaustive
grid-search. The oct-tree and Metropolis-simulated annealing methods are only about 10 times
slower than standard linearised location algorithms, which are difficult or impossible to apply
with 3D models.

An image of all cell centres visited by the oct-tree method (*blow, left*) shows that this
method samples globally while producing efficient importance sampling:* i.e.* The distribution
of cell centres follows closely the distribution of samples of the final *PDF* (*right*).

The oct-tree method performs well for the earthquake location problem because it is 3D. This allows the use of the simple geometry of oct-tree division of rectangular cells: the volume of each cell is always known and it can be determined easily which cell contains a given point. The oct-tree method should be applicable in 4D, allowing a search over origin time. But in higher dimensional problems the determination of the volume of a cell and whether or not a cell contains a given point may become difficult or impossible.

The oct-tree approach can be applied to teleseismic location in a spherical earth by a) performing the location in a cubic region containing the spherical earth, or b) dividing the spherical earth into organized curvilinear cells which can be further sub-divided into 8 child cells.