A randomized algorithm may terminate almost surely even though exceptional random tapes make it run forever. This paper studies the survival tail, the Kolmogorov complexity of one such tape, and the Hausdorff dimension of all of them. For each $s>0$ at which the powered repair matrices commute, the main theorem bounds $\sum_wP[w]^s$ over surviving prefixes $w$, uniformly over deterministic nonanticipating selectors. The case $s=1$ controls termination; the full family gives weak-source and dimension bounds. The source powers contain information absent even from the ordinary repair kernel and the complete stopping-time law. Under one common finite tape source, two overlapping disagreement-repair rules on a four-vertex path have the same ordinary kernels and the same stopping-time law for every selector, yet their nontermination dimensions can be arbitrarily close to zero and one. At one common source-power level, the same dominated tape source makes one rule run forever but gives the other an exponential stopping tail. The separation is caused by action labels that produce the same state transition and are therefore invisible at power one. For bounded-dependence $k$-SAT, conditional block min-entropy above the trace-growth threshold gives exponential termination, and the effective dimension of an individual infinite run is bounded by the trace growth induced by the clauses repaired infinitely often. Tree formulas asymptotically attain the maximum-degree dimension and global source bounds, while clique formulas attain the graph-specific one-step threshold in the stated regime. An exact backward likelihood identity complements these setwise results with tail and coding bounds for each run.
We prove Breiman's conjecture under the first-moment assumption. Let $Y_1,Y_2,\ldots$ be iid nonnegative random variables with $\mathbb P\{Y_1>0\}>0$, normalized by their sum. If the resulting randomly weighted sum converges to a nondegenerate law for one fixed integrable, nonconstant mark distribution, then the tail of $Y_1$ is regularly varying. More generally, any full-sequence limit for one such mark, including a constant limit, determines the asymptotic regime of the ranked weights: one big jump, a Poisson$\unicode{x2013}$Dirichlet partition, or dust. It consequently determines the limit for every integrable mark, with convergence in the $1$-Wasserstein metric, and the limits of independently marked empirical measures. The inverse step is based on a countable power-sum theorem: signed Fourier$\unicode{x2013}$Mellin identities extract a positive limiting expected power sum from one nondegenerate marked limit, without a moment of order greater than one. A ratio$\unicode{x2013}$Tauberian argument then recovers the tail index. The same method classifies ratios formed from the marked jumps of a nonzero, unkilled, driftless subordinator at zero and at infinity, assuming infinite activity at zero. A nondegenerate limit is equivalent to regular variation of the L\'evy tail with index in $(-1,0]$. A constant limit is equivalent to disappearance of the largest normalized jump, or, analytically, to slow variation of the integrated L\'evy tail. The latter condition need not imply regular variation of the L\'evy tail with index $-1$. A Cauchy-mark example shows that the conclusion can fail without integrability of the mark.
We give a counterexample to the convergence conjecture in Remark 12 of [Bolte&Pauwels, 2021] for mini-batch stochastic approximation with definable potentials. The construction uses two convex piecewise-affine, hence semialgebraic, summands on $\mathbb{R}$. We choose a deterministic nonincreasing block stepsize sequence satisfying $\alpha_k = o(1/\log k)$ and an admissible minimum-norm selection from each aggregate batch field. On successive blocks, the iterates form lazy reflected random walks on nested dyadic lattices. An explicit endpoint-cover-time estimate, Markov's inequality, and the first Borel-Cantelli lemma imply that almost surely every sufficiently late block's iterates visit their entire lattice. Consequently, the iterates remain in $[-1,1]$ but do not converge, and their accumulation set is exactly $[-1,1]$, on which the averaged objective is constant. Finally, the construction has $\sum_k \alpha_k^2 =\infty$. Both Chat-GPT 5.6 (Sol) and Gemini Pro 3.1 (DeepThink) were used in the development and drafting of this result.
Bernard and Letac (1971) introduced a method for uniform random sampling among m outcomes from an unknown biased source of independent and identically distributed symbols. The process terminates when the multinomial coefficient of the cumulative symbol counts equals zero modulo m. This study extends the computational and information-theoretic analysis of their construction by presenting five algorithms with formal correctness guarantees and comprehensive complexity analyses. For prime m = p, the Bernard-Letac framework is analyzed in greater detail. The R\'enyi entropies of the source yield an exact product formula for the expected number of draws. A first-order approximation consistently overestimates this value, and the entropy lower bound is never attained. As p approaches 1, the expected cost converges to a constant greater than 1, determined by the entire source distribution. Furthermore, a seven-state automaton computes the mod-2 first-passage kernel of the binary walk, reducing the fair assignment cost from quadratic to nearly linear.
Resolvent Monte Carlo estimates eigenvalues of large matrices by sampling Markov chains and reading the target value off a truncated resolvent quotient, trading exact arithmetic for a stochastic error that the almost-optimal sampling scheme is designed to suppress. This paper studies when that error vanishes outright. An exact closed-form identity is derived for the variance of the moment estimators of a general, possibly signed matrix, and is used to isolate a hierarchy of zero-variance notions ranging from the most local, which constrains only the first draws, through the finite-truncation regime that a practical run can certify, to the global regime in which every moment estimator is deterministic. Determinism of the estimator is separated from correctness of the eigenvalue it reports, and the exact conditions under which each notion holds are exhibited, together with the examples that separate them. A single edgewise condition, termed the eigen-triple condition, forces the truncated quotient to equal the target eigenvalue in finite samples; the associated moment and quotient variances are second order in the maximal edge defect and vanish at the eigen-triple. A linear-time procedure certifies the condition.
Tsvetelina Kostadinov, I. Dimov· Mathematics· 0 citations
Accounting for information flow on the path space of trajectories of a nonnegative martingale yields exact variational identities for it, even at arbitrary random times. This recovers the widely used classical concentration inequalities, from Ville to PAC-Bayes, and measures what each one discards. The tail a bound controls is itself a relative entropy, resolved by the chain rule into per-step conditional divergences. The discarded slack has an exact form in each of three geometries: a Gibbs tilt for the Azuma-Hoeffding and PAC-Bayes bounds, the crossing itself for Ville's and for pooled tests, and a dominating certificate for the $L^p$ maximal bound. That certificate's optional-stopping deficit resolves per step into Bregman divergences of the running maximum. On a path-time space, the same identity gains one factor that prices anticipation: an arbitrary random time carries an e-process ``peeking penalty.''The partition function can be read as a coalescent--a prefix-sharing probability of independent copies--and geometric mixtures of test martingales gain a pooling benefit for multi-model safe testing.
We give explicit complex polynomials $P,Q$ in three independent standard real Gaussian variables such that \[ {\mathbb E}(P^m)=0,\qquad {\mathbb E}(QP^m)=m!\neq0 \] for every $m\geq1$. In natural complex linear coordinates, $P$ has five terms and total degree $4$. Hence the Gaussian Moments Conjecture is false in every dimension $n\geq3$. We also give a six-term cubic example in four variables, which was found first and already proves failure for every $n\geq4$. Both examples follow from the same coefficient identity. The search was prompted by Levent Alp\"oge's public announcement of an explicit three-dimensional counterexample to the Jacobian Conjecture. Although the main theorem of Derksen, van den Essen, and Zhao is stated globally in dimension, its proof has fixed-dimensional content: a noninvertible cubic-homogeneous Keller map in $r$ variables forces the failure of ${\mathrm GMC}(2r)$. Tracking a standard Bass--Connell--Wright reduction of the announced map gives a conservative cubic-homogeneous counterexample in $79$ variables, and hence a route-based failure of ${\mathrm GMC}(158)$. That route is nonconstructive at the final Gaussian step and does not furnish explicit polynomials $P,Q$. The much smaller explicit failures in dimensions $4$ and $3$ below were not derived from the announced Jacobian map.
Christopher D. Long· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
