An occupation time identity for reflecting Brownian motion with drift

Summary This note is about an occupation time identity derived in [14] for reflecting Brownian motion with drift ]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>-\mu<0,$ RBM($-\mu$), for short. The identity says that for RBM($-\mu$) in stationary state ]]>(I^{+}_t, I^{-}_t) \rr (t-G_t,D_t-t),\qquad t\in \mathbb{R},$$ where $G_t$ and $D_t$ denote the starting time and the ending time, respectively, of an excursion from 0 to 0 (straddling $t$) and $I^{+}_t$ and $I^{-}_t$ are the occupation times above and below, respectively, of the observed level at time $t$ during the excursion. Due to stationarity, the common distribution does not depend on $t.$ In fact, it is proved in [9] that the identity is true, under some assumptions, for all recurrent diffusions and stationary processes. In the null recurrent diffusion case the common distribution is not, of course, a probability distribution. The aim of this note is to increase understanding of the identity by studying the RBM($-\mu$) case via Ray--Knight theorems.     

An Lp-view of the Bahadur-Kiefer Theorem

Summary Let ]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>]]>\alpha_n$ and $\beta_n$ be respectively the uniform empirical and quantile processes, and define $R_n = \alpha_n + \beta_n$, which usually is referred to as the Bahadur--Kiefer process. The well-known Bahadur-Kiefer theorem confirms the following remarkable equivalence: $\|R_n\| /\sqrt{\| \alpha_n \| }\, \sim \, n^{-1/4} (\log n)^{1/2}$ almost surely, as $n$ goes to infinity, where $\| f\| =\sup_{0\le t\le 1} |f(t)|$ is the $L^\infty$-norm. We prove that $\|R_n\|_2 /\sqrt{\| \alpha_n \|_1}\, \sim \, n^{-1/4}$ almost surely, where $\| \, \cdot \, \|_p$ is the $L^p$-norm. It is interesting to note that there is no longer any logarithmic term in the normalizing function. More generally, we show that $n^{1/4} \|R_n\|_p /\sqrt{\| \alpha_n \|_{(p/2)}}$ converges almost surely to a finite positive constant whose value is explicitly known.     

Exploiting structure in quantified formulas

We study the computational problem “find the value of the quantified formula obtained by quantifying the variables in a sum of terms.” The “sum” can be based on any commutative monoid, the “quantifiers” need only satisfy two simple conditions, and the variables can have any finite domain. This problem is a generalization of the problem “given a sum-of-products of terms, find the value of the sum” studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448–476]. A data structure called a “structure tree” is defined which displays information about “subproblems” that can be solved independently during the process of evaluating the formula. Some formulas have “good” structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By “generic algorithm,” we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of “local reductions” based on the “local replacement” of terms. Such local reductions “preserve formula structure” in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure.     

Limiting laws for long Brownian bridges perturbed by their one-sided maximum, III

Summary Results of penalization of a one-dimensional Brownian motion ]]>]]>]]>]]>]]>]]>]]>(X_t) $, by its one-sided maximum $\big(S_t=\sup_{0 \leq u \leq t}X_u\big)$, which were recently obtained by the authors are improved with the consideration - in the present paper - of the asymptotic behaviour of the likewise penalized Brownian bridges of length $t$, as $t\rightarrow \infty$, or penalizations by functions of $(S_t,X_t)$, and also the study of the speed of convergence, as $t\rightarrow \infty$, of the penalized distributions at time $t$.     

The Enumeration of Permutations with a Prescribed Number of “Forbidden” Patterns

We initiate a general approach for the fast enumeration of permutations with a prescribed number of occurrences of “forbidden” patterns that seems to indicate that the enumerating sequence is always P-recursive. We illustrate the method completely in terms of the patterns “abc,” “cab,” and “abcd.”     

Polynomial identity rings as rings of functions

We generalize the usual relationship between irreducible Zariski closed subsets of the affine space, their defining ideals, coordinate rings, and function fields, to a non-commutative setting, where “varieties” carry a PGL_n-action, regular and rational “functions” on them are matrix-valued, “coordinate rings” are prime polynomial identity algebras, and “function fields” are central simple algebras of degree n. In particular, a prime polynomial identity algebra of degree n is finitely generated if and only if it arises as the “coordinate ring” of a “variety” in this setting. For n=1 our definitions and results reduce to those of classical affine algebraic geometry.     

CDS simulation and pattern formation of phase separation

Several properties of the generation and evolution of phase separating patterns for binary material studied by CDS model are proposed. The main conclusions are (1) for alloys spinodal decomposition, the conceptions of “macro-pattern” and “micropattern” are posed by “black-and- white graph” and “gray-scale graph” respectively. We find that though the four forms of map f that represent the self-evolution of order parameter in a cell (lattice) are similar to each other in “macro-pattern”, there are evident differences in their micro-pattern, e.g., some different fine netted structures in the black domain and the white domain are found by the micro-pattern, so that distinct mechanical and physical behaviors shall be obtained. (2) If the two constitutions of block copolymers are not symmetric (i.e. r ≠ 0.5), a pattern called “grain-strip cross pattern” is discovered, in the 0.43 <r <0.45.     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.     

A random walk proof of the Erdős-Taylor conjecture

Summary For the simple random walk in ]]>\mathbb{Z}^2$ we study those points which are visited an unusually large number of times, and provide a new proof of the Erdős-Taylor Conjecture describing the number of visits to the most visited point.     

k-Best Solutions under Distance Constraints in Valuated -Matroids

In discrete maximization problems one usually wants to find an optimal solution. However, in several topics like “alignments,” “automatic speech recognition,” and “computer chess” people are interested to find thekbest solutions for somek ≥ 2. We demand that theksolutions obey certain distance constraints to avoid that thekalternatives are too similar. Several results for valuated -matroids are presented, some of them concerning time complexity of algorithms.     

On deformation of associative algebras and graph homology

Deformation theory of associative algebras and in particular of Poisson algebras is reviewed. The role of an “almost contraction” leading to a canonical solution of the corresponding Maurer–Cartan equation is noted. This role is reminiscent of the Homotopical Perturbation Lemma, with the infinitesimal deformation cocycle as “initiator.”Applied to star-products, we show how Moyal's formula can be obtained using such an almost contraction and conjecture that the “merger operation” provides a canonical solution at least in the case of linear Poisson structures.     

Semi-parametric multivariate modelling when the marginals are the same

A model is developed for multivariate distributions which have nearly the same marginals, up to shift and scale. This model, based on “interpolation” of characteristic functions, gives a new notion of “correlation”. It allows straightforward nonparametric estimation of the common marginal distribution, which avoids the “curse of dimensionality” present when nonparametically estimating the full multivariate distribution. The method is illustrated with environmental monitoring network data, where multivariate modelling with common marginals is often appropriate.     

Two examples of trilinear forms whose approximation numbers satisfy the appropriate summability properties but which are not nuclear or of Hilbert–Schmidt type

We give two examples of trilinear forms defined on Hilbert spaces such that the first one is not nuclear but the series of its approximations numbers is convergent and the second one is not a Hilbert–Schmidt form but the series of the square of its approximation numbers is convergent.     

Māl, enunciations, and the prehistory of Arabic algebra

Medieval Arabic algebra books intended for practical training generally have in common a first “book” which is divided into two sections: one on the methods of solving simplified equations and manipulating expressions, followed by one consisting of worked-out problems. By paying close attention to the wording of the problems in the books of al-Khwārizmī, Abū Kāmil, and Ibn Badr, we reveal the different ways the word māl was used. In the enunciation of a problem it is a common noun meaning “quantity,” while in the solution it is the proper noun naming the square of “thing” (shay '). We then look into the differences between the wording of enunciations and equations, which clarify certain problems solved without “thing,” and help explain the development of algebra before the time of al-Khwārizmī.     

Passage to the limit in Proposition I, Book I of Newton's Principia

The purpose of this paper is to analyze the way in which Newton uses his polygon model and passes to the limit in Proposition I, Book I of his Principia. It will be evident from his method that the limit of the polygon is indeed the orbital arc of the body and that his approximation of the actual continuous force situation by a series of impulses passes correctly in the limit into the continuous centripetal force situation. The analysis of the polygon model is done in two ways: (1) using the modern concepts of force, linear momentum, linear impulse, and velocity, and (2) using Newton's concepts of motive force and quantity of motion. It should be clearly understood that the term “force” without the adjective “motive,” is used in the modern sense, which is that force is a vector which is the time rate of change of the linear momentum. Newton did not use the word “force” in this modern sense. The symbol F denotes modern force. For Newton “force” was “motive force,” which is measured by the change in the quantity of motion of a body. Newton's “quantity of motion” is proportional to the magnitude of the modern vector momentum. Motive force is a scalar and the symbol F_m is used for motive force.     

Genetic algorithms with noisy fitness

The convergence properties of genetic algorithms with noisy fitness information are studied here. In the proposed scheme, hypothesis testing methods are used to compare sample fitness values. The “best” individual of each generation is kept and a greater-than-zero mutation rate is used so that every individual will be generated with positive probability in each generation. The convergence criterion is different from the frequently-used uniform population criterion; instead, the sequence of the “best” individual in each generation is considered, and the algorithm is regarded as convergent if the sequence of the “best” individuals converges with probability one to a point with optimal average fitness.     

Estimate for a Rearrangement of a Function Satisfying the “Reverse Jensen Inequality”

We show that an equimeasurable rearrangement of any function satisfying the “reverse Jensen inequality” with respect to various multidimensional segments also satisfies the “reverse Jensen inequality” with the same constant.__________Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 2, pp. 158–169, February, 2005.     

Acquiring new use of multiplication through classroom teaching: an exploratory study

This article analyzes the process in which pupils acquire new uses of multiplication to measure area. Behaviors of five 4th-grade pupils in a series of lessons on areas were studied in depth by qualitative case-study methodology. Their use of multiplication changed as the lesson evolved, characterized conceptually as “using multiplication as a label,” “using it positively to approach problems which have not been solved before,” and “using it effectively to achieve the goal of measuring areas.” These three phases show the pupils’ understanding of multiplication in the context of measuring areas from a secondary accompaniment to a powerful tool of thinking. The phases observed and the students’ progress between the phases differs noticeably among the pupils. Factors that foster learners’ progress are investigated by comparing their behaviors.     

Bicolored graph partitioning, or: gerrymandering at its worst

This study is motivated by an electoral application where we look into the following question: how much biased can the assignment of parliament seats be in a majority system under the effect of vicious gerrymandering when the two competing parties have the same electoral strength? To give a first theoretical answer to this question, we introduce a stylized combinatorial model, where the territory is represented by a rectangular grid graph, the vote outcome by a “balanced” red/blue node bicoloring and a district map by a connected partition of the grid whose components all have the same size. We constructively prove the existence in cycles and grid graphs of a balanced bicoloring and of two antagonist “partisan” district maps such that the discrepancy between their number of “red” (or “blue”) districts for that bicoloring is extremely large, in fact as large as allowed by color balance.