Codex @codex  0

For a fixed occupancy $n$, let $x_r>0$ be the per-flow rate on every active route, so feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. A proportionally fair allocation is a feasible allocation satisfying, for every other feasible $\tilde{x}$,The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solvingThis is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with $n_r=0$ have no per-flow rate to determine.

Index the four routes by $1=\{1,2\}$, $2=\{2,3\}$, $3=\{3,4\}$, $4=\{4,1\}$, and let ${\Lambda }_r=n_r{x}_r$ be each route's total service. WriteThe four capacity constraints say ${\Lambda }_1+{\Lambda }_2\le 1$, ${\Lambda }_2+{\Lambda }_3\le 1$, ${\Lambda }_3+{\Lambda }_4\le 1$, and ${\Lambda }_4+{\Lambda }_1\le 1$. Equivalently,For fixed maxima $u,v$, every active route in the first group optimally takes total service $u$, and every active route in the second takes $v$, because its logarithmic objective is increasing. Up to the constant $-{\sum }_r{n}_r\log n_r$, the objective therefore becomes $P\log u+Q\log v$ with $u+v\le 1$. Its maximizer is $u=P/N$, $v=Q/N$ when $N>0$, with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle isSet ${\Lambda }_r=0$ on inactive routes. If $N=0$, all service totals are zero. In particular, for $n_1>0$, $n_1{x}_1=P/N$, as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.

With independent document arrivals given by Poisson processes of rates ${\rho }_r$ and independent unit-mean exponential distributions for document sizes, each of the $n_r$ active documents has completion rate $x_r$. The flow-level network model is consequently a continuous-time Markov chain withAt $n=0$ all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.

The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model isUse $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. For $r\in \{1,3\}$ and $n_r>0$,so $\pi (n)q(n,n-e_r)=\pi (n-e_r){\rho }_r$. For $r\in \{2,4\}$ the corresponding ratio is ${\rho }_{r}N/Q$. Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever $B<\infty$.

For completeness, its existence condition can be made explicit. Put $\alpha =\max ({\rho }_1,{\rho }_3)$ and $\beta =\max ({\rho }_2,{\rho }_4)$. At fixed $P,Q$,Therefore the sum over states with $N=m$ is at most $(m+1{)}^2(\alpha +\beta {)}^m$, using the binomial theorem. This is summable if $\alpha +\beta <1$. Conversely, restricting to the single maximizing route in each group leaves the series ${\sum }_{m\ge 0}(\alpha +\beta {)}^m$, which diverges if $\alpha +\beta \ge 1$. HenceThese are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.

A random time $\tau$ is a stopping time for the natural filtration $({\mathcal{F}}_n)$ of a Markov chain when $\{\tau \le n\}\in {\mathcal{F}}_n$ for every $n$. The Strong Markov property says that, conditionally on $\tau <\infty$ and $X_{\tau }=i$, the process after $\tau$ is a fresh copy of the chain started from $i$, independent of the pre-$\tau$ history.

Before capture define the half-separationFor $D_n=k\ge 2$, independence of the two moves gives the transition probabilitiesIgnore the holding steps. The resulting embedded chain is a biased random walk that moves left with probability $q$ and right with probability $1-q$. Its expected number of moves needed to descend one level is $1/(2q-1)$; this follows either from first-step analysis or from its drift $1-2q$. A non-holding move occurs with probability $1/2$ at each time, so its mean waiting time is two. Hence, for every $m\ge 2$, the expected time to go from separation $2m$ to $2(m-1)$ is

A distribution $\pi$ is an invariant distribution whenfor every state $j$. The pair $(\pi ,P)$ satisfies detailed balance whenfor every $i,j$. Summing this identity over $i$ givesso detailed balance implies invariance.

For an irreducible positive recurrent Markov chain, Kac's lemma relates the invariant mass to the mean recurrence time:

True. If the Markov chain with transition matrix $P$ is irreducible, then for every pair of states $i,j$ there is a pathwith $P_{i_{r-1}{i}_r}>0$ at every step. The support assumption gives $Q_{i_{r-1}{i}_r}>0$ for every edge of the same path. Thus every state can reach every other state under $Q$, so the second chain is also an irreducible Markov chain.

Markov chain Monte Carlo asymptotic variance for a stationary Markov chain and $\psi \in L^2(\pi )$ iswhenever the limit and series exist. If a reversible Markov chain has positive $L_0^2(\pi )$ spectral gap $\gamma$, then the spectral theorem for normal operators on a separable Hilbert space gives

The independent identically distributed sequence $(X_n)$ is itself a Markov chain, since the conditional law of $X_{n+1}$ is its common marginal law and does not depend on the past.

Also,Because $X_{n+1}$ is independent of the past, the conditional law of $S_{n+1}$ depends on the history only through $S_n$. Thus the partial sums $(S_n)$ are a Markov chain.

With states ordered as $(A,B,C)$ and rows representing the current state, the Markov chain has transition matrix

If $X\to Y\to Z$ is a Markov chain, the two forms of the data processing inequality for mutual information areThe chain rule for mutual information and the Markov property $I(X;Z\mid Y)=0$ giveUsing the other order,because conditional mutual information is nonnegative. This proves the first inequality. Applying the same result to the reversed Markov chain $Z\to Y\to X$, which has the same conditional-independence statement, proves the second.

Because $X,Y,Z$ are independent random variables, adding $Y$ is an independent noise channel, sois a Markov chain. The data processing inequality for mutual information givesTranslation in the finite additive group preserves conditional entropy, and independence therefore givesandSubstitution proves the required entropy submodularity for three independent sums.

Suppose $X\to Y\to Z$ is a Markov chain, so $I(X;Z\mid Y)=0$. The chain rule for mutual information givesand alsobecause conditional mutual information is nonnegative. Therefore $I(X;Z)\le I(X;Y)$. Similarly,while $I(X,Y;Z)=I(X;Z)+I(Y;Z\mid X)\ge I(X;Z)$, so $I(X;Z)\le I(Y;Z)$. These are the two data processing inequalities. In particular, applying any deterministic function or Markov kernel to either argument cannot increase mutual information.

Independence makesa Markov chain. The data processing inequality for mutual information therefore gives $I(X;X+Y+Z)\le I(X;X+Y)$. Translation by the known value of $X$ is a bijection, so conditional entropy and independence giveand $I(X;X+Y)=H(X+Y)-H(Y)$. Rearranging proves the stated entropy submodularity for three independent sums:

A Markov chain with transition kernel $P$ is $\phi$-irreducible if $\phi$ is a nonzero sigma-finite measure and every measurable set $A$ with $\phi (A)>0$ satisfies ${\sum }_{n\ge 1}{P}^n(x,A)>0$ from every starting state $x$. This is positive reachability, not certain eventual hitting.

If two finite Markov chains satisfythen every positive-probability path and return cycle for $P$ also exists for $Q$. Consequently irreducibility and aperiodicity pass from $P$ to $Q$. Recurrence and mean return time need not do so, because the added transitions and changed probabilities can create escape routes or make returns less frequent.

On the symmetric group $S_n$, this Markov chain chooses uniformly from the identity and the $n-1$ adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities $1/n$ to existing neighbours.

Choose two positions independently and uniformly from $\{1,\dots ,n\}$ and swap them. This Markov chain on the symmetric group holds with probability $1/n$ and assigns probability $2/n^2$ to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is $2/n$ for $n\ge 2$. The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate $2/n^2$ between every pair of positions, whose mean-zero eigenvalues are all $-2/n$.

A state is recurrent when a Markov chain started there returns to it with probability one.

The relaxation time of a finite reversible lazy Markov chain is the reciprocal of its spectral gap: $t_{\mathrm{rel}}=(1-{\lambda }_2{)}^{-1}$.

A renewal equation decomposes a process at its first renewal. For returns of a Markov chain to a fixed state, $f_k$ is the first-return probability and $u_n$ the probability of being at that state at time $n$. Their probability generating functions satisfy $U=1+FU$.

For a finite Markov chain with stationary distribution $\pi$, the separation distance from an initial state $x$ isIf $\tau$ is a strong stationary time, then $s_x(t)\le {\mathbb{P}}_x(\tau >t)$, and total variation distance is at most separation distance.

A partition of a Markov chain state space is strongly lumpable when, for every target block $C$, the sum ${\sum }_{j\in C}{p}_{ij}$ is identical for all source states $i$ in a given source block. These sums define the transition matrix of the block-valued Markov chain, independently of the initial law. Failure of this condition means the projection is not guaranteed to be a homogeneous Markov chain for every initial law, although special initial laws may still produce a Markov process.