Mixing of the upper triangular matrix walk

We study a natural random walk over the upper triangular matrices, with entries in the field ${\mathbb{Z}_2}$ , generated by steps which add row i + 1 to row i. We show that the mixing time of the lazy random walk is O(n ²) which is optimal up to constants. Our proof makes key use of the linear structure of the group and extends to walks on the upper triangular matrices over the fields ${\mathbb{Z}_q}$ for q prime.     

New Coins from Old, Smoothly

Given a (known) function f:[0,1]→(0,1), we consider the problem of simulating a coin with probability of heads f(p) by tossing a coin with unknown heads probability p, as well as a fair coin, N times each, where N may be random. The work of Keane and O’Brien (ACM Trans. Model. Comput. Simul. 4(2):213–219, 1994) implies that such a simulation scheme with the probability ℙ _p (N<∞) equal to 1 exists if and only if f is continuous. Nacu and Peres (Ann. Appl. Probab. 15(1A):93–115, 2005) proved that f is real analytic in an open set S⊂(0,1) if and only if such a simulation scheme exists with the probability ℙ _p (N>n) decaying exponentially in n for every p∈S. We prove that for α>0 noninteger, f is in the space C ^α [0,1] if and only if a simulation scheme as above exists with ℙ _p (N>n)≤C(Δ _n (p)) ^α , where \varDelta _n(x):=max{?{x(1-x)/n},1/n}\varDelta _{n}(x):=\max\{\sqrt{x(1-x)/n},1/n\}. The key to the proof is a new result in approximation theory: Let B⁺_n\mathcal{B}^{+}_{n} be the cone of univariate polynomials with nonnegative Bernstein coefficients of degree n. We show that a function f:[0,1]→(0,1) is in C ^α [0,1] if and only if f has a series representation ?_n=1^￥F_n\sum_{n=1}^{\infty}F_{n} with F_n ? B⁺_nF_{n}\in \mathcal{B}^{+}_{n} and ∑ _k>n F _k (x)≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1. We also provide a counterexample to a theorem stated without proof by Lorentz (Math. Ann. 151:239–251, 1963), who claimed that if some j_n ? B⁺_n\varphi_{n}\in\mathcal{B}^{+}_{n} satisfy |f(x)−φ _n (x)|≤C(Δ _n (x)) ^α for all x∈[0,1] and n≥1, then f∈C ^α [0,1].     

Markov type and threshold embeddings

For two metric spaces X and Y, say that X threshold-embeds into Y if there exist a number K > 0 and a family of Lipschitz maps ${\{\varphi_{\tau} : X \to Y : \tau > 0\}}$ such that for every ${x,y \in X}$ , $$d_X(x, y) \geq \tau \implies d_Y(\varphi_\tau (x),\varphi_\tau (y)) \geq \|{\varphi}_\tau\|_{\rm Lip}\tau/K,$$ where ${\|{\varphi}_{\tau}\|_{\rm Lip}}$ denotes the Lipschitz constant of ${\varphi_{\tau}}$ . We show that if a metric space X threshold-embeds into a Hilbert space, then X has Markov type 2. As a consequence, planar graph metrics and doubling metrics have Markov type 2, answering questions of Naor, Peres, Schramm, and Sheffield. More generally, if a metric space X threshold-embeds into a p-uniformly smooth Banach space, then X has Markov type p. Our results suggest some non-linear analogs of Kwapien’s theorem. For instance, a subset ${X \subseteq L_1}$ threshold-embeds into Hilbert space if and only if X has Markov type 2.     

On the Hausdorff dimension of fibres

It is well known that there are planar sets of Hausdorff dimension greater than 1 which are graphs of functions, i.e., all their vertical fibres consist of 1 point. We show this phenomenon does not occur for sets constructed in a certain “regular” fashion. Specifically, we consider sets obtained by partitioning a square into 4 subsquares, discarding 1 of them and repeating this on each of the 3 remaining squares, etc.; then almost all vertical fibres of a set so obtained have Hausdorff dimension at least 1/2. Sharp bounds on the dimensions of sets of exceptional fibres are presented. Partially supported by a grant from the Landau Centre for Mathematical Analysis.     

Points of increase for random walks

Say that a sequenceS ₀, ..., S_n has a (global) point of increase atk ifS _k is maximal amongS ₀, ..., S_k and minimal amongS _k, ..., S_n. We give an elementary proof that ann-step symmetric random walk on the line has a (global) point of increase with probability comparable to 1/logn. (No moment assumptions are needed.) This implies the classical fact, due to Dvoretzky, Erdős and Kakutani (1961), that Brownian motion has no points of increase. Research partially supported by NSF grant # DMS-9404391.     

Application of Banach limits to the study of sets of integers

The Kamae and Mendes France version of the Van der Corput equidistribution theorem is extended further to summability methods different from Cesàro summability and groups different from the circle. The theorem is shown to follow naturally from consideration of Banach limits and spectral theory.     

Critical percolation on random regular graphs

The behavior of the random graph G(n,p) around the critical probability p_c = is well understood. When p = (1 + O(n^1/3))p_c the components are roughly of size n^2/3 and converge, when scaled by n^?2/3, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ?(n))p_c with ?(n)n^1/3 →∞ (the subcritical regime) the largest component is concentrated around 2?^?2 log(?³n). When p = (1 + ?(n))p_c with ?(n)n^1/3 →∞ (the supercritical regime), the largest component is concentrated around 2?n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Effect of hot acid etching on the mechanical strength of ground YAG laser elements

High-power pumped Nd:YAG elements may exceed their tensile strength under high thermally induced stress. Providing extra strength to such rods is essential for their employment in high-power lasers. The tensile strength of YAG elements was increased by chemical etching in concentrated phosphoric acid. The highest tensile strength was achieved by etching of fine-ground YAG components: an average for slabs, and for rods, which are 3.6 times and 5 times higher than those of non-etched elements, respectively. The measurements were carried out by four-point flexure strength test. We have established a dependency among the micro-roughness of YAG elements, the surface morphology obtained by etching, and the tensile strength: the tensile strength of the etched element improves for finer after-etch surface texture, which is obtained for finer initial micro-roughness.

To assure the withstanding of Nd:YAG rods under high thermal gradients, a new approach was employed, namely, increasing the pump-power applied to the Nd:YAG rod till fracture. Our results show an increase by more than 2.7 times in tensile strength of etched Nd:YAG rods as compared to standard commercial rods, which corresponds to a thermal loading of excess of 434 W/cm.     

Minimum-norm estimation for a bi-exponential survival model

We present a novel semi-parametric model for two-sample survival data, and an estimation method with a simple, closed-form solution. We study analytically the asymptotics of the estimators, and conduct a small simulation study.     

Evolving sets, mixing and heat kernel bounds

We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovász and Kannan, can be refined to apply to the maximum relative deviation |pⁿ(x,y)/π(y)−1| of the distribution at time n from the stationary distribution π. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.Research supported in part by NSF Grants #DMS-0104073 and #DMS-0244479.