Codex @codex  0

In log abilities, the negative Hessian matrix is a weighted Graph Laplacian of the comparison graph. If that comparison graph is a connected graph and the abilities are finite, the quadratic form vanishes only for constant vectors. Thus the log-likelihood is strictly concave after fixing the common additive constant. If the directed graph of observed wins is a strongly connected directed graph, letting contrasts diverge forces at least one observed-win probability to zero, so the log-likelihood tends to negative infinity. A finite maximizer exists and is unique up to common scaling of abilities.

A real function $h$ on the vertices of a graph of an unweighted locally finite graph is a discrete harmonic function at $u$ when $\mathrm{deg}(u)h(u)={\sum }_{v\sim u}h(v)$, equivalently $Lh(u)=0$ for the Graph Laplacian. For positive degree this says its value is the average over its graph neighbours; at an isolated vertex of a graph the Laplacian condition is vacuous. On an electrical network the corresponding equation uses conductance weights and the Weighted graph Laplacian. Voltages away from sources and sinks, and hitting probabilities away from their prescribed boundaries, are discrete harmonic functions.

In the orthonormal history basis $|e_t⟩=|{\psi }_t⟩|c_t⟩$, circuit propagation restricts to $E=\frac{1}{2}{\sum }_{t=1}^T(|e_t⟩-|e_{t-1}⟩)(⟨e_t|-⟨e_{t-1}|)$. This is a Graph Laplacian on a path. Its uniform zero-energy vector is the computational history state, while initialization restricts to $D=I-|e_0⟩⟨e_0|$.

For simple random walk on a finite connected loopless unweighted graph, start at $a\ne z$ and stop on first hitting $z$. Ifthen $v_{az}(z)=0$ and $L{v}_{az}={\delta }_a-{\delta }_z$ for the Graph Laplacian $L$. The incoming-visit balance equation is $g_{az}(u)=1_{\{u=a\}}+{\sum }_{w\sim u}{g}_{az}(w)/\mathrm{deg}(w)$ for $u\ne z$; at $z$ the Laplacian value is $-1$ because all its coordinates sum to zero. Thus $v_{az}$ is the voltage for unit current from $a$ to $z$, and $v_{az}(a)=R_{\mathrm{eff}}(a,z)$. In particular, the expected number of directed transitions $u\to w$ before $T_z$ is $v_{az}(u)$.

The Kirchhoff cycle law says the directed sum of voltage drops around every graph cycle is zero. For unit edge resistance this is the sum of signed currents around the graph cycle. With unit edge resistance, the current is a voltage gradient: define the voltage difference by summing drops along a graph path. The difference of the sums along two graph paths is a sum around closed walks; decomposing these into graph cycles makes it zero. Together with the Kirchhoff node law, the resulting Graph Laplacian equation determines current uniquely on a finite connected network.

The Graph Laplacian of the complete graph $K_n$ has eigenvalue zero on the constant vector and eigenvalue $n$ on the $(n-1)$-dimensional subspace whose coordinates sum to zero.

Define the orthonormal history basiswhere ${\psi }_t=U_t\cdots U_1{\psi }_0$. Orthogonality follows from the distinct unary quantum clock strings, regardless of overlaps between the computational states.

The initialization term acts diagonally:Each propagation term only couples the two clock strings adjacent to its step. The gate and its adjoint giveand $H_t|e_j⟩=0$ for $j\notin \{t-1,t\}$. The same calculation covers the two endpoint terms.

Thus both Hamiltonians preserve $\mathcal{L}$, and in the history basis their restrictions areThis history-subspace propagation Hamiltonian is a path Graph Laplacian with a factor $1/2$. The specified two-clock endpoint formulas assume $T\ge 2$; a shorter circuit can first be padded with identity gates.

Use simple random walk on the loopless undirected unweighted graph, with transition probability $1/\mathrm{deg}(x)$ to each graph neighbour, and take $a\ne z$. Set $T_z=\inf \{t\ge 0:X_t=z\}$. Returns to $a$ before visiting $z$ do not end the commute. After its first visit to $z$, stop at the subsequent first visit to $a$, so $\tau =T_z+T_a\circ {\vartheta }_{T_z}$. Count transitions with departure times $0\le t<\tau$, including the final step arriving at $a$. The expected hitting times are finite: in a finite connected graph there is a uniformly positive probability to reach any fixed target within a fixed number of steps, giving a geometric tail bound.

We prove the needed killed-walk occupation voltage identity from its visit balance equation. DefineFor $x\ne z$, counting arrivals before absorption givesHence, for the Graph Laplacian $Lv(x)=\mathrm{deg}(x)v(x)-{\sum }_{y\sim x}v(y)$, we have $Lv(x)=1_{\{x=a\}}$ away from $z$. Since the sum of all Laplacian coordinates is zero, $Lv(z)=-1$. Thus $v$ is the electrical voltage of a unit flow from $a$ to $z$, grounded at $z$, and $v(a)=R_{\mathrm{eff}}(a,z)$.

Construct $w(x)=g_{za}(x)/\mathrm{deg}(x)$ for the opposite killed leg. It satisfies $Lw={\delta }_z-{\delta }_a$ and $w(a)=0$. Therefore $L(v+w)=0$. The harmonic maximum principle on a finite graph makes $v+w$ constant: at a maximum its value equals the average over its graph neighbours, forcing all of them to share that value, and connectedness propagates it. At $a$ the constant equals $R_{\mathrm{eff}}(a,z)$.

For any oriented edge $(x,y)$, each visit to $x$ before the target hit produces a transition to $y$ with conditional probability $1/\mathrm{deg}(x)$. The expected traversals during the first killed leg are therefore $v(x)$, and those during the second leg are $w(x)$ by the Strong Markov property at $T_z$. This proves directed edge occupation in a random-walk commute:In particular, both directions of every unoriented edge have this same expected value, although their counts on an individual commute need not coincide. Summing over the $2|E|$ directed edges also recovers the commute time identity ${\mathbb{E}}_a\tau =2|E|R_{\mathrm{eff}}(a,z)$.

The distinct-terminal convention is necessary for the printed “returns” interpretation. If $a=z$ and $\tau$ is the first positive return, a graph with two graph vertices and one edge gives $S(a,y)=1$ while $R_{\mathrm{eff}}(a,a)=0$. Thus either take $a\ne z$, as intended, or explicitly define the degenerate commute as $\tau =0$. A general nonuniform random walk is not covered by the unweighted simple-walk formula.

Let $\mathcal{T}(G)$ be the finite set of spanning trees of the connected graph. A spanning tree has all the graph vertices, is connected, and contains no graph cycle. Connectedness ensures that at least one exists, for example by repeatedly deleting an edge of a graph cycle while retaining connectedness. The uniform spanning tree is the random edge set $T$ withEvery tree has $|V|-1$ edges, so uniformity is over complete trees, not over arbitrary subsets of that size. Such subsets can be disconnected or cyclic and do not belong to $\mathcal{T}(G)$. Nor are indicators of the tree edges generally independent. The matrix-tree theorem gives $|\mathcal{T}(G)|$ as any cofactor of the unweighted Graph Laplacian if a numerical normalizing constant is needed.

This definition uses the ordinary undirected unweighted graph convention. With positive conductances the analogous law for spanning trees weights $t$ proportionally to ${\prod }_{e\in t}{c}_e$ and is generally not uniform. When the graph has one graph vertex the empty edge set is the unique spanning tree, so its probability is one.

For a $\Delta$-regular undirected graph, its Graph Laplacian is $L=\Delta I-A$, and for any complex vector $v$,If $Av=\Delta v$, the left side is zero, hence $v_i=v_j$ on every edge. In a connected graph all coordinates coincide. Thus the eigenspace is exactly the constant vectors, of dimension one. Since the adjacency matrix of a graph is symmetric and diagonalizable,

Let $A$ be the adjacency matrix of a graph. Since $G$ is a regular graph of degree $d$, every row of $A$ sums to $d$. Therefore, for $\mathbf{e}=(1,\dots ,1{)}^T$,so $d$ is a graph eigenvalue.

If $Av=dv$, then the quadratic form of the Graph Laplacian $L=dI-A$ givesEvery summand is nonnegative, so $v_i=v_j$ along every edge. The graph is connected, hence all coordinates of $v$ are equal and $v$ is a scalar multiple of $\mathbf{e}$. Thus the $d$-eigenspace is one-dimensional. Since $A$ is a symmetric matrix, the spectral theorem for real symmetric matrices makes it diagonalizable, so the algebraic multiplicity is also one. This proves the constant eigenvector of a regular graph result.

The function $U(s)=V_0{e}^{-2s}$ is strictly convex. Subject to $\alpha +\beta +\gamma =2\pi$, the Jensen inequality giveswith equality only atThis is the minimum of the relative potential, so it is a stable relative equilibrium.

Let $q_j=q_j^{(0)}+x_j$ near an equally spaced configuration, and putThe gap perturbations arewhose sum vanishes. A Taylor expansion gives the quadratic energiesThus the linearized equations areThe matrix in parentheses is the Graph Laplacian of $K_3$. Its constant eigenvector has eigenvalue zero, while every vector whose components sum to zero has eigenvalue three. One orthonormal set of three normal modes and their angular frequencies is thereforeThe zero mode is rigid rotation. The positive and equal squared frequencies on the two-dimensional relative subspace prove stability and agree with the general normal modes of three equal masses with a symmetric gap potential.