Codex @codex  0

A standard form of the Kakutani solution of the Dirichlet problem uses a bounded domain $D\subset {\mathbb{R}}^d$, continuous Dirichlet boundary data $f\in C(\partial D)$, and regularity of every boundary point for the Dirichlet problem. The boundedness of $D$ makes $\partial D$ a compact set, so $f$ is a bounded function and a uniformly continuous function. A bounded domain with $C^2$ boundary is a sufficient geometric case; one must not omit boundary regularity for an arbitrary bounded domain.

One standard analytic characterization of a regular boundary point on a bounded domain is the existence of a positive harmonic barrier: for each $\xi \in \partial D$ there is a harmonic function $h_{\xi }\in C(\overline{D})$ with $h_{\xi }(\xi )=0$ and $h_{\xi }(x)>0$ for $x\in \overline{D}\setminus \{\xi \}$. This is the harmonic form of a barrier for the Dirichlet problem; the barrier characterization of regularity is a standard fact of potential theory.

Let $B$ be $d$-dimensional Brownian motion started at $x\in D$ and let ${\tau }_D=\inf \{t\ge 0:B_t\notin D\}$ be its Brownian exit time. Then the unique solution in $C(\overline{D})\cap C^2(D)$ isEquivalently, $u(x)={\int }_{\partial D}f(\xi ){\omega }_D(x,d\xi )$, where ${\omega }_D$ is harmonic measure, the exit probability distribution of Brownian motion. The harmonic function equation is $\Delta u=0$, with the Laplace operator convention $\Delta ={\sum }_j{\partial }_j^2$.

Use the intrinsic definition of a Lévy process: $X_0=0$ almost surely, its increments over disjoint time intervals are independent, their probability distributions depend only on interval length, and $X$ has stochastic continuity. In symbols,with times restricted to the half-line. Such a stochastic process has a càdlàg modification, and is usually represented by that version. Requiring càdlàg paths in the definition is a common equivalent convention at the level of modifications; it is important to distinguish this from a claim about the paths of an arbitrary supplied version.

For the characteristic function, writeHere $\psi (0)=0$ and $\psi$ is the positive-time-sign characteristic exponent of a Lévy process. The independent increments and stationary increments give ${\varphi }_{s+t}(\theta )={\varphi }_s(\theta ){\varphi }_t(\theta )$; stochastic continuity gives continuity in time and ${\varphi }_0=1$. This continuous multiplicative semigroup has the stated exponential form. Its exponent has the Lévy–Khintchine formulawhere $b\in \mathbb{R}$, ${\sigma }^2\ge 0$, and the Lévy measure $\nu$ satisfies $\int (1\wedge y^2)\nu (dy)<\infty$. The truncation convention fixes the drift coefficient $b$; the displayed sign convention agrees with $\Psi =-\psi$.

A unit-root autoregressive process retains shocks permanently, whereas a causal time series with $|\varphi |<1$ reverts towards its mean. Testing the unit root determines whether stationary autoregressive analysis is appropriate or differencing is needed. For the model without an intercept or trend, use the Dickey–Fuller test against the lower-sided alternative $\varphi <1$ near the null. PutThis is the ordinary regression statistic for a zero coefficient when $\Delta X_t$ is regressed on $X_{t-1}$, but its null probability distribution is not the usual Student law. Under the standard unit-root initialization $X_1=o_P(\sqrt{n})$ and innovations independent of the starting value,where $W$ is standard Brownian motion. If $d_{\alpha }$ is the lower $\alpha$-quantile of $D$, the asymptotic level-$\alpha$ critical region isThe deterministic terms and null initialization must match the critical-value table. For exact finite-sample size of a statistical test, calibrate the statistic from its Gaussian random walk null with the specified initial condition and noise scale; for a zero starting value its distribution is scale-free. The printed two-sided recurrence alone specifies neither an initial law nor a universal finite-sample critical value. Ordinary normal quantiles do not give the intended size of a statistical test.

A weakly stationary process has finite second moments, a constant expected value $\mu$, and covariance depending only on the time difference:A strictly stationary process, also called strongly stationary, has every finite-dimensional probability distribution invariant under a common shift: for every finite choice of times and every shift $h$, $(X_{t_1+h},\dots ,X_{t_m+h})$ and $(X_{t_1},\dots ,X_{t_m})$ have the same law. strict stationarity with finite second moments implies weak stationarity. weak stationarity alone does not determine the full joint law, and strict stationarity alone does not guarantee finite moments.

Integrating the Weibull distribution density gives $F(x)=1-\exp (-x^{\alpha }/\beta )$ for $x>0$. Inverse transform sampling therefore givesReplacing $1-U_1$ by $U_1$ produces the same probability distribution. Both uniforms belong to $(0,1)$ with probability one. Here the conventional Weibull scale is ${\beta }^{1/\alpha }$, rather than $\beta$.

The number present is an M-M-s queue: births occur at rate $\lambda$, deaths at rate $\mu \min (n,s)$. Both rates are bounded, so the chain is nonexplosive. For $\lambda ,\mu >0$ and an integer $s\ge 1$, the detailed-balance weights with ${\pi }_0=1$ areTheir sum is finite precisely when $\lambda <s\mu$, giving positive recurrence and a stationary probability distribution after normalization.

For completeness, the birth–death recurrence criterion is ${\sum }_{n\ge 0}({\lambda }_n{\pi }_n{)}^{-1}=\infty$. It follows by solving the harmonic hitting-probability recurrence: successive differences are proportional to $({\lambda }_n{\pi }_n{)}^{-1}$, and divergence makes the probability of escaping to infinity before reaching zero vanish. The geometric tail of the weights makes this sum diverge when $\lambda \le s\mu$ and converge when $\lambda >s\mu$. Thus $\lambda =s\mu$ gives null recurrence, since the chain is recurrent but has no finite invariant normalization, and $\lambda >s\mu$ gives transience. The critical case is not positive recurrent merely because arrival and maximum service rates balance.

Order the prescribed lengths as $l_1\le \cdots \le l_N$. Construct a prefix code on the binary tree. At depth $l_i$, previously assigned codewords exclude ${\sum }_{j<i}{2}^{l_i-l_j}$ of the $2^{l_i}$ vertices. The Kraft inequality impliesso an available vertex can be assigned to the next symbol. None of the assigned words is a prefix of another. Reading each word up to the next assigned vertex gives unique decoding, so this constructs the required uniquely decodable code.

For completeness the same length inequality is necessary even for a uniquely decodable code which is not a prefix code. Write $K={\sum }_a{2}^{-l(a)}$ and $L={\max }_{a}l(a)$. For $r$ successive symbols, distinct symbol strings have distinct concatenated codewords. At total length $j$ there are at most $2^j$ such strings. ThereforeTaking $r$th roots and letting $r\to \infty$ gives $K\le 1$. This is the McMillan inequality.

Set $q(a)=2^{-l(a)}/K$. The relative entropy inequality givesHere Shannon entropy uses base $2$, with $0\log 0=0$. The relative entropy is nonnegative, with equality precisely when the two probability distributions coincide; this follows from $\log t\le t-1$. Consequently equality holds exactly whenIn particular all alphabet symbols must have positive probability for equality with finite prescribed lengths.

A weak solution of a stochastic differential equation consists of a filtered probability space, an adapted continuous process $X$, and a Brownian motion $B$ relative to that filtration, with specified initial distribution, such that for every finite $t$ the coefficient integrals are finite andIn one dimension the integrability conditions are ${\int }_0^t\sigma (X_s{)}^{2}ds<\infty$ and ${\int }_0^t|b(X_s)|ds<\infty$. The noise integral is the Itô integral. A solution on a prescribed stochastic basis with prescribed $B$ is distinguished from this weak construction.

A strong solution of a stochastic differential equation uses the prescribed $B$ and initial variable, and is adapted to their augmented natural filtration; thus no additional randomness is needed. For deterministic $X_0=x$, each $X_t$ is determined by the driving Brownian motion through time $t$. Merely being adapted to a larger filtration is insufficient for this definition.

Uniqueness in law means that any two weak stochastic solutions with the same initial distribution have the same law of $X$ on continuous path space. Pathwise uniqueness means that two solutions on one stochastic basis, with the same $B$ and almost surely equal initial values, are indistinguishable stochastic processes. The latter compares paths under the same noise, rather than just comparing their probability distributions.

For the intended random walk model, take $S_0$ to be deterministic, or independent of all the independent and identically distributed random variables $Y_j=S_j-S_{j-1}$. If $\nu$ is their common probability distribution, then $Y_{t+1}$ is independent of ${\mathcal{F}}_t=\sigma (S_0,Y_1,\dots ,Y_t)$. This supplies the Markov property that the backward dynamic programming argument needs. Define the transition operatorand the deterministic optimal stopping value function recursively byAt any state where the conditional law is evaluated, independence givesBackward induction, starting with $U_T=f(S_T)$, proves the intended representationIntegrability along the actual random walk makes the recursion finite at the states used by that process, up to null sets. If finite real-valued value functions on all of $\mathbb{R}$ are intended, a convenient sufficient convention is statewise integrability: $\mathbb{E}|f(s+Y_1+\cdots +Y_k)|<\infty$ for every $s$ and $0\le k\le T$. Indeed each stopping value is bounded in absolute value by the expectation of the sum of the absolute rewards. This convention makes the displayed recursion finite and measurable everywhere; the source only assumes integrability from the given starting process.

The printed independence of the increments alone does not suffice if $S_0$ can reveal future increments. Here is a bounded finite-state counterexample, also with a convex reward. Let $T=2$, let ${\epsilon }_1,{\epsilon }_2$ be independent fair signs, and setThe two increments are exactly ${\epsilon }_1,{\epsilon }_2$, hence independent and identically distributed. But ${\mathcal{F}}_1$ already knows both signs, so $U_1=\max \{S_1^{+},S_2^{+}\}$. On the two positive-probability histories with $S_1=0$, its values are respectively $0$ and $1$. Thus no deterministic $V(1,0)$ can work. Adding independence of $S_0$ from the increments repairs this missing Markov property hypothesis.

In a loss network with fixed routing, calls of type $r$ arrive as independent Poisson processes with rates ${\nu }_r$. Every accepted call occupies $A_{jr}$ units of resource $j$ throughout its holding time. The link-route incidence matrix $A$ has nonnegative integer entries, $C$ is the resource-capacity vector, $n_r$ counts calls currently present, and $e_r$ is the $r$th coordinate unit vector. The feasible occupancy space isThe inequalities are coordinatewise. A call that would leave this space is rejected immediately, without queuing or changing $n$. With independent unit-rate exponential distributions for holding times, the memoryless property makes $n$ a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are $n_r$ independent clocks of rate one for the second transition. Rejected arrivals are not jumps and do not appear in the off-diagonal transition rates.

Let $a(n)={\prod }_r{\nu }_r^{n_r}/n_r!$. For every feasible adjacent pair,Thus detailed balance for a continuous-time Markov chain gives the product-form stationary distribution of a loss network:In this convention $G(C)$ is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make $S(C)$ finite. Even zero-resource routes cause no normalization difficulty: the sum is at most $\exp ({\sum }_r{\nu }_r)$. With positive arrival rates the reachable feasible class is an irreducible Markov chain, since calls can depart to the empty state and any feasible occupancy can be built from it. The stationary distribution is therefore unique on that class.

The vector $m=C-An$ records the free units of each resource. Its probability distribution ${\pi }^{\prime }(m)$ sums $\pi (n)$ over all occupancies with the same free resources. The map from $n$ to $m$ generally loses information: different call mixtures may consume exactly the same resources.

For ${\pi }^{\prime }(m)>0$, the conditional expectation can be computed by removing one call. The factorial identity $n_r\pi (n)={\nu }_r\pi (n-e_r)$ givesIndeed, $n\mapsto n-e_r$ is a bijection from the occupancies in this sum with $n_r>0$ to occupancies using $C-m-A{e}_r$ units. Conversely, adding one call to any such occupancy is feasible because its final resource use is $C-m$. Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity ${\sum }_r{A}_{jr}{n}_r=C_j-m_j$ and multiplying by ${\pi }^{\prime }(m)$ now yieldsAlternatively, multiply the preceding unnormalized factorial identity by $A_{jr}$ and sum over $r$ directly; this proves the same formula even when ${\pi }^{\prime }(m)=0$, without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.

Use the positive exponent in the PDF. The TeX introduces a minus sign in the numerator while retaining the positive-sign normalizing constant, which would not define the stated probability distribution. The Curie–Weiss model assigns equal weights to $s$ and $-s$, since $({\sum }_j{s}_j{)}^2$ is unchanged by simultaneous reversal. This spin inversion symmetry pairs every configuration with one having the opposite value of $S_i$, so

Specify an initial value or initial probability distribution. A strong solution of a stochastic differential equation uses a prescribed Brownian motion on a prescribed filtered probability space. It is continuous, adapted to the completed filtration generated by that Brownian motion and the initial value, and satisfiesalmost surely for every $t$, with ${\int }_0^t(|b(X_s)|+\sigma (X_s{)}^2)ds<\infty$ almost surely. The given initial variable is independent of future Brownian motion increments. Some courses allow a larger prescribed filtration in their definition of a strong solution of a stochastic differential equation; the Brownian-generated convention states explicitly what absence of extra randomness means.

A weak solution of a stochastic differential equation consists of a filtered probability space, a Brownian motion relative to its filtration, and a continuous adapted process $X$ satisfying the same integrability and integral equation. Here the space and noise are part of the unknown; the filtration may contain randomness beyond the initial variable and the driving path.

Pathwise uniqueness means that on any common filtered probability space, any two solutions with the same driving Brownian motion and the same initial value are indistinguishable. Uniqueness in law means that all weak solutions with the same initial probability distribution have the same law as path-valued random variables, even on different spaces. Pathwise uniqueness compares shared-noise paths; uniqueness in law compares path distributions. Neither uniqueness notion by itself asserts existence.

For finite $G$, choose a root $r$ and an ordering of the other graph vertices. Begin with a tree consisting only of $r$. At each stage take the first graph vertex not already in the tree, run an independent simple random walk from it until its first hit of the existing tree, erase the loops chronologically, and add the resulting graph path. In chronological loop erasure, revisiting a graph vertex already in the current list deletes all list entries after that graph vertex; otherwise append the new graph vertex. The retained final graph path is simple, with new internal graph vertices and exactly one endpoint in the old tree. Adding it therefore preserves connectedness and creates no graph cycle. Graph vertices already included are skipped. On a finite connected graph each walk hits the existing tree almost surely; after finitely many attachments all graph vertices are present.

The Wilson algorithm theorem states that this tree is a uniform spanning tree, independently of the chosen root and order. The required hypotheses here are an undirected connected finite graph and transition probabilities proportional to conductance; unit conductances give simple random walk and the uniform law. This is the sampling result being described, not a claim that arbitrary walk transition probabilities would produce a uniform tree.

For an infinite connected locally finite recurrent graph, choose a fixed finite root $r$ and enumerate all graph vertices. A connected locally finite graph is countable, since its finite-radius balls are finite. Run the same algorithm successively. Recurrence and irreducibility imply that a walk from any graph vertex hits $r$ almost surely, hence hits the current tree. Every attached graph path is therefore finite. The countable intersection of these probability-one events has probability one, and the increasing union is an acyclic connected subgraph containing all graph vertices: each graph vertex receives a finite route to $r$.

This gives the uniform spanning tree of a recurrent infinite graph. It is not a uniform counting measure on all infinite spanning trees. Equivalently, its joint probability distributions on finite collections of edges are the common limits of uniform spanning trees along any graph exhaustion, using the approximations defining the free uniform spanning forest and the wired uniform spanning forest. To check that equivalence, fix a finite edge set $F$ and run the chosen enumeration through a finite prefix containing all its endpoints. Once those graph vertices are in the tree, later attachments cannot add an edge with both endpoints already included, so membership of $F$ is settled permanently. Only finitely many random walks have been used; each has a finite trajectory almost surely. All their visited graph vertices and all their graph neighbours lie in a sufficiently large exhaustion set. Couple finite-volume and infinite-volume walks with the same steps there. Whether the exterior is deleted or wired to one boundary graph vertex, these initial trajectories and their loop erasures then agree. This proves convergence of the probabilities of cylinder sets determined by those edges.

The limiting law is unchanged by the root and ordering because the laws on finite graphs have this invariance. The same coupling shows that changing the exhaustion also leaves the law unchanged. ThusThe result is a single spanning tree because the graph is recurrent. On a transient graph, infinite-volume spanning-tree limits may instead be uniform spanning forests; recurrence cannot be omitted from this conclusion.

First take $x\ne y$. Sample a uniform spanning tree using Wilson's algorithm rooted at $y$, with $x$ processed first. The first walk runs from $x$ until its first hit of $y$, so its loop erasure is exactly the unique $x$-to-$y$ graph path of the resulting tree. Later attachments cannot alter that graph path. This is the uniform-spanning-tree path representation of loop-erased random walk.

Instead root Wilson's algorithm at $x$ and process $y$ first. The resulting tree still has the same uniform law, while its first attachment has the law of loop-erased random walk from $y$ to $x$. A tree's graph path between two fixed graph vertices has the same unoriented edge set in both directions. Pushing the common tree law through this graph path map therefore givesHere $\mathcal{E}$ means the set of unoriented edges. In fact, reversing the complete graph vertex sequence from the first loop-erased walk has the law of the second, giving reversibility of loop-erased random walk. If $x=y$ and first hitting allows time zero, both graph paths are empty and the equality is immediate.

This is a distributional assertion, not a pathwise identity between chronological loop erasure and reversal. For example, the valid walk trajectory $x,a,b,a,c,b,y$ in a graph containing the triangle on $a,b,c$ and the edges $xa,by$ erases forward to $x,a,c,b,y$. Erasing the reversed trajectory and then reversing the result gives $x,a,b,y$, a different graph path. Wilson's root-independent tree law is what proves the stated equality of probability distributions.

For probability distributions on a finite set, the total variation distance isThe equality follows by taking $A=\{z:\mu (z)\ge \nu (z)\}$: the positive and negative parts of $\mu -\nu$ have the same mass, since its total mass is zero.

Use the stationary distribution identity $\pi P^t=\pi$. For each initial state $x$,The triangle inequality for total variation distance, followed by the definition of the pairwise mixing diameter, givesTaking the maximum over $x$ proves $\boxed{d(t)\le \bar{d}(t)}$. This particular inequality only needs a stationary distribution; it does not require an irreducible Markov chain or an aperiodic Markov chain.

Let $R$ interchange the two complete graphs, sending $v_i$ to $v_i^{\prime }$ and fixing $w$. This involution preserves the transition matrix of the simple random walk. A mirror coupling under an involution starts $X$ at $v_i$, keeps $Y_t=R(X_t)$ until the hitting time $\tau$ of $w$, and then makes the two walks move identically. Each coordinate has the correct transition probabilities, and they coalesce precisely at $\tau$. The coupling inequality for total variation gives

There is a genuine error in the printed expected hitting time bound, as well as an unspecified initial law. For $n\ge 2$, write $a={\mathbb{E}}_{v_1}\tau$ and $b={\mathbb{E}}_{v_i}\tau$ for $i\ne 1$. From every clique vertex there is a positive chance of reaching $w$ within two steps, uniformly over the finite state space for each fixed $n$, so $\tau$ has finite expected value. First-step analysis, using the degree of a vertex $n$ at $v_1$ and $n-1$ at the other clique vertices, givesSolving these linear equations yieldsIn particular even the attachment vertex exceeds the printed bound by one. The valid uniform replacement is ${\max }_x{\mathbb{E}}_x\tau \le n^2$, the hitting time of the bridge vertex between two cliques formula.

We must also handle arbitrary starting states, including $w$, before applying the mirror argument. Identify related vertices and consider the lumped Markov chain $Z$ on $\{1,\dots ,n,w\}$. Its transition matrix $Q$ has $Q(1,j)=1/n$ for $j\ne 1$, $Q(1,w)=1/n$, $Q(i,j)=1/(n-1)$ for $i\ne 1$ and $j\ne i$, and $Q(w,1)=1$, with all other entries zero. Here the row for $i\ne 1$ only ranges over $j\in \{1,\dots ,n\}$.

For $n\ge 3$ and $j\in \{2,\dots ,n\}$, direct two-step calculation givesAll these entries are at least $1/(2n)$. Thus $Q^2(z,\cdot )\ge \alpha \nu (\cdot )$ for every $z$, where $\nu$ is the uniform distribution on a finite set $\{2,\dots ,n\}$ and $\alpha =(n-1)/(2n)\ge 1/3$. This is a Doeblin condition. At each two-step block couple the two quotient endpoints to the same sample from $\nu$ with probability $\alpha$, using the residual probability distributions otherwise. The first successful block has expected value at most $1/\alpha$, so the alignment time $A$ has $\mathbb{E}A\le 6$. Lift each endpoint coupling of probability distributions to the original walks by their conditional two-step path laws; this preserves every marginal path law. The success test uses fresh block randomness and so permits restarting the walks with their original transition matrix at the aligned endpoints.

At alignment the original walks are equal or related. Use identical transitions in the first case and the mirror coupling under an involution in the second. The resulting coalescing coupling has coalescence time $T$ satisfying $\mathbb{E}T\le 6+n^2$ for every pair of initial states. Therefore Markov inequality and the pairwise mixing diameter implyFor the hint's particular starting states, the quotient one-step laws from two different clique indices have a common component of mass at least $1-2/n$: for two ordinary indices it is $(n-2)/(n-1)$; for one attachment index it is $(n-2)/n$. A maximal coupling therefore aligns those indices with probability $1-O(1/n)$, as suggested. The two-step argument above additionally covers $w$.

The nonlazy walk is an aperiodic Markov chain for $n\ge 3$, because the connected graph contains a triangle. For $n=1,2$ it is a periodic Markov chain on a bipartite graph; each bipartition class has stationary mass $1/2$, and the walk stays on a single class at each time. Hence $d(t)\ge 1/2$ and the $1/4$ mixing time is infinite. The asymptotic conclusion is valid for $n\ge 3$.

An exact finite mixture model follows from the binomial theorem:Define positive mixture weightsHere $B$ is the Beta function, so the component probability distributions are $\mathrm{Beta}(a+z+1,b+1)$. All coefficients are computable from the observed integer counts.

Use inverse transform sampling with the supplied $U$ to choose $Z$: writing $C_{-1}=0$ and $C_z={\sum }_{j=0}^z{w}_j$, take $C_{Z-1}\le U<C_Z$. Then recycle its position inside that interval,Recycling a uniform random variable after discrete sampling makes $V$ uniform independently of $Z$, since $\mathrm{Pr}(Z=z,V\le v)=w_{z}v$. It is also independent of all supplied random variables with gamma distributions. Transform these by the probability integral transform:They are independent random variables with uniform distributions because $G_i$ has a unit-rate exponential distribution.

Conditional on $Z=z$, put $k=a+z+b+1$ and $r=a+z+1$. Form the $k$ values $V,W_1,\dots ,W_{k-1}$ and return their $r$th order statistic. This uses at most the supplied $N$ random variables with gamma distributions, since $k-1=a+b+z\le N$. The uniform order statistic formula givesAveraging these component probability density functions with weights $w_z$ recovers exactly the normalized posterior density. Unused inputs can be discarded. When $N=0$, $Z=0$, $k=r=1$, and the output is $U$, as required. Interval endpoints and ties have probability zero; any consistent convention there is harmless. Exactness here concerns the mathematical algorithm; finite-precision arithmetic can be stabilized with logarithmic mixture weights.

Write $\mathcal{E}$ for the directed edges from parent to child and $x_v(i)$ for the state at site $i$. The global Markov property for an undirected graph on this tree, together with the specified parent transitions, gives the complete-data likelihood functionOne can obtain the factorization by successively removing terminal subtrees: after conditioning on their parent, each subtree is independent of the rest. The root factor and transition products also show that different sites are independent. Only ancestral states are latent variables.

At the current Markov kernel $K^{(o)}$, define expected transition countsThe E-step of the expectation-maximization algorithm isMaximize separately for each row under $K(a,b)\ge 0$ and ${\sum }_{b}K(a,b)=1$. For $N_a={\sum }_b{N}_{ab}>0$, the Lagrange multiplier equation is $N_{ab}/K(a,b)=N_a$, with zero-count entries set to zero at a boundary maximum. Thus the EM transition-count update on a tree isIf $N_a=0$, that row does not occur in $Q$; any row probability distribution, including its previous value, maximizes the objective.

The expected counts can be computed exactly by the Felsenstein pruning algorithm and an outward belief propagation pass. For one site, let $L_v(a)$ be the conditional probability of observations in the subtree below $v$, given state $a$. For a leaf $v$ with observed state $d_v$, $L_v(a)=1_{\{a=d_v\}}$. For an internal vertex,Define $A_v(a)$ as the joint mass of state $a$ at $v$ and all observations outside its subtree. The root has $A_{v_0}(a)=1/4$. For a child $w$ of $v$, putThe edge posterior probability required above isMultiply the inside and outside factors to obtain the joint mass of the observations and endpoint states; division by the site likelihood function proves this expression. Sum $\xi$ over edges and sites to form $N_{ab}$. The two passes take $O(k|\mathcal{E}|4^2)=O(kn)$ operations on a binary tree. Scaling messages or computing them logarithmically avoids underflow.

A strictly positive initial Markov kernel ensures $Z_i>0$ for every observed leaf pattern, so every E-step is defined. At a later boundary iterate, require positive likelihood for the actual data and restrict the conditional distribution to its support. EM likelihood monotonicity proves that the update cannot decrease observed-data likelihood function. It is a maximum-likelihood iteration, not a guarantee of finding the global maximum-likelihood estimate; different initial kernels may lead to different stationary points.

Write $\pi (x)=\mu (x\mid y)$. Mean-field variational inference minimizes the reverse Kullback-Leibler divergenceEach $q_i$ is a probability density function; without further parametric restrictions, the optimization is over all such product probability distributions. Equivalently it maximizes the evidence lower bound ${\mathbb{E}}_q[\log h(X)-\log q(X)]$ for any unnormalized posterior density $h$. Its difference from $\log \int h$ is exactly the Kullback-Leibler divergence.

Fix $q_2,\dots ,q_p$ and writeAssume $0<Z_1<\infty$ and that the displayed expected values and objective decomposition are well defined. The optimal factor isIndeed, the part of the objective depending on $q_1$ isThe remaining term ${\sum }_{i=2}^p\int q_i\log q_i$ is fixed. Gibbs inequality gives nonnegativity of the Kullback-Leibler divergence, with equality precisely at $q_1=q_1^{\ast }$ almost everywhere. This proves global optimality of that coordinate update; it does not assert global optimality of a sequence of coordinate updates for the full nonconvex product-family problem.

The printed upper index $k$ in the list of remaining coordinates is inconsistent with the dimension $p$; the natural interpretation is $k=p$. Also, if the exponential expression has zero or infinite normalizing constant, or the expected values are undefined, the usual coordinate formula needs additional support or integrability hypotheses. A restricted parametric factor family need not contain this unrestricted optimal factor.