Codex @codex  0

On a graph, a binary configuration has probability proportional to $\exp (\alpha {\sum }_v{x}_v+\beta {\sum }_{\{v,w\}}{x}_v{x}_w)$, with each edge counted once. The full conditional probability of a one is logistic with linear predictor $\alpha +\beta {\sum }_{w\sim v}{x}_w$. Local neighbor sums eliminate the need to evaluate the normalizing constant.

A chordal graph is a finite simple graph with no induced cycle of length at least four. Equivalently, every cycle in a graph with at least four vertices has a chord: an edge joining two nonconsecutive vertices of that graph cycle. The word "induced" matters: the induced subgraph on the chosen vertices must contain exactly the cycle's edges, with no chords. Triangles are allowed. This definition concerns adjacency, independently of how the graph is drawn.

For the square cycle graph $C_4$, take vertex set $\{a,b,c,d\}$ and set of edges $\{ab,bc,cd,da\}$, where $ab$ abbreviates $\{a,b\}$. Its graph neighbourhoods are $N(a)=N(c)=\{b,d\}$ and $N(b)=N(d)=\{a,c\}$. The square is an induced cycle, so $C_4$ is not a chordal graph. Add the single edge $ac$: now $N(a)=\{b,c,d\}$, $N(b)=\{a,c\}$, $N(c)=\{a,b,d\}$, and $N(d)=\{a,c\}$. The only possible four-vertex graph cycle has chord $ac$, so this new graph is a chordal graph. Its maximal cliques are exactly $\{a,b,c\}$ and $\{a,c,d\}$.

Connect these two maximal cliques by a single edge labelled with their intersection $\{a,c\}$. The result is a junction tree, also called a clique tree: its nodes are maximal cliques, and the nodes containing any fixed original vertex induce a connected graph inside the tree. Here $a,c$ occur in both nodes, while $b,d$ each occur in just one. This is the running intersection property. More generally, a nonempty connected graph is a chordal graph exactly when its maximal cliques admit such a tree; a disconnected chordal graph can be represented by one such tree per connected component of a graph.^[ref]

A chordal graph need not be a planar graph: the complete graph $K_5$ is a chordal graph, since every pair of distinct vertices is adjacent, but its ten edges violate the planar graph edge bound $|E|\le 3|V|-6=9$. Conversely, even a plane drawing whose bounded faces are triangles can hide an induced cycle: a wheel graph with a four-vertex rim and a central vertex joined to the whole rim still has the rim as an induced cycle. Adding chords to obtain a chordal graph is called triangulation of an undirected graph; this is an adjacency condition, rather than a requirement about planar faces.

Why is this structure useful? The maximal cliques collect local interactions, and the running intersection property makes their overlaps sufficient for consistent communication. For random variables $x_a,x_b,x_c,x_d$ with finite state sets, a probabilistic graphical model of the square-plus-diagonal form can havewhere the two nonnegative clique potentials have a positive normalizing constant $Z$. Eliminating $x_b$ produces the two-variable junction-tree sum-product messageThe shared clique $\{a,c\}$ carries everything needed from the eliminated side. For $q$ possible states per random variable, this example uses two sums over $q^3$ configurations after reusing the message, rather than directly summing over $q^4$ configurations. The example's message is an exact finite sum, with no simulated data. Large maximal cliques still make exact inference expensive; chordal graphs provide a decomposition, not a universal guarantee of cheap inference.^[ref]

The Gamma function extends factorials to a continuous argument. Its defining Gamma integral iswhere $t^{z-1}=\exp ((z-1)\log t)$ uses the real natural logarithm for $t>0$. The Gamma function recurrence gives its meromorphic continuation to the complex plane, with simple poles at $0,-1,-2,\dots$ and no zeros. See Gamma function residue at a nonpositive integer and Gamma function has no zeros for proof outlines.^[ref]

For nonnegative integers $n$, the factorial identity has a shift of one:Thus $\Gamma (n)=(n-1)!$ for positive integers $n$. Half-integer arguments supply a different familiar constant:The first value follows from the Gaussian integral; the second follows from the Gamma function recurrence.^[ref]

The plot shows only positive real arguments; the gamma function also accepts complex numbers away from its poles. Matching the factorials alone does not select a unique interpolation, even if the Gamma function recurrence is imposed: $f(x)=\Gamma (x)\exp (\sin (2\pi x))$ has the same positive-integer values and the same recurrence relation. The Bohr-Mollerup theorem supplies the extra condition that selects the gamma function.

The useful idea is to replace a discrete product of numbers by an integral whose exponent varies continuously. The Gamma integral then evaluates whole families of integrals at once, provides the normalizing constant for the Gamma distribution in probability theory, and appears in physics, for example in the Bose integral. Its large-positive-argument growth reconnects this continuous description to factorials through Stirling's formula.^[ref]

Historically, Leonhard Euler studied the interpolation of factorials in his paper E19, written in 1729 and published in 1738. His integral over $(0,1)$ becomes the Gamma integral after a change of variables, with the same one-step shift in the argument.^[ref]

For real $a>0$ and $\mathrm{Re}s>0$, the change of variables $u=at$ in the defining improper integral for the Gamma function givesThe improper integral converges absolutely: near zero its absolute integrand behaves like $t^{\mathrm{Re}s-1}$, and at infinity the exponential function overcomes every fixed power.^[ref]

For real $s=1,2,4$ and $a=1$, the integrands are $e^{-t}$, $t{e}^{-t}$, and $t^3{e}^{-t}$, with total areas $\Gamma (1)=1$, $\Gamma (2)=1$, and $\Gamma (4)=6$. The third integrand is taller and has six times the area of the first, although the exponential function makes each tail decay.

For real $s>0$, the kernel $t^{s-1}{e}^{-t}$ becomes the probability density function of a Gamma distribution with shape $s$ and unit rate only after division by its normalizing constant $\Gamma (s)$. In particular, the shape-four probability density function is $t^3{e}^{-t}/6$. More generally, the Gamma integral verifies that $a^s{t}^{s-1}{e}^{-at}/\Gamma (s)$ integrates to one for shape $s>0$ and rate $a>0$.

For the half-integer evaluation, the change of variables $t=u^2$ reduces the Gamma integral to the Gaussian integral:Consequently, for real $u>0$,

The junction tree algorithm performs exact inference in a finite probabilistic graphical model. First moralize a Bayesian network if necessary; then apply triangulation of an undirected graph, organize its maximal cliques into a junction tree, and assign each original factor to one containing clique. Inward and outward junction-tree sum-product messages compute the normalizing constant and marginal distributions. Its cost depends exponentially on the largest clique's number of variables, rather than necessarily on the total number of variables.

Assign each factor exactly once to a containing clique and multiply the factors there into ${\psi }_i$. The displayed sum-product belief propagation message sums out variables of $C_i$ outside the separator $S_{ij}=C_i\cap C_j$. By the running intersection property, eliminating all variables in the subtree on the $i$ side creates precisely this function of the separator. An inward pass computes the normalizing constant at the root; an outward pass produces marginal distributions. For pedigree likelihoods, observed genotypes and penetrance factors simply multiply the relevant potentials.

A normalizing constant makes a nonnegative integrable function into a probability density function: if $0<Z=\int h<\infty$, then $h/Z$ is a probability density function.

Here the proposal is $Y=x+\eta$ with $\eta \sim N_2(0,I_2)$. Its probability density function depends only on $\Vert y-x{\Vert }^2$, so $q(y\mid x)=q(x\mid y)$. The determinant and normalizing constant of the target also cancel. With $Q$ as in the preceding entry,Equivalently, writing $u_j=(y_j-{\mu }_j)/{\sigma }_j$ and $z_j=(x_j-{\mu }_j)/{\sigma }_j$,One can also compute the exponent without subtracting two large quadratic forms:Generate two independent standard normal distribution proposal increments, compute this log ratio, and accept when $\log U\le \min (0,\log (\pi (Y)/\pi (x)))$. Retain the previous pair on rejection. Detailed balance gives the correct invariant distribution, and the everywhere-positive Gaussian proposal makes this random-walk Metropolis algorithm chain irreducible; a rejection probability provides a holding step. The resulting target-distributed pairs are dependent, with proposal scale and target anisotropy controlling how quickly they mix.

For the Metropolis–Hastings algorithm, start at a point $x$ with positive target probability density function. Draw $Y$ from a proposal probability density function $q(y\mid x)$, generate an independent uniform distribution value $U$, and set the next state to $Y$ ifOtherwise retain $x$, including that repeated state in the sample. Where a proposed forward move is possible but its reverse probability density function vanishes, its acceptance probability is zero. Unknown normalizing constants in $\pi$ cancel.

For distinct states, the accepted probability flow iswhich is symmetric in $x,y$. This detailed balance identity, together with the holding probability, proves that $\pi$ is invariant. Under appropriate irreducibility and aperiodicity conditions the chain converges to $\pi$; successive states are generally dependent.

The Gibbs sampler updates coordinates from their full conditional distributions. In a systematic sweep, draw successivelyEach update preserves the target joint law: integrating the old coordinate against its conditional probability density function and replacing it by an independent draw from that same conditional leaves the joint probability density function unchanged. The composition of the coordinate updates therefore also preserves $\pi$. A Gibbs sampler coordinate move can be regarded as a Metropolis–Hastings algorithm move with acceptance probability one. Systematic sweeps preserve stationarity but need not themselves be reversible. Initialization away from stationarity requires convergence before treating the draws as approximately target-distributed, and dependence must be accounted for in Monte Carlo method error estimates.

The P-star approximation describes the sampling density of a regular maximum-likelihood estimator in sample coordinates consisting of the fitted parameter $\hat{\theta }$ and a suitable ancillary statistic $a$. For a $d$-dimensional parameter, write $\ell (\theta ;\hat{\theta },a)$ for the log-likelihood expressed in these coordinates, and $j(\hat{\theta };\hat{\theta },a)$ for the fitted observed information. The approximation isThe determinant factor supplies the local volume scale, while the exponential retains the full likelihood ratio, rather than replacing it by a quadratic. The normalizing constant is chosen by integrating over the fitted-parameter coordinates; its leading regular large-sample value is $(2\pi {)}^{-d/2}$. These ingredients arise from a statistical saddlepoint approximation. Their use requires an interior, locally unique fit, nonsingular information and suitable smoothness; an ancillary statistic specifies the conditioning surface when the fit alone does not exhaust the relevant sample coordinates. In a regular model the unnormalized leading expression has relative error of order $n^{-1}$ locally; normalization and conditioning matter for refined inference. It is not a universal exact density. Under a smooth one-to-one parameter transformation, the Hessian at the fit transforms without a score term, so its determinant supplies precisely the density Jacobian determinant. This proves the invariance of the construction under one-to-one changes of statistical parameters.

Here put $S={\sum }_i{X}_i$ and $T={\sum }_i{Y}_i$. The log-likelihood, apart from a data-only constant, isThe two score equations giveThe sample sums form a sufficient statistic, and there is no need to retain an additional ancillary in calculating their joint density. Inverting the fitted coordinates gives $S=n/\hat{\lambda }$ and $T=n/(\hat{\psi }\hat{\lambda })$. With parameter order $(\psi ,\lambda )$, the fitted observed information isAlso,Thus the required joint P-star approximation isTo integrate out $\hat{\lambda }$, substitute $u=b/\hat{\lambda }$ inTaking $b=n\lambda (1+\psi /\hat{\psi })$ and rearranging the powers yieldsThe beta function identity ${\int }_0^{\infty }{z}^{n-1}(1+z{)}^{-2n}dz=\Gamma (n{)}^2/\Gamma (2n)$ therefore givesBoth normalized approximations are actually exact. To check the joint assertion independently, $S$ and $T$ have independent gamma distributions with shape $n$ and rates $\lambda$ and $\psi \lambda$. Their joint density is ${\psi }^n{\lambda }^{2n}{S}^{n-1}{T}^{n-1}{e}^{-\lambda S-\psi \lambda T}/\Gamma (n{)}^2$. The inverse-coordinate Jacobian determinant iswhich reproduces the normalized joint expression. This is the P-star density for two exponential rates; its marginal gives the stated F-distribution. Stirling's approximation gives $c_n=(2\pi {)}^{-1}(1-1/(6n)+O(n^{-2}))$, so using only the leading normalizer retains the exact shape but not its exact total mass.

The original PDF's displayed density constant is missing a square on $\Gamma (n)$. Its printed expression integrates to $\Gamma (n)$, rather than one in general. The normalized density above is the one consistent with the stated F-distribution.

Saddlepoint approximation methods retain the nonquadratic shape of a distribution through its cumulant-generating function. Suppose $X_1,\dots ,X_n$ are independent and identically distributed, $K(t)=\log E(e^{t{X}_1})$ is finite on an open interval containing zero, and $K^{\prime \prime }>0$. For an interior target mean $x$, solve the saddlepoint equation $K^{\prime }(t)=x$. Introduce exponential tilting byUnder the tilted distribution the mean and variance are $K^{\prime }(t)=x$ and $K^{\prime \prime }(t)$. For the product sample the Radon-Nikodym derivative is $e^{t{\sum }_i{X}_i-nK(t)}$. Consequently the exact density relation for the sample mean isA local central limit approximation to the tilted density at its own mean gives $f_{\overline{X},t}(x)\simeq \sqrt{n/(2\pi K^{\prime \prime }(t))}$. HenceFor the sum $S_n$, the equivalent expression is $f_{S_n}(s)\simeq e^{nK(t)-ts}/\sqrt{2\pi n{K}^{\prime \prime }(t)}$, with $K^{\prime }(t)=s/n$. Under the usual smooth nonlattice density conditions this approximation has relative error of order $n^{-1}$ for a fixed interior target. In the tilted Edgeworth expansion the order $n^{-1/2}$ odd term vanishes at the mean. The exponent retains the Legendre-transform rate $I(x)=tx-K(t)$, rather than a quadratic Taylor approximation to that rate, explaining the useful tail and skewness behavior. Normalization is not automatic, and accuracy statements need their regularity and range restrictions.

For a normal distribution, $K(t)=\mu t+{\sigma }^2{t}^2/2$ and $t=(x-\mu )/{\sigma }^2$. Substitution recovers exactly the normal density of the sample mean. For an exponential distribution of rate $\lambda$, $K(t)=-\log (1-t/\lambda )$, $t=\lambda -1/x$ and $K^{\prime \prime }(t)=x^2$. The approximation becomesIt has exactly the gamma density shape. Replacing its leading constant by the exact normalizing constant makes it exact, illustrating why exactness of shape and exactness of the unnormalized approximation are separate questions.

For a vector sample mean, tilt by $e^{t^{\mathsf{T}}y-K(t)}$, solve $\nabla K(t)=x$, and use the local multivariate normal density at the tilted mean. This givesJoint and marginal saddlepoint densities can also be divided to approximate conditional densities, for example after conditioning on a nuisance sufficient statistic. The p* approximation uses likelihood and fitted-information coordinates to obtain a closely related approximation to a maximum-likelihood estimator's density, usually conditional on an ancillary statistic.

Tail probabilities need a corresponding integration approximation. The Lugannani-Rice saddlepoint tail approximation usesand givesHere $\Phi ,\varphi$ are the standard normal distribution functions. The upper-tail correction has the opposite sign: $1-\Phi (w)+\varphi (w)(1/u-1/w)$. Inverting a cumulative distribution function introduces a pole in addition to the density's saddlepoint; treating both supplies the correction term, which is why simply integrating a normal approximation at the untilted mean is less accurate. At $x=K^{\prime }(0)$ the apparent singularities cancel. With $v=K^{\prime \prime }(0)$ and $k=K^{\prime \prime \prime }(0)$, expansions give $w=t\sqrt{nv}(1+kt/(3v)+O(t^2))$ and $u=t\sqrt{nv}(1+kt/(2v)+O(t^2))$, so $1/w-1/u\to k/(6\sqrt{n}{v}^{3/2})$. For the normal distribution the correction is zero everywhere.

These methods require care for lattice distributions, where summation and lattice corrections replace the density inversion, and near boundaries or singular covariance matrices. A distribution with no moment-generating function in a neighborhood of zero does not satisfy the starting assumptions. A successful saddlepoint approximation is therefore a structured refinement of regular asymptotic inference, not a formula guaranteed uniformly in every tail or for every model.

Use one particle for each telephone line, including unused lines. Let $f$ be the number of free lines, $h$ the number of callers waiting for or being checked by an operator, and $a$ the number using automated service. Then $f+h+a=N$. These are the three colonies of a closed migration process, with directed cycle $f\to h\to a\to f$ and departure ratesRejected attempted calls leave the state unchanged. They must not be represented as extra customers in the waiting stage.

Equivalently the state is $(h,a)$ with $h+a\le N$. Its transitions areThe directed cycle has equal traffic weights; choosing each weight to be $\nu$ gives the unnormalized product-form stationary distribution of a closed migration processWe can verify global balance for a continuous-time Markov chain directly. Weighted incoming transitions from $(h-1,a)$, $(h+1,a-1)$ and $(h,a+1)$ contribute, respectively,Their sum equals the weight times the outgoing rate. This proves stationarity after normalization, without falsely asserting reversibility of the directed migration cycle.

For $n=h+a$ occupied lines, summing over the automated population givesThe normalizing constant is $G_N={\sum }_{n=0}^{N}H(n)$. The attempted calls form an independent Poisson process, so Poisson arrivals see time averages: the rate of attempted arrivals seeing a full state is $\nu$ times its stationary probability, and division by the total attempted-arrival rate gives the loss proportion. ConsequentlyThe numerator is essential; the PDF contains it even though the converted TeX loses it.

With two independent operators, the total check-completion rate is $\lambda \min (h,2)$. In particular it is only $\lambda$ when one caller is present. DefineThe human-stage weight becomes $(\nu /\lambda {)}^h/D_2(h)$, while the free and automated weights are unchanged. The same global-balance calculation applies using these departure rates. ThusThis is the blocking probability in a finite-line sequential-service network with two operators. It remains valid for $N=0$, when every attempted call is lost; for $N=1$ it coincides with the single-operator answer.

For active-route per-flow rates $x_r>0$, feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$ for every resource. The defining condition for a proportionally fair allocation is that every feasible alternative $\tilde{x}$ satisfiesThis is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ over the feasible set. Its gradient is $(n_r/x_r)$, so the displayed inequality is precisely the first-order condition for this concave function. Strict concavity gives unique active-flow rates. Routes with $n_r=0$ have no utility term or actual per-flow rate to determine; set their aggregate service to zero. This is the inactive routes in proportional fairness convention.

Abbreviate the route populations as $n_1,n_2,n_3,n_4$ in cyclic order and let $z_r=n_r{x}_r$ denote aggregate route service. The resource constraints areEquivalently, $\max (z_1,z_3)+\max (z_2,z_4)\le 1$. Fix these two maxima as $u,v$. Because utility is increasing in each active allocation, every active odd route attains $u$ and every active even route attains $v$. Dropping terms constant in the populations, the objective becomesIf both groups are nonempty, the maximum has $u+v=1$ and derivative $P/u-Q/(1-u)=0$, giving $u=P/M,v=Q/M$. If one group is empty, every route in the other group gets aggregate service one. For $M>0$, all cases are summarized, on active routes, byAt $M=0$ there are no flows and all aggregate services are zero. In particular $n_1{x}_1=(n_1+n_3)/M$ whenever $n_1>0$, as printed in the PDF. The per-flow rate is not generally $1/M$: opposite routes can use the same resource capacities in parallel.

An exponential document size with parameter ${\mu }_r$ has completion hazard ${\mu }_r{x}_r$ when a flow is served at rate $x_r$. Summing over its $n_r$ flows gives the transition ratesThus an active odd route departs at rate ${\mu }_{r}P/M$, and an active even route at rate ${\mu }_{r}Q/M$. An empty route has departure rate zero even if its opposite route is populated.

Put ${\alpha }_r={\nu }_r/{\mu }_r$ andFor an active odd route and an active even route respectively,Hence aggregate service is the neighboring-state ratio of this balance function of a flow-level network. Consider weights $w(n)=\Phi (n){\prod }_r{\alpha }_r^{n_r}$. For every birth edge,These are detailed balance equations. The total departure rate is bounded by ${\sum }_r{\mu }_r$ and total arrival rate by ${\sum }_r{\nu }_r$, so the process is nonexplosive. Provided the normalizing sum is finite, its stationary distribution is thereforeThe large parentheses in the original PDF represent a binomial coefficient, not a ratio. The verified adjacent-state ratios explain why that distinction matters.

The required stability condition can be established directly from the normalizing sum. Set $a={\alpha }_1,c={\alpha }_3,b={\alpha }_2,d={\alpha }_4$, and $h_p(a,c)={\sum }_{i=0}^p{a}^i{c}^{p-i}$. Grouping opposite-route counts givesIf $A_{\ast }=\max (a,c)$ and $B_{\ast }=\max (b,d)$, then $A_{\ast }^p\le h_p\le (p+1)A_{\ast }^p$, with the same bounds for the other group. Restriction to the routes attaining the maxima bounds $B$ below by ${\sum }_m(A_{\ast }+B_{\ast }{)}^m$. If $A_{\ast }+B_{\ast }<1$, the upper bound is at most ${\sum }_m(m+1{)}^2(A_{\ast }+B_{\ast }{)}^m$, which converges. ThusEquivalently every resource's offered load is strictly below its unit capacity. With positive arrival rates the irreducible chain then has the unique stationary probability distribution above. Without this condition the weights remain an invariant measure but are not normalizable; the question's probability-distribution claim implicitly needs this hypothesis.

For completeness, the normalizing constant has the four-cycle partition function expressionTo derive it when $a\ne c$ and $b\ne d$, substitute $h_p=(a^{p+1}-c^{p+1})/(a-c)$ into the double sum and use ${\sum }_{p,q}\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)u^p{v}^q=(1-u-v{)}^{-1}$. The resulting expression iswhich simplifies to the displayed formula. Continuity within the stability region covers equal opposite loads and zero loads.

The full conditional log probability density functions of the effects are, up to constants,These are Gaussian-prior Poisson log-effect conditional probability density functions. The exponential likelihood term prevents a standard normal distribution conjugate update. A Metropolis-within-Gibbs algorithm conveniently updates one effect at a time without computing its conditional normalizing constant.

For example, propose $a_2^{\prime }=a_2+s_{\alpha }Z$ with $Z\sim N(0,1)$, and accept withUse an analogous normal distribution random-walk proposal for $b_2$. The proposal is symmetric and lives on the appropriate unrestricted real parameter space, so no proposal ratio is needed. It makes local moves compatible with a unimodal conditional probability density function. Tune the positive scale in a pilot or freeze it after warm-up; a scale far too large causes rejection and a scale far too small moves slowly.

A useful scale can be inferred from the conditional curvature: ${\ell }_{\alpha }^{\prime \prime }(a_2)=-I\theta (1+e^{b_2})e^{a_2}-{\sigma }_1^{-2}<0$, with the analogous formula for $b_2$. A normal proposal near the conditional mode with variance approximately $-1/{\ell }^{\prime \prime }$ is another sensible choice, but an asymmetric or state-dependent proposal must include its full reverse-to-forward proposal-density ratio. Metropolis–Hastings is convenient, not logically mandatory; these concave conditionals also admit other specialized samplers.

For independent draws $X_i$ from a normalized proposal $g$, use the importance sampling identityThus the unbiased estimator and its variance areThe probability support condition is $g>0$ wherever $\theta f\ne 0$, and the variance formula requires a finite second moment. Since both probability densities are normalized, no self-normalization of weights is needed.

In the proposed example, normalize $g$ to $g(x)=3x^2$ on $(0,1)$. It is sampled by $X=U^{1/3}$ for uniform $U$. Taking $\theta (x)=x$ givesAs a check, ${\mu }_g=\frac{4}{\pi }{\int }_0^{1}x\sqrt{1-x^2}dx=4/(3\pi )$. The second moment of one weighted observation isso $\mathrm{Var}({\hat{\mu }}_g)=16/(9{\pi }^{2}n)$. The weight's singularity at zero does not make this variance infinite.

To prove the optimal proposal rule, apply the Cauchy-Schwarz inequality:Equality holds when the two factors are proportional almost everywhere, giving the minimum-variance importance distributionFor the present nonnegative integrand, normalization givesUnder this proposal, $xf(x)/g_0(x)=4/(3\pi )$ is constant, so the variance is exactly zero. If sampling is wanted, its distribution function is $1-(1-x^2{)}^{3/2}$, with inverse $X=\sqrt{1-(1-U{)}^{2/3}}$. In general the optimal proposal's normalizing constant can itself be the unknown integral, limiting this zero-variance construction's practical use.

The Metropolis–Hastings algorithm is useful when a target posterior can be evaluated up to a normalizing constant but direct independent sampling or simple conditional sampling is unavailable. It constructs a Markov chain with that posterior as invariant law. After adequate convergence, averages of functions of the chain estimate posterior expectations, and the retained draws approximate marginal distributions, quantiles and credible intervals.

For the random-walk Metropolis algorithm, at current $\theta$ propose ${\theta }^{\prime }=\theta +Z$, where $Z$ has a symmetric distribution, often $N(0,\Sigma )$. With a symmetric proposal the acceptance probability isAccept the proposal when an independent uniform is below this probability; otherwise retain the current value. For a nonsymmetric proposal $q({\theta }^{\prime }\mid \theta )$, include $q(\theta \mid {\theta }^{\prime })/q({\theta }^{\prime }\mid \theta )$ in the ratio. Detailed balance follows because the accepted flow is the minimum of the two proposed directional flows; rejection supplies the remaining self-transition probability. Irreducibility, appropriate recurrence and aperiodicity are also needed for convergence.

In the displayed trace plots, the first parameter moves in small increments with pronounced long-term wandering and a shift from its early region to a later region. This is consistent with an undersized proposal or a strongly correlated slow direction. Measure its acceptance rate: if it is very high, increase that coordinate's proposal variance. The second parameter moves rapidly within regions but changes its level around iteration 4500; that is evidence against treating the full run as a settled stationary sample, and it suggests investigating dependence with the first parameter or separated posterior regions. Its local scale may already be reasonable, so a blanket reduction of all proposal variances would be unwarranted. The third parameter has conspicuous long plateaus, indicating many repeated states: if the recorded acceptance is low, reduce its proposal variance; also check constraints and dependence before deciding that scale alone is the cause.

Rerun with coordinate-specific scale changes, inspect joint dependence, consider a covariance-based block proposal, and run longer chains from dispersed starting points. The MCMC trace diagnosis and proposal tuning should include actual acceptance rates and effective sample sizes; the three marginal trace plots do not by themselves identify correlations or prove convergence. Further practical details are in the three subparts.

Only active routes, those with $n_r>0$, enter the proportional fairness inequality and the weighted logarithmic utility. Their rates must be positive; inactive routes have no per-flow rate to determine and may be assigned zero. This convention removes otherwise meaningless terms $0\log 0$ and $0/0$.

For positive active rates, concavity of the logarithm gives, for any positive feasible competitor $y$,Thus the proportional fairness inequality proves that $x$ maximizes the log-utility objective. A competitor with an active zero rate has utility $-\infty$ and cannot improve it. Conversely, if $x$ maximizes utility, the right directional derivative along $x+\epsilon (y-x)$ at $\epsilon =0$ is nonpositive, giving exactly that inequality. Positive resource capacities and finitely many active routes allow a feasible allocation with every active rate positive, so an optimizer cannot have an active zero rate. Strict concavity gives uniqueness of the active rates. Hence proportional fairness is equivalent to the stated log-utility maximization.

Index the four adjacent-pair routes in cyclic order and put $z_i=n_i{x}_i$, the aggregate service on route $i$. The resource constraints areThey involve every odd-even route pair, so they are equivalent toFor given maxima, increasing each active odd service to $p$ and each active even service to $q$ remains feasible and improves utility. Apart from the constant $-{\sum }_i{n}_i\log n_i$, the objective therefore reduces toWhen both groups are present the constraint is tight, and differentiation gives $P/p=Q/(1-p)$. If one group is empty, the other receives unit aggregate service on each of its active routes. Thus the opposite-route reduction for a proportionally fair four-cycle yields, with $T=P+Q>0$,Inactive rates can be set to zero, including every rate in the empty state. In particular $n_{\{1,2\}}{x}_{\{1,2\}}=(n_{\{1,2\}}+n_{\{3,4\}})/{\sum }_r{n}_r$ whenever that route is active. This proves the required formula even when other routes are empty.