Tilted laws and the drift

Written by Claude Opus 5.5 (Anthropic), October 2026. Self-checked by the writing AI. Public domain (CC0).

Suppose a random set of edges is hidden, and each edge is observed through a number that is larger on average if the edge is present, with Gaussian noise added. Given the observed numbers on finitely many edges, the conditional law of the hidden set is the original law with a density that is the exponential of a linear function: a tilt. This lesson studies the tilts of the free uniform spanning forest. Their dependence on the observed numbers is bounded by the constant \(\tfrac12\) of the response identity, for every graph and every finite set of observed edges. From the tilts the lesson defines, for every edge, a function of all the numbers on the graph, the drift, and proves that it is measurable, respects isomorphisms of graphs, and satisfies the same bound.

The lesson follows [OpenAI-F, Section 2, the part on finite tilts and the canonical drift]; Proposition 2.1 is the first step of the proof of the lemma on the posterior drift in [OpenAI-F, Section 3]. The lesson continues Weighted spanning trees and The forest as a limit of trees. It uses product measures, densities and measurable functions (core course Measure and Integration).

1. Tilts of a law

Let \(I\) be a countable set and \(\nu\) a probability measure on \(\{0,1\}^I\), with the \(\sigma\)-algebra generated by the coordinates \(x_i\). Let \(S\subseteq I\) be finite, \(t\ge0\) and \(y\in\mathbb R^I\). Put \[ \begin{gathered} w(x)=\exp\Bigl(\sum_{f\in S}\bigl(y_f-\tfrac t2\bigr)x_f\Bigr),\\ Z_S(t,y)=\int w\,d\nu,\\ b_{i,S}(t,y)=\frac1{Z_S(t,y)}\int x_i\,w\,d\nu \end{gathered} \] for \(i\in I\). The probability measure with the density \(w/Z_S(t,y)\) with respect to \(\nu\) is the tilt of \(\nu\) by the numbers \(y_f-\tfrac t2\), \(f\in S\), and \(b_{i,S}(t,y)\) is the probability of \(\{x_i=1\}\) under the tilt. The role of the parameter \(t\) is explained in Section 2.

Lemma 1.1.

  1. \(Z_S(t,y)\ge e^{-M}>0\), where \(M=\sum_{f\in S}|y_f-\tfrac t2|\).
  2. \(0\le b_{i,S}(t,y)\le1\).
  3. \(b_{i,S}(t,y)\) depends only on \(t\) and the numbers \(y_f\) with \(f\in S\), and it is a continuous function of these finitely many real variables.
  4. For the empty set, \(b_{i,\emptyset}(t,y)=\nu(x_i=1)\). If \(\nu(x_i=1)=1\), then \(b_{i,S}(t,y)=1\) for all \(S,t,y\).

Proof. (1) The exponent is at least \(-M\) for every \(x\). (2) \(0\le x_iw\le w\). (3) The functions \(w\) and \(x_iw\) depend on \(x\) only through the coordinates in \(S\cup\{i\}\). So each of the two integrals is the finite sum, over the \(a\in\{0,1\}^{S\cup\{i\}}\), of the value of the function at \(a\) times the probability that \(x\) agrees with \(a\) on \(S\cup\{i\}\). These sums are continuous in \(t\) and the \(y_f\), and the denominator is positive. (4) For \(S=\emptyset\), \(w=1\). If \(x_i=1\) almost surely, then \(\int x_iw\,d\nu=\int w\,d\nu\). \(\blacksquare\)

2. The tilt as a conditional probability

For \(t>0\) let \(\gamma_t(u)=(2\pi t)^{-1/2}e^{-u^2/(2t)}\) be the density of the normal law with mean \(0\) and variance \(t\).

Proposition 2.1. Let \(t>0\), let \(S\subseteq I\) be finite and not empty, let \(X\) be a random element of \(\{0,1\}^I\) with the law \(\nu\), and let \(N_f\), \(f\in S\), be standard normal random variables such that \(X\) and the \(N_f\) are independent. Put \[ Y_f=tX_f+\sqrt t\,N_f\quad(f\in S), \] \(Y=(Y_f)_{f\in S}\) and \(\Gamma_t(y)=\prod_{f\in S}\gamma_t(y_f)\). Then for every Borel set \(A\subseteq\mathbb R^S\) and every \(i\in I\), \[ \begin{gathered} \mathbb P(Y\in A)=\int_AZ_S(t,y)\,\Gamma_t(y)\,dy,\\ \mathbb P(X_i=1,\ Y\in A)\\ =\int_Ab_{i,S}(t,y)\,Z_S(t,y)\,\Gamma_t(y)\,dy . \end{gathered} \] So \(Y\) has the density \(Z_S(t,\cdot)\,\Gamma_t\), and \(b_{i,S}(t,Y)\) is the conditional probability of \(\{X_i=1\}\) given \(Y\): for every Borel set \(A\), the probability of \(\{X_i=1,\ Y\in A\}\) is the expectation of \(b_{i,S}(t,Y)\) on \(\{Y\in A\}\).

Proof. For \(a\in\{0,1\}\) and real \(u\), \[ \gamma_t(u-ta)=\gamma_t(u)\,e^{(u-t/2)a}, \] because \((u-ta)^2=u^2-2tua+t^2a\), where \(a^2=a\) was used. Let \(a\in\{0,1\}^{S\cup\{i\}}\), and let \(\nu_a\) be the probability that \(X\) agrees with \(a\) on \(S\cup\{i\}\). On this event \(Y_f=ta_f+\sqrt t\,N_f\). The variables \(\sqrt t\,N_f\) are independent with the density \(\gamma_t\), and they are independent of \(X\). So the probability that \(X\) agrees with \(a\) on \(S\cup\{i\}\) and \(Y\in A\) is \[ \begin{aligned} &\nu_a\int_A\prod_{f\in S}\gamma_t(y_f-ta_f)\,dy\\ &=\nu_a\int_A\exp\Bigl(\sum_{f\in S}\bigl(y_f-\tfrac t2\bigr)a_f\Bigr)\Gamma_t(y)\,dy . \end{aligned} \] The sum over all \(a\) is the first formula, by the description of \(Z_S\) as a finite sum in the proof of Lemma 1.1. The sum over the \(a\) with \(a_i=1\) is \(\int_A\bigl(\int x_iw\,d\nu\bigr)\Gamma_t(y)\,dy\), and \(\int x_iw\,d\nu=b_{i,S}(t,y)Z_S(t,y)\). \(\blacksquare\)

The variable \(Y_f\) is an observation of \(X_f\) in noise. Its mean is \(t\) if \(X_f=1\) and \(0\) otherwise, and the standard deviation of the noise is \(\sqrt t\); for large \(t\) the two cases are far apart, and the observation reveals \(X_f\) (Exercise 5.1). In [OpenAI-F, Section 3] the noise \(\sqrt t\,N_f\) is the value at the time \(t\) of a Brownian motion, all coordinates are observed, and the conditional probabilities are taken given the observations at all times up to \(t\). This course does not treat Brownian motion; the statement for one time and finitely many coordinates is the one above.

3. The response of the forest

Let \(G\) be an infinite connected graph in which every vertex lies on finitely many edges, with edge set \(E\), and let \(\nu=\mathsf{FUSF}_G\) be its free uniform spanning forest, a probability measure on \(\{0,1\}^E\). The functions \(b_{e,S}\) of Section 1 are formed with \(I=E\) and this \(\nu\).

Lemma 3.1. For every edge \(e\), every finite \(S\subseteq E\), every \(t\ge0\) and all \(y,y'\in\mathbb R^E\), \[ \begin{aligned} &|b_{e,S}(t,y)-b_{e,S}(t,y')|\\ &\quad\le\frac12\max_{f\in S}|y_f-y'_f| . \end{aligned} \] For the empty set the right side is read as \(0\).

Proof. For \(S=\emptyset\) both values are \(\nu(x_e=1)\). Let \(S\) be not empty, and let \(H_1\subseteq H_2\subseteq\cdots\) be an exhaustion of \(G\). Let \(m\) be so large that \(S\cup\{e\}\subseteq E(H_m)\), and let \(\mu_m\) be the law of the uniform spanning tree of \(H_m\). Define \(h\in\mathbb R^{E(H_m)}\) by \(h_f=y_f-\tfrac t2\) for \(f\in S\) and \(h_f=0\) for the other edges. The random spanning tree of \(H_m\) with the weights \(e^{h_f}\) gives a tree \(T_0\) a probability proportional to \[ \prod_{f\in T_0}e^{h_f}=\exp\Bigl(\sum_{f\in S}h_f\,\xi_f(T_0)\Bigr), \] where \(\xi_f\) is the indicator of \(f\). So the probability that it contains \(e\) is \[ p^{(m)}_e(h)=\frac{\int x_e\,w\,d\mu_m}{\int w\,d\mu_m}, \] with the function \(w\) of Section 1. Let \(h'\) be defined in the same way from \(y'\). Then \(|h_f-h'_f|\) is \(|y_f-y'_f|\) for \(f\in S\) and \(0\) for the other edges. By Corollary 5.2 of the lesson on weighted spanning trees, \[ |p^{(m)}_e(h)-p^{(m)}_e(h')|\le\frac12\max_{f\in S}|y_f-y'_f| . \] Let \(m\to\infty\). The functions \(w\) and \(x_ew\) depend only on the coordinates in \(S\cup\{e\}\), so their integrals are finite sums of multiples of probabilities of cylinders. By Theorem 4.1 of the lesson on the forest as a limit of trees, the integrals for \(\mu_m\) converge to the integrals for \(\nu\). The limit of the denominator is \(Z_S(t,y)>0\). So \(p^{(m)}_e(h)\to b_{e,S}(t,y)\), in the same way \(p^{(m)}_e(h')\to b_{e,S}(t,y')\), and the inequality passes to the limit. \(\blacksquare\)

The bound is special to spanning trees and forests. It fails for other laws, for example if three coordinates are always equal (Exercise 5.3).

4. The drift

The functions \(b_{e,S}\) depend on the finite set \(S\). To obtain one function for every edge, we take a definite sequence of sets that depends only on the graph and the edge. Let \(d\) be the distance in \(G\): the smallest number of edges of a path between two vertices. For an edge \(e=\{u,v\}\) and \(n\ge1\) let \(H_n(e)\) be the subgraph of \(G\) with the vertices \(z\) such that \[ \min\{d(z,u),d(z,v)\}\le n \] and all edges of \(G\) between these vertices, and let \(S_n(e)\) be its set of edges.

Lemma 4.1. The graphs \(H_1(e)\subseteq H_2(e)\subseteq\cdots\) form an exhaustion of \(G\).

Proof. The number of vertices at distance at most \(n\) from a given vertex is finite, by induction on \(n\), because every vertex lies on finitely many edges. So \(H_n(e)\) is finite. It contains \(u\) and \(v\). It is connected: a vertex \(z\) of \(H_n(e)\) is joined to the nearer one of \(u,v\) by a shortest path, all vertices of this path are at most as far from that vertex as \(z\), and \(u\) and \(v\) are joined by \(e\). The graphs increase with \(n\). An edge \(\{a,c\}\) of \(G\) belongs to \(H_n(e)\) as soon as \(n\ge d(a,u)\) and \(n\ge d(c,u)\). \(\blacksquare\)

Definition 4.2. For an edge \(e\), \(t\ge0\) and \(y\in\mathbb R^E\), the drift is \[ b_e(t,y)=\limsup_{n\to\infty}\,b_{e,S_n(e)}(t,y). \]

On \([0,\infty)\times\mathbb R^E\) we use the \(\sigma\)-algebra generated by \(t\) and the coordinates \(y_f\); the measurable functions for it are called Borel functions.

Proposition 4.3.

  1. Every \(b_e\) is a Borel function on \([0,\infty)\times\mathbb R^E\) with values in \([0,1]\).
  2. For every \(t\ge0\) and all \(y,y'\in\mathbb R^E\) for which \(\sup_{f\in E}|y_f-y'_f|\) is finite, and for every edge \(e\), \[ \begin{aligned} &|b_e(t,y)-b_e(t,y')|\\ &\quad\le\frac12\sup_{f\in E}|y_f-y'_f| . \end{aligned} \]
  3. Let \(\varphi\) be an isomorphism from \(G\) to a graph \(G'\), and let \(b'\) be the drift of \(G'\). For \(y\in\mathbb R^E\) let \(y'\) be the corresponding function on the edges of \(G'\), \(y'_{\varphi(f)}=y_f\). Then \(b'_{\varphi(e)}(t,y')=b_e(t,y)\).

Proof. (1) By Lemma 1.1, each \(b_{e,S_n(e)}\) has values in \([0,1]\) and is a continuous function of \(t\) and finitely many coordinates, hence a Borel function. The upper limit of a sequence of measurable functions is measurable.

(2) Let \(D\) be the supremum. By Lemma 3.1, for every \(n\), \[ b_{e,S_n(e)}(t,y)\le b_{e,S_n(e)}(t,y')+\tfrac12D . \] Taking the upper limit gives \(b_e(t,y)\le b_e(t,y')+\tfrac12D\), and the same holds with \(y\) and \(y'\) exchanged.

(3) An isomorphism preserves distances, so it maps \(S_n(e)\) onto the set \(S_n(\varphi(e))\) of \(G'\). By Theorem 4.1 of the lesson on the forest as a limit of trees it carries \(\mathsf{FUSF}_G\) to \(\mathsf{FUSF}_{G'}\). So the two integrals that define \(b'_{\varphi(e),S_n(\varphi(e))}(t,y')\) are equal to those that define \(b_{e,S_n(e)}(t,y)\). \(\blacksquare\)

In (2) the numbers \(y_f\) themselves may be unbounded; only the difference of the two functions has to be bounded. The definition uses an upper limit because the sequence \(b_{e,S_n(e)}(t,y)\) is not claimed to converge for every \(y\); the upper limit is defined everywhere.

The drift from finite graphs. The proof of Lemma 3.1, with the exhaustion \(H_m(e)\), gives for every \(n\) \[ \begin{gathered} b_{e,S_n(e)}(t,y)=\lim_{m\to\infty}\frac{\sum_{T}\xi_e(T)\,W_n(T)}{\sum_{T}W_n(T)},\\ W_n(T)=\exp\Bigl(\sum_{f\in T\cap S_n(e)}\bigl(y_f-\tfrac t2\bigr)\Bigr), \end{gathered} \] where both sums are over the spanning trees \(T\) of \(H_m(e)\), \(m\ge n\). So the drift at \(e\) is computed from the spanning trees of finite graphs around \(e\): first \(m\to\infty\) with \(n\) fixed, then the upper limit over \(n\).

Example 4.4. If \(G\) is a tree, every edge is present in the free uniform spanning forest with probability one, and \(b_e(t,y)=1\) for all \(t\) and \(y\), by Lemma 1.1.

In [OpenAI-F, Sections 3 and 4] the drift is evaluated at the observations: \(b_e(t,Y(t))\) is the conditional probability of the edge \(e\) given the observations of all edges up to the time \(t\), and the bound of Proposition 4.3 is the estimate that makes it possible to reconstruct the observations, and with them the forest, from independent noise. These sections are outside this course.

5. Exercises

5.1. Let \(I\) have one element \(i\), and \(\nu(x_i=1)=p\) with \(0<p<1\). Compute \(b_{i,\{i\}}(t,y)\). In the situation of Proposition 2.1, show that \(b_{i,\{i\}}(t,Y_i)\) converges to \(X_i\) in probability as \(t\to\infty\).

5.2. Let \(\nu\) be a probability measure on \(\{0,1\}^I\), as in Section 1. Show that for \(f\in S\) the derivative of \(b_{i,S}(t,y)\) with respect to \(y_f\) is the covariance of \(x_i\) and \(x_f\) under the tilt. Deduce from Lemma 3.1 that for the free uniform spanning forest the absolute values of the covariances of \(x_e\) with the \(x_f\), \(f\in S\), under every tilt add up to at most \(\tfrac12\).

5.3. Let \(I=\{1,2,3\}\), and let \(\nu\) give the probability \(\tfrac12\) to each of the points \((0,0,0)\) and \((1,1,1)\). Show that the bound of Lemma 3.1 does not hold for this \(\nu\), with \(S=I\).

5.4. Let \(G\) be the triangle with an infinite path attached at each of its three vertices (Example 4.4 of the lesson on the forest as a limit of trees). Compute the drift of every edge, and show that the upper limit in its definition is a limit.

6. Solutions

5.1. The two integrals are \(\int w\,d\nu=1-p+pe^{y-t/2}\) and \(\int x_iw\,d\nu=pe^{y-t/2}\), so \[ b_{i,\{i\}}(t,y)=\frac{pe^{y-t/2}}{1-p+pe^{y-t/2}} . \] On the event \(X_i=1\), \(Y_i-\tfrac t2=\tfrac t2+\sqrt t\,N_i\). For every real \(M\), the probability that this is at most \(M\) is the probability of \(N_i\le(M-\tfrac t2)/\sqrt t\), which tends to \(0\) as \(t\to\infty\). So \(Y_i-\tfrac t2\to+\infty\) in probability and \(b_{i,\{i\}}(t,Y_i)\to1\). On the event \(X_i=0\), \(Y_i-\tfrac t2=-\tfrac t2+\sqrt t\,N_i\to-\infty\) in probability, and \(b_{i,\{i\}}(t,Y_i)\to0\).

5.2. Let \(N=\int x_iw\,d\nu\) and \(Z=\int w\,d\nu\), finite sums of exponentials. Then \(\partial N/\partial y_f=\int x_ix_fw\,d\nu\) and \(\partial Z/\partial y_f=\int x_fw\,d\nu\). So \[ \begin{aligned} \frac{\partial}{\partial y_f}\frac NZ&=\frac{\int x_ix_fw\,d\nu}{Z}\\ &\quad-\frac NZ\cdot\frac{\int x_fw\,d\nu}{Z}, \end{aligned} \] which is the expectation of \(x_ix_f\) minus the product of the expectations of \(x_i\) and \(x_f\) under the tilt. For the forest, let \(\sigma_f\) be the sign of the covariance of \(x_e\) and \(x_f\) under the tilt by \(y\), for \(f\in S\), and \(\sigma_f=0\) for the other edges. The derivative of \(\tau\mapsto b_{e,S}(t,y+\tau\sigma)\) at \(\tau=0\) is the sum of the absolute values of these covariances. By Lemma 3.1, \(|b_{e,S}(t,y+\tau\sigma)-b_{e,S}(t,y)|\le\tfrac12|\tau|\), so this derivative is at most \(\tfrac12\).

5.3. Here \(\int w\,d\nu=\tfrac12(1+e^s)\) and \(\int x_1w\,d\nu=\tfrac12e^s\) with \(s=y_1+y_2+y_3-\tfrac{3t}2\), so \(b_{1,S}(t,y)=e^s/(1+e^s)\). Take \(t=0\), \(y=(0,0,0)\) and \(y'=(\tfrac15,\tfrac15,\tfrac15)\). Then \(b_{1,S}(0,y)=\tfrac12\) and \(b_{1,S}(0,y')=e^{3/5}/(1+e^{3/5})>0.64\), because \(e^{3/5}>1.8\) and \(u\mapsto u/(1+u)\) is increasing with the value \(0.6428\ldots\) at \(1.8\). The difference is more than \(0.14\), and \(\tfrac12\max_f|y_f-y'_f|=0.1\).

5.4. Under \(\mathsf{FUSF}_G\) all edges of the paths are present with probability one, and two of the three edges of the triangle are present, each pair with probability \(\tfrac13\). For an edge \(e\) of a path, \(b_e(t,y)=1\) by Lemma 1.1. Let \(e\) be the edge \(1\) of the triangle, with the other edges \(2,3\), and let \(S\) be a finite set of edges that contains the triangle. Almost surely the function \(w\) is the product of the factors \(e^{y_f-t/2}\) of the edges of the paths in \(S\), which is a constant, and of the factors \(c_j=e^{y_j-t/2}\) of the two edges of the triangle that are present. The constant cancels, and \[ b_{1,S}(t,y)=\frac{c_1(c_2+c_3)}{c_1c_2+c_1c_3+c_2c_3} . \] The set \(S_n(e)\) contains the triangle for every \(n\ge1\), because the third vertex of the triangle is at distance \(1\) from the ends of \(e\). So the sequence in the definition of the drift is constant, and \(b_1(t,y)\) is the displayed expression. It agrees with the probability \(p_1\) of the weighted spanning tree of the triangle (Example 5.3 of the lesson on weighted spanning trees).

References