International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 102-106   | 1 | 2 |

## Section 1.3.4.5.2. Application to probability theory and direct methods

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

#### 1.3.4.5.2. Application to probability theory and direct methods

| top | pdf |

The Fourier transformation plays a central role in the branch of probability theory concerned with the limiting behaviour of sums of large numbers of independent and identically distributed random variables or random vectors. This privileged role is a consequence of the convolution theorem and of the moment-generating' properties which follow from the exchange between differentiation and multiplication by monomials. When the limit theorems are applied to the calculation of joint probability distributions of structure factors, which are themselves closely related to the Fourier transformation, a remarkable phenomenon occurs, which leads to the saddlepoint approximation and to the maximum-entropy method.

#### 1.3.4.5.2.1. Analytical methods of probability theory

| top | pdf |

The material in this section is not intended as an introduction to probability theory [for which the reader is referred to Cramér (1946), Petrov (1975) or Bhattacharya & Rao (1976)], but only as an illustration of the role played by the Fourier transformation in certain specific areas which are used in formulating and implementing direct methods of phase determination.

 (a) Convolution of probability densities The addition of independent random variables or vectors leads to the convolution of their probability distributions: if and are two n-dimensional random vectors independently distributed with probability densities and , respectively, then their sum has probability density given byi.e. This result can be extended to the case where and are singular measures (distributions of order zero, Section 1.3.2.3.4) and do not have a density with respect to the Lebesgue measure in . (b) Characteristic functions This convolution can be turned into a simple multiplication by considering the Fourier transforms (called the characteristic functions) of , and , defined with a slightly different normalization in that there is no factor of in the exponent (see Section 1.3.2.4.5), e.g.Then by the convolution theoremso that may be evaluated by Fourier inversion of its characteristic function as(see Section 1.3.2.4.5 for the normalization factors). It follows from the differentiation theorem that the partial derivatives of the characteristic function at are related to the moments of a distribution P by the identitiesfor any n-tuple of non-negative integers . (c) Moment-generating functions The above relation can be freed from powers of i by defining (at least formally) the moment-generating function:which is related to by so that the inversion formula readsThe moment-generating function is well defined, in particular, for any probability distribution with compact support, in which case it may be continued analytically from a function over into an entire function of n complex variables by virtue of the Paley–Wiener theorem (Section 1.3.2.4.2.10). Its moment-generating properties are summed up in the following relations: (d) Cumulant-generating functions The multiplication of moment-generating functions may be further simplified into the addition of their logarithms:or equivalently of the coefficients of their Taylor series at , viz:These coefficients are called cumulants, since they add when the independent random vectors to which they belong are added, and log M is called the cumulant-generating function. The inversion formula for then reads (e) Asymptotic expansions and limit theorems Consider an n-dimensional random vector X of the formwhere the N summands are independent n-dimensional random vectors identically distributed with probability density P. Then the distribution of X may be written in closed form as a Fourier transform:whereis the moment-generating function common to all the summands. This an exact expression for , which may be exploited analytically or numerically in certain favourable cases. Supposing for instance that P has compact support, then its characteristic function can be sampled finely enough to accommodate the bandwidth of the support of (this sampling rate clearly depends on n) so that the above expression for can be used for its numerical evaluation as the discrete Fourier transform of . This exact method is practical only for small values of the dimension n. In all other cases some form of approximation must be used in the Fourier inversion of . For this purpose it is customary (Cramér, 1946) to expand the cumulant-generating function around with respect to the carrying variables t:where is a multi-index (Section 1.3.2.2.3). The first-order terms may be eliminated by recentring around its vector of first-order cumulantswhere denotes the mathematical expectation of a random vector. The second-order terms may be grouped separately from the terms of third or higher order to givewhere is the covariance matrix of the multivariate distribution P. Expanding the exponential gives rise to a series of terms of the formeach of which may now be subjected to a Fourier transformation to yield a Hermite function of t (Section 1.3.2.4.4.2) with coefficients involving the cumulants κ of P. Taking the transformed terms in natural order gives an asymptotic expansion of P for large N called the Gram–Charlier series of , while grouping the terms according to increasing powers of gives another asymptotic expansion called the Edgeworth series of . Both expansions comprise a leading Gaussian term which embodies the central-limit theorem: (f) The saddlepoint approximation A limitation of the Edgeworth series is that it gives an accurate estimate of only in the vicinity of , i.e. for small values of E. These convergence difficulties are easily understood: one is substituting a local approximation to log M (viz a Taylor-series expansion valid near ) into an integral, whereas integration is a global process which consults values of log M far from . It is possible, however, to let the point t where log M is expanded as a Taylor series depend on the particular value of X for which an accurate evaluation of is desired. This is the essence of the saddlepoint method (Fowler, 1936; Khinchin 1949; Daniels, 1954; de Bruijn, 1970; Bleistein & Handelsman, 1986), which uses an analytical continuation of from a function over to a function over (see Section 1.3.2.4.2.10). Putting then , the version of Cauchy's theorem (Hörmander, 1973) gives rise to the identityfor any . By a convexity argument involving the positive-definiteness of covariance matrix Q, there is a unique value of τ such thatAt the saddlepoint , the modulus of the integrand above is a maximum and its phase is stationary with respect to the integration variable s: as N tends to infinity, all contributions to the integral cancel because of rapid oscillation, except those coming from the immediate vicinity of where there is no oscillation. A Taylor expansion of log to second order with respect to s at then givesand henceThe last integral is elementary and gives the saddlepoint approximation':whereand where This approximation scheme amounts to using the conjugate distribution' (Khinchin, 1949)instead of the original distribution for the common distribution of all N random vectors . The exponential modulation results from the analytic continuation of the characteristic (or moment-generating) function into , as in Section 1.3.2.4.2.10. The saddlepoint approximation is only the leading term of an asymptotic expansion (called the saddlepoint expansion) for , which is actually the Edgeworth expansion associated with .

#### 1.3.4.5.2.2. The statistical theory of phase determination

| top | pdf |

The methods of probability theory just surveyed were applied to various problems formally similar to the crystallographic phase problem [e.g. the problem of the random walk' of Pearson (1905)] by Rayleigh (1880, 1899, 1905, 1918, 1919) and Kluyver (1906). They became the basis of the statistical theory of communication with the classic papers of Rice (1944, 1945).

The Gram–Charlier and Edgeworth series were introduced into crystallography by Bertaut (1955a,b,c, 1956a) and by Klug (1958), respectively, who showed them to constitute the mathematical basis of numerous formulae derived by Hauptman & Karle (1953). The saddlepoint approximation was introduced by Bricogne (1984) and was shown to be related to variational methods involving the maximization of certain entropy criteria. This connection exhibits most of the properties of the Fourier transform at play simultaneously, and will now be described as a final illustration.

• (a) Definitions and conventions

Let H be a set of unique non-origin reflections h for a crystal with lattice Λ and space group G. Let H contain acentric and centric reflections. Structure-factor values attached to all reflections in H will comprise real numbers. For h acentric, and will be the real and imaginary parts of the complex structure factor; for h centric, will be the real coordinate of the (possibly complex) structure factor measured along a real axis rotated by one of the two angles , π apart, to which the phase is restricted modulo (Section 1.3.4.2.2.5). These n real coordinates will be arranged as a column vector containing the acentric then the centric data, i.e. in the order

• (b) Vectors of trigonometric structure-factor expressions

Let denote the vector of trigonometric structure-factor expressions associated with , where D denotes the asymmetric unit. These are defined as follows:where

According to the convention above, the coordinates of in will be arranged in a column vector as follows:

• (c) Distributions of random atoms and moment-generating functions

Let position x in D now become a random vector with probability density . Then becomes itself a random vector in , whose distribution is the image of distribution through the mapping just defined. The locus of in is a compact algebraic manifold (the multidimensional analogue of a Lissajous curve), so that p is a singular measure (a distribution of order 0, Section 1.3.2.3.4, concentrated on that manifold) with compact support. The average with respect to p of any function Ω over which is infinitely differentiable in a neighbourhood of may be calculated as an average with respect to m over D by the induction formula':

In particular, one can calculate the moment-generating function M for distribution p asand hence calculate the moments μ (respectively cumulants κ) of p by differentiation of M (respectively log M) at :The structure-factor algebra for group G (Section 1.3.4.2.2.9) then allows one to express products of 's as linear combinations of other 's, and hence to express all moments and cumulants of distribution as linear combinations of real and imaginary parts of Fourier coefficients of the prior distribution of atoms . This plays a key role in the use of nonuniform distributions of atoms.

• (d) The joint probability distribution of structure factors

In the random-atom model of an equal-atom structure, N atoms are placed randomly, independently of each other, in the asymmetric unit D of the crystal with probability density . For point atoms of unit weight, the vector F of structure-factor values for reflections may be writtenwhere the N copies of random vector ξ are independent and have the same distribution .

The joint probability distribution is then [Section 1.3.4.5.2.1(e)]

For low dimensionality n it is possible to carry out the Fourier transformation numerically after discretization, provided is sampled sufficiently finely that no aliasing results from taking its Nth power (Barakat, 1974). This exact approach can also accommodate heterogeneity, and has been used first in the field of intensity statistics (Shmueli et al., 1984, 1985; Shmueli & Weiss, 1987, 1988), then in the study of the and relations in triclinic space groups (Shmueli & Weiss, 1985, 1986). Some of these applications are described in Chapter 2.1 of this volume. This method could be extended to the construction of any joint probability distribution (j.p.d.) in any space group by using the generic expression for the moment-generating function (m.g.f.) derived by Bricogne (1984). It is, however, limited to small values of n by the necessity to carry out n-dimensional FFTs on large arrays of sample values.

The asymptotic expansions of Gram–Charlier and Edgeworth have good convergence properties only if lies in the vicinity of for all . Previous work on the j.p.d. of structure factors has used for a uniform distribution, so that ; as a result, the corresponding expansions are accurate only if all moduli are small, in which case the j.p.d. contains little phase information.

The saddlepoint method [Section 1.3.4.5.2.1(f)] constitutes the method of choice for evaluating the joint probability of structure factors when some of the moduli in are large. As shown previously, this approximation amounts to using the conjugate distribution'instead of the original distribution for the distribution of random vector ξ. This conjugate distribution is induced from the modified distribution of atomswhere, by the induction formula, may be written asand where τ is the unique solution of the saddlepoint equation:The desired approximation is thenwhereand where

Finally, the elements of the Hessian matrix are just the trigonometric second-order cumulants of distribution p, and hence can be calculated via structure-factor algebra from the Fourier coefficients of . All the quantities involved in the expression for are therefore effectively computable from the initial data and .

• (e) Maximum-entropy distributions of atoms

One of the main results in Bricogne (1984) is that the modified distribution in (SP1) is the unique distribution which has maximum entropy relative to , whereunder the constraint that be the centroid vector of the corresponding conjugate distribution . The traditional notation of maximum-entropy (ME) theory (Jaynes, 1957, 1968, 1983) is in this case (Bricogne, 1984)so that Z is identical to the m.g.f. M, and the coordinates of the saddlepoint are the Lagrange multipliers λ for the constraints .

Jaynes's ME theory also gives an estimate for :whereis the total entropy and is the counterpart to under the equivalence just established.

is identical to , but lacks the denominator. The latter, which is the normalization factor of a multivariate Gaussian with covariance matrix , may easily be seen to arise through Szegö's theorem (Sections 1.3.2.6.9.4, 1.3.4.2.1.10) from the extra logarithmic term in Stirling's formula(see, for instance, Reif, 1965) beyond the first two terms which serve to define entropy, sinceThe relative effect of this extra normalization factor depends on the ratio

The above relation between entropy maximization and the saddlepoint approximation is the basis of a Bayesian statistical approach to the phase problem (Bricogne, 1988) where the assumptions under which joint distributions of structure factors are sought incorporate many new ingredients (such as molecular boundaries, isomorphous substitutions, known fragments, noncrystallographic symmetries, multiple crystal forms) besides trial phase choices for basis reflections. The ME criterion intervenes in the construction of under these assumptions, and the distribution is a very useful computational intermediate in obtaining the approximate joint probability and the associated conditional distributions and likelihood functions.

• (f) Role of the Fourier transformation

The formal developments presented above make use of the following properties of the Fourier transformation:

 (i) the convolution theorem, which turns the convolution of probability distributions into the multiplication of their characteristic functions; (ii) the differentiation property, which confers moment-generating properties to characteristic functions; (iii) the reciprocity theorem, which allows the retrieval of a probability distribution from its characteristic or moment-generating function; (iv) the Paley–Wiener theorem, which allows the analytic continuation of characteristic functions associated to probability distributions with compact support, and thus gives rise to conjugate families of distributions; (v) Bertaut's structure-factor algebra (a discrete symmetrized version of the convolution theorem), which allows the calculation of all necessary moments and cumulants when the dimension n is small; (vi) Szegö's theorem, which provides an asymptotic approximation of the normalization factor when n is large.

This multi-faceted application seems an appropriate point at which to end this description of the Fourier transformation and of its use in crystallography.

### References

Barakat, R. (1974). First-order statistics of combined random sinusoidal waves with applications to laser speckle patterns. Opt. Acta, 21, 903–921.
Bertaut, E. F. (1955a). La méthode statistique en cristallographie. I. Acta Cryst. 8, 537–543.
Bertaut, E. F. (1955b). La méthode statistique en cristallographie. II. Quelques applications. Acta Cryst. 8, 544–548.
Bertaut, E. F. (1955c). Fonction de répartition: application à l'approache directe des structures. Acta Cryst. 8, 823–832.
Bertaut, E. F. (1956a). Les groupes de translation non primitifs et la méthode statistique. Acta Cryst. 9, 322.
Bhattacharya, R. N. & Rao, R. R. (1976). Normal Approximation and Asymptotic Expansions. New York: John Wiley.
Bleistein, N. & Handelsman, R. A. (1986). Asymptotic Expansions of Integrals. New York: Dover Publications.
Bricogne, G. (1984). Maximum entropy and the foundations of direct methods. Acta Cryst. A40, 410–445.
Bricogne, G. (1988). A Bayesian statistical theory of the phase problem. I. A multichannel maximum entropy formalism for constructing generalised joint probability distributions of structure factors. Acta Cryst. A44, 517–545.
Bruijn, N. G. de (1970). Asymptotic Methods in Analysis, 3rd ed. Amsterdam: North-Holland.
Cramér, H. (1946). Mathematical Methods of Statistics. Princeton University Press.
Daniels, H. E. (1954). Saddlepoint approximation in statistics. Ann. Math. Stat. 25, 631–650.
Fowler, R. H. (1936). Statistical Mechanics, 2nd ed. Cambridge University Press.
Hauptman, H. & Karle, J. (1953). Solution of the Phase Problem. I. The Centrosymmetric Crystal. ACA Monograph No. 3. Pittsburgh: Polycrystal Book Service.
Hörmander, L. (1973). An Introduction to Complex Analysis in Several Variables, 2nd ed. Amsterdam: North-Holland.
Jaynes, E. T. (1957). Information theory and statistical mechanics. Phys. Rev. 106, 620–630.
Jaynes, E. T. (1968). Prior probabilities. IEEE Trans. SSC, 4, 227–241.
Jaynes, E. T. (1983). Papers on Probability, Statistics and Statistical Physics. Dordrecht: Kluwer Academic Publishers.
Khinchin, A. I. (1949). Mathematical Foundations of Statistical Mechanics. New York: Dover Publications.
Klug, A. (1958). Joint probability distributions of structure factors and the phase problem. Acta Cryst. 11, 515–543.
Kluyver, J. C. (1906). A local probability problem. K. Ned. Akad. Wet. Proc. 8, 341–350.
Pearson, K. (1905). The problem of the random walk. Nature (London), 72, 294, 342.
Petrov, V. V. (1975). Sums of Independent Random Variables. Berlin: Springer-Verlag.
Rayleigh (J. W. Strutt), Lord (1880). On the resultant of a large number of vibrations of the same pitch and arbitrary phase. Philos. Mag. 10, 73–78.
Rayleigh (J. W. Strutt), Lord (1899). On James Bernoulli's theorem in probabilities. Philos. Mag. 47, 246–251.
Rayleigh (J. W. Strutt), Lord (1905). The problem of the random walk. Nature (London), 72, 318.
Rayleigh (J. W. Strutt), Lord (1918). On the light emitted from a random distribution of luminous sources. Philos. Mag. 36, 429–449.
Rayleigh (J. W. Strutt), Lord (1919). On the problem of random flights in one, two or three dimensions. Philos. Mag. 37, 321–347.
Reif, F. (1965). Fundamentals of Statistical and Thermal Physics, Appendix A.6. New York: McGraw-Hill.
Rice, S. O. (1944, 1945). Mathematical analysis of random noise. Bell Syst. Tech. J. 23, 283–332 (parts I and II); 24, 46–156 (parts III and IV). [Reprinted in Selected Papers on Noise and Stochastic Processes (1954), edited by N. Wax, pp. 133–294. New York: Dover Publications.]
Shmueli, U. & Weiss, G. H. (1985). Exact joint probability distribution for centrosymmetric structure factors. Derivation and application to the Σ1 relationship in the space group . Acta Cryst. A41, 401–408.
Shmueli, U. & Weiss, G. H. (1986). Exact joint distribution of , and , and the probability for the positive sign of the triple product in the space group . Acta Cryst. A42, 240–246.
Shmueli, U. & Weiss, G. H. (1987). Exact random-walk models in crystallographic statistics. III. Distributions of for space groups of low symmetry. Acta Cryst. A43, 93–98.
Shmueli, U. & Weiss, G. H. (1988). Exact random-walk models in crystallographic statistics. IV. P.d.f.'s of allowing for atoms in special positions. Acta Cryst. A44, 413–417.
Shmueli, U., Weiss, G. H. & Kiefer, J. E. (1985). Exact random-walk models in crystallographic statistics. II. The bicentric distribution for the space group . Acta Cryst. A41, 55–59.
Shmueli, U., Weiss, G. H., Kiefer, J. E. & Wilson, A. J. C. (1984). Exact random-walk models in crystallographic statistics. I. Space groups and P1. Acta Cryst. A40, 651–660.