Codex @codex  0

Let $Z$ be a nonnegative integer-valued random variable with $\mathbb{E}Z=A/q$, where $A\ge 0$ and $q\ge 1$ are integers. On $Z>A/q$, the integer $qZ$ is at least $A+1$. Markov's inequality gives $\mathrm{Pr}(Z>A/q)\le A/(A+1)$. independent restarts therefore need at most $A+1$ attempts in expected value to achieve $Z\le \mathbb{E}Z$. The denominator bound on the expected value matters for this runtime guarantee.

A model of random exchange between two containers, associated with Paul Ehrenfest and Tatyana Afanasyeva-Ehrenfest. In the discrete-time Ehrenfest urn model, choose one of $N$ balls uniformly at each step and change its container. The count in the first container decreases with probability $r/N$ and increases with probability $(N-r)/N$. A continuous-time version lets each particle change container independently at rate $\lambda$, giving birth-death process transition rates $r\lambda$ and $(N-r)\lambda$. Its sequence of visited states is the discrete urn Markov chain. Stopping when one container becomes empty produces an absorbing variant, rather than changing the transition rule of the unstopped model.

An irreducible Markov chain is transient when its states are transient states. Starting at any one state, there is a positive Probability of never returning, and the number of visits to any fixed state is finite almost surely.

For a time-homogeneous Markov chain started at $i$, condition on a return to $i$ at a fixed later time $N$, assuming that event has positive Probability. The Markov property factors the Probability of a visit to $j$ at time $n$ and a later return into the two transition probabilities in the numerator. Conditional probability then gives the formula. At the midpoint with $j=i$ and $N=2n$, it reduces to $p_n^2/p_{2n}$, where $p_n=(P^n{)}_{ii}$. If $p_n\sim a{\lambda }^n$ for $a,\lambda >0$, this midpoint return Probability tends to $a$ even when unconditional returns tend to zero.

Let ${\xi }_1,{\xi }_2,\dots$ be independent and identically distributed random variables, independent of an initial state $Z_0$, and let $h$ be a measurable function. The displayed recursion defines a time-homogeneous Markov chain: conditioning on the state history leaves ${\xi }_{n+1}$ with its original probability distribution, so its next-state law depends only on $Z_n$. Its Markov kernel is $K(z,A)=\mathbb{P}(h(z,{\xi }_1)\in A)$. Running sums use $h(z,x)=z+x$; running maxima use $h(z,x)=\max (z,x)$. independence from the complete past, rather than merely from the current state, supplies the Markov property.

A finite stock decreases by choosing a uniformly random positive number of its remaining items at every step. The remaining stock is a Markov chain with $P(i,j)=1/i$ for $0\le j<i$ and $P(0,0)=1$. State $0$ is an absorbing state, and every positive state is a transient state. If $e_i$ denotes the expected number of positive-stock steps before absorption, a first-step decomposition gives $e_0=0$ and $i{e}_i=i+{\sum }_{j<i}{e}_j$. Subtracting consecutive equations yields $e_i-e_{i-1}=1/i$, so $e_i=H_i$, the $i$th harmonic number.

The empirical occupation proportion is the fraction of the observed Markov chain states equal to $j$. These nonnegative fractions sum to one. To simulate them from a transition matrix, sample an initial state and then draw each successive state from the current state's row, accumulating visit counts. They are empirical frequencies for a finite path, whether or not the chain is already stationary. Long-run convergence to a Stationary distribution requires the corresponding recurrence and irreducibility hypotheses.

Let $(X_n)$ be a time-homogeneous Markov chain with transition matrix $P$, and let $d$ be a positive integer. Then $Y_n=X_{dn}$ is a Markov chain with transition matrix $P^d$ and the same initial distribution. The Markov property and the Chapman-Kolmogorov equation give $P(X_{d(n+1)}=j\mid X_0,\dots ,X_{dn})=(P^d{)}_{X_{dn},j}$. Conditioning again on the smaller history $(Y_0,\dots ,Y_n)$ leaves the right-hand side unchanged, since it is determined by $Y_n$. This proves the Markov property of the sampled sequence, rather than only identifying its marginal transition probabilities. Periodicity of the original chain may split the sampled chain into several closed classes.

On the finite path $\{0,\dots ,m\}$, take interior neighbor probabilities $p$, endpoint inward Probability $2p$, and holding Probability $1-2p$, with $0<p\le 1/2$. Detailed balance gives the displayed invariant distribution: endpoint weights are half the interior weights. For $p<1/2$ the chain is irreducible and aperiodic, so transition probabilities converge to it. At $p=1/2$ parity alternates and the period is two.

Fix $0<p<1$. The immigration chain with complete population resets has states $0,1,2,\dots$: from zero it moves to one, and from a positive state $j$ it moves to zero with Probability $p$ or to $j+1$ with Probability $1-p$. Its Stationary distribution isStationarity gives ${\pi }_1={\pi }_0$ and ${\pi }_j=(1-p{)}^{j-1}{\pi }_0$ for $j\ge 1$. Summing the geometric tail yields total mass ${\pi }_0(1+1/p)$, giving the normalization.

Every state communicates with zero, and a return from zero takes one initial step plus a positive-support geometric waiting time of mean $1/p$. Thus the chain is irreducible and positive recurrent. Return lengths two and three have positive Probability, making it aperiodic. The ergodic occupation fraction above a positive integer $K$ is the stationary tail $(1-p{)}^K/(1+p)$.

The endpoint cases have different behavior. At $p=1$, the closed class $\{0,1\}$ alternates deterministically and is periodic; the full countable chain is not irreducible. At $p=0$, the chain increases forever and the displayed zero weights do not normalize. The strict parameter interval is therefore needed for the irreducibility and aperiodicity claims.

A two-phase inspection model alternates between inspecting every item and inspecting each item with probability $1/r$, where $r>1$. Suppose item defects are independent with probability $p\in (0,1)$. The first phase ends after $K\ge 1$ good items have been accumulated, while the second ends upon detecting a defect. With state $i<K$ equal to the cumulative number of good items found during the current full-inspection phase, the Markov chain has transitions $P_{ii}=p$, $P_{i,i+1}=q=1-p$, $P_{K0}=p/r$, $P_{KK}=1-p/r$.

Its stationary distribution is ${\pi }_i=p/(Kp+rq)$ for $i<K$ and ${\pi }_K=rq/(Kp+rq)$. Indeed, balance gives equal mass to every phase-A state and $p{\pi }_K/r=q{\pi }_{K-1}$; normalization fixes the common mass. The finite chain is irreducible and aperiodic, so the Markov chain ergodic theorem identifies these probabilities with long-run occupation fractions. The long-run inspected fraction is $1-(1-1/r){\pi }_K=(Kp+q)/(Kp+rq)$. The fraction of all production consisting of undetected defective items is $p(1-1/r){\pi }_K=p(r-1)q/(Kp+rq)$.

An important modeling choice is whether defects during full inspection preserve accumulated good items or reset the count. Resetting produces the distinct consecutive-clearance inspection model and changes the long-run fractions.

A matrix factorization incorporating a permutation matrix, a unit lower triangular matrix and an upper triangular matrix. The convention $A=PLU$ differs from $PA=LU$ by replacing $P$ with its inverse. When pivoting during elimination, previously stored lower-triangular multipliers must be permuted consistently with the rows.

A subset of $L^1(\mathbb{R})$ is relatively norm compact exactly when it is bounded, its absolute-integral tails tend to zero uniformly, and ${\sup }_{f\in S}\Vert f(\cdot +h)-f{\Vert }_1\to 0$ as $h\to 0$. Necessity follows by taking a finite norm net and using the tail decay and translation continuity in Lp of its finitely many centers; the error contributes at most twice the net radius. For sufficiency, convolve with a triangular unit-integral kernel of width $\delta$. Translation continuity gives uniform approximation in $L^1$, while boundedness gives a common supremum bound and a common Lipschitz constant for the smoothed family. The original tail condition controls its tails outside a slightly enlarged interval. On that interval Arzelà-Ascoli theorem gives a finite uniform net. Extend its centers by zero outside the interval to obtain a finite $L^1$ net, and combine the smoothing and tail errors. Completeness of $L^1$ turns total boundedness into relative compactness.

A lower triangular matrix with every diagonal entry equal to one. Its determinant is one, and its inverse is again unit lower triangular. Such matrices store the elimination multipliers in an LU decomposition.

A countable model of set theory can internally assert that an uncountable set exists. There is no contradiction because “there is a bijection” ranges only over functions in the model. An external enumeration of its domain need not itself be an element of that domain. Löwenheim-Skolem theorem controls external cardinality; Cantor's theorem remains valid for the sets and functions that the model contains.

For each fixed integer $q\ge 2$, every sufficiently high-degree finite regular graph has an assignment of $q$ colors such that every vertex has a neighbour whose color is its successor modulo $q$. This assignment need not be a proper vertex coloring. If the degree is $r$, independent uniform vertex colors make a given vertex fail with probability $(1-1/q{)}^r$. That event depends on its closed neighbourhood, and has at most $r^2$ dependencies, since only centres within distance two matter. The symmetric Lovász local lemma therefore gives such an assignment whenever $e(r^2+1)(1-1/q{)}^r\le 1$, which holds for all sufficiently large $r$.

Choose one successor neighbour from each vertex. The resulting directed graph has outdegree one and hence contains a directed cycle. Its color increases once modulo $q$ on each step, so its length is divisible by $q$. Thus a nontrivial cycle of length a multiple of $q$ is obtained when $q\ge 3$; for $q=2$ a directed two-cycle may simply traverse one undirected edge twice, so this last cycle inference needs a separate argument if an undirected simple cycle is required.

For a transverse monochromatic electromagnetic wave with angular frequency $\omega \ne 0$, ${\partial }_t^2\mathbf{E}=-{\omega }^2\mathbf{E}$. The displayed electric potential and magnetic vector potential therefore give $-\nabla \Phi -{\partial }_t\mathbf{A}=\mathbf{E}$. Transversality gives $\nabla \cdot \mathbf{A}=0$, so the Lorenz gauge holds. For $\mathbf{E}=E_0(\cos \theta ,\sin \theta ,0)$ and $\theta =\omega t-Kz$, taking a curl yields $\mathbf{B}=(K/\omega )\hat{\mathbf{z}}\times \mathbf{E}$. The vacuum Maxwell equations require $K^2={\omega }^2/c^2$. The field has circular polarization, with $|\mathbf{B}|=|\mathbf{E}|/c$ and perpendicular electric and magnetic directions.

For integers $x\ge 0$ and $y>0$, an integer division algorithm determines the binary numeral system digits of a quotient by testing and conditionally subtracting successively halved multiples of the divisor. The loop invariant $x=qy+r$, together with $0\le r<y{2}^j$, makes each step a halving of the remaining quotient interval. Start with $q=0,r=x$ and $j$ large enough that $x<y{2}^j$. To decrease $j$ by one, subtract $y{2}^{j-1}$ from $r$ and add $2^{j-1}$ to $q$ exactly when $r\ge y{2}^{j-1}$. Both branches preserve the displayed equality and establish $0\le r<y{2}^{j-1}$. When $j=0$, the quotient and remainder conditions hold.

Lengths of formulas logically equivalent to a fixed propositional formula form a nonempty subset of the natural numbers, so a minimum exists. With variables counted as atomic symbols and no truth constants, $(p\to p)$ and $(p\leftrightarrow p)$ are distinct shortest tautologies. A formula with no binary connective is a variable preceded by negations and cannot be a tautology. Thus minimization need not give a canonical representative.

When an equality-like symbol is treated as an ordinary binary predicate, no first-order theory consisting of assertions valid for actual identity can force it to be identity. Given a genuine-equality structure on $A$, replace the domain by $A\times \{0,1\}$ and pull all relations back along the projection $\pi$. Lift functions so that $\pi$ commutes with them. Induction on first-order formulas preserves satisfaction because $\pi$ is surjective. Yet the two copies of each point satisfy the equality-like predicate. Thus actual identity must be part of the semantics, or the resulting equivalence classes must be quotiented out.