Narrow Results

Although regular expressions do not correspond univocally to regular languages, it is still worthwhile to study their properties and algorithms. For the average case analysis one often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward that asymptotic estimates obtained by considering the whole set of regular expressions are different from those obtained using a more refined set that avoids some large class of equivalent expressions. In this paper we study a set of expressions that avoid a given absorbing pattern. It is shown that, although this set is significantly smaller than the standard one, the asymptotic average estimates for the size of the Glushkov automaton for these expressions does not differ from the standard case. Furthermore, for this set the asymptotic density of $𝜀$-accepting expressions is also the same as for the set of all standard regular expressions.

Several efficient, but non-optimal, solutions to the Selection Problem on coarse grained parallel computers have appeared in the literature. We consider the example of the Saukas-Song algorithm; we analyze it without expressing the running time in terms of communication rounds. This shows that while in the best case the Saukas-Song algorithm runs in asymptotically optimal time, in general it does not. We propose another algorithm for coarse grained selection that has optimal expected running time.

The CDT subproblem, which minimizes a quadratic function over the intersection of two ellipsoids, is a classical quadratic programming problem. In this paper, we study a method of solving CDT with a positive Lagrangian duality gap. An efficient splitting algorithm is proposed for finding the global optimal solutions. A cutting plane is firstly added to divide the feasible set of CDT into two subsets, and then two new quadratic programming problems with ellipsoidal and linear constraints are generated accordingly. Using the newly developed technique — second-order cone constraints to enhance the efficiencies of the SDP relaxation-based algorithms on the two subproblems, an optimal solution of CDT can be acquired by comparing the objective values of the two subproblems. Numerical experiments show that the new algorithm outperforms the two recent SDP relaxation-based algorithms, the two-parameter eigenvalue-based algorithm and the solver Gurobi 9.5 for certain types of CDT.

In this paper, a novel unimodal chaotic system is presented which has stable Lyapunov exponents, a wider range of parameters and a larger phase space. In order to generate evenly distributed chaotic sequences, a general homogenization scheme is proposed with a rigorous mathematical proof. To generate high-quality pseudo-random number sequences, a PRNG scheme based on cross-coupling is designed. Theoretical derivation and experimental analysis fully demonstrate that the proposed PRNG has the ability to produce high-security random numbers with excellent random characteristics.

We consider a random variable expressed as the Euclidean distance between an arbitrary point and a random variable uniformly distributed in a closed and bounded set of a three-dimensional Euclidean space. Four cases are considered for this set: a union of disjoint disks, a union of disjoint balls, a union of disjoint line segments, and the boundary of a polyhedron. In the first three cases, we provide closed-form expressions of the cumulative distribution function and the density. In the last case, we propose two algorithms with complexity $O(nlnn)$, $n$ being the number of edges of the polyhedron, that computes exactly the cumulative distribution function. An application of these results to probabilistic seismic hazard analysis and extensions are discussed. Finally, we present an open source library, available at https://github.com/vguigues/Areas_Library, that implements the algorithms presented in this paper.

In this paper, we propose a new variables control chart, called the box-chart, to simultaneously monitor, on a single chart, the process mean and process variability for multivariate processes. The box-chart uses a probability integral transformation to obtain two independently and identically distributed uniform distributions. Therefore, a box-shaped (thus the name), two-dimensional control chart can be constructed. We discuss in detail on how to construct the box-chart. The proposed chart is applied to two real-life examples. The performance of the box-chart is also compared to that of the traditional T²- and |S|-charts.

We give an overview of probabilistic phenomena in metric discrepancy theory and present several new results concerning the asymptotic behavior of discrepancies D_N(n_kx) and sums ∑_ckf(n_kx) for sequences (n_k)_{k ≥ 1} of integers.

A short proof utilizing dynamical systems techniques is given of a necessary and sufficient condition for the normalized occupation measure of a Lévy process in a metrizable compact group to be asymptotically uniform with probability one.

Given any minimal ring extension $k\subset L$ of finite fields, several families of examples are constructed of a finite local (commutative unital) ring $A$ which is not a field, with a (necessarily finite) inert (minimal ring) extension $A\subset B$ (so that $B$ is a separable $A$-algebra), such that $A\subset B$ is not a Galois extension and the residue field of $A$ (respectively, $B$) is $k$ (respectively, $L$). These results refute an assertion of G. Ganske and McDonald stating that if $R\subseteq S$ are finite local rings such that $S$ is a separable $R$-algebra, then $R\subseteq S$ is a Galois ring extension. We identify the homological error in the published proof of that assertion. Let $(A,M)$ be a finite special principal ideal ring (SPIR), but not a field, such that $M$ has index of nilpotency $\alpha$ ($\ge 2$). Impose the uniform distribution on the (finite) set of ($A$-algebra) isomorphism classes of the minimal ring extensions of $A$. If $2\in M$ (for instance, if $A\cong \mathbb{Z}/2^{\alpha }\mathbb{Z}$), the probability that a random isomorphism class consists of ramified extensions of $A$ is at least $2/3$; if $2\notin M$ (for instance, if $A\cong \mathbb{Z}/p^{\alpha }\mathbb{Z}$ for some odd prime $p$), the corresponding probability is at least $3/4$. Additional applications, examples and historical remarks are given.

We study the distribution properties of sequences which are a generalization of the well-known van der Corput–Halton sequences on one hand, and digital (T,s)-sequences on the other. In this paper, we give precise results concerning the distribution properties of such sequences in the s-dimensional unit cube. Moreover, we consider subsequences of the above-mentioned sequences and study their distribution properties. Additionally, we give discrepancy estimates for some special cases, including subsequences of van der Corput and van der Corput–Halton sequences.

An exact formula for distribution of sequences of fractional parts is proved. This provides us with a possibility for computational study of their discrepancies by the means of integer-number programming.

We consider a large class of fast growing sequences of numbers U_n like the nth superfactorial , the nth hyperfactorial and similar ones. We show that their mantissas are distributed following Benford's law in the sense of the natural density. We prove that this is also verified by , by and is passed down to all the sequences obtained by iterating this design process. We also consider the superprimorial numbers and the products of logarithms of integers.

Using a recent improvement by Bettin and Chandee to a bound of Duke, Friedlander and Iwaniec [Bilinear forms with Kloosterman fractions, Invent. Math.128 (1997) 23–43] on double exponential sums with Kloosterman fractions, we establish a uniformity of distribution result for the fractional parts of Dedekind sums $s(m,n)$ with $m$ and $n$ running over rather general sets. Our result extends earlier work of Myerson [Dedekind sums and uniform distribution, J. Number Theory28 (1988) 233–239] and Vardi [A relation between Dedekind sums and Kloosterman sums, Duke Math. J.55 (1987) 189–197]. Using different techniques, we also study the least denominator of the collection of Dedekind sums $\{s(m,n):m\in {({\mathbb{Z}}/n{\mathbb{Z}})}^{\ast }\}$ on average for $n\in [1,N]$.

The well-known Three Gap Theorem states that there are at most three gap sizes in the sequence of fractional parts ${\{\alpha n\}}_{n<N}$. It is known that if one averages over $\alpha$, the distribution becomes continuous. We present an alternative approach, which establishes this averaged result and also provides good bounds for the error terms.

It is well known that sequences such as the Fibonacci numbers and the factorials satisfy Benford’s Law; that is, leading digits in these sequences occur with frequencies given by $P(d)={log}_{10}(1+1/d)$, $d=1,2,\dots ,9$. In this paper, we investigate leading digit distributions of arithmetic sequences from a local point of view. We call a sequence locally Benford distributed of order $k$ if, roughly speaking, $k$-tuples of consecutive leading digits behave like $k$ independent Benford-distributed digits. This notion refines that of a Benford distributed sequence, and it provides a way to quantify the extent to which the Benford distribution persists at the local level. Surprisingly, most sequences known to satisfy Benford’s Law have rather poor local distribution properties. In our main result we establish, for a large class of arithmetic sequences, a “best-possible” local Benford Law; that is, we determine the maximal value $k$ such that the sequence is locally Benford distributed of order $k$. The result applies, in particular, to sequences of the form $\{a^n\}$, $\{a^{n^d}\}$, and $\{n^{\beta }{a}^{n^{\alpha }}\}$, as well as the sequence of factorials $\{n!\}$ and similar iterated product sequences.

There have been results on uniform distribution modulo 1 of sequences of the form ${\{\alpha f(n)\}}_{n=1}^{\infty }$ where $f(n)$ is an arithmetic function and $\alpha$ is an irrational number. For example, ${\{\alpha n\}}_{n=1}^{\infty }$ (Bohl, Sierpiński and Weyl) and ${\{\alpha \mathrm{\Omega }(n)\}}_{n=1}^{\infty }$ (Erdős and Delange) have been shown to be uniformly distributed modulo 1 for all irrational numbers $\alpha$. De Koninck and Kátai have shown that ${\{\alpha \varphi (n)\}}_{n=1}^{\infty }$ and ${\{\alpha \sigma (n)\}}_{n=1}^{\infty }$ are uniformly distributed modulo 1 for a subset of irrational numbers $\alpha$. In this article, we will extend their result by showing that the sequences ${\{\alpha \varphi (n)\}}_{n=1}^{\infty }$ and ${\{\alpha \sigma (n)\}}_{n=1}^{\infty }$ are uniformly distributed modulo 1 when $\alpha$ is a non-Liouville number. The proof will use Weyl’s criterion, upper bounds of exponential functions established by Vinogradov and Vaughan, and the notion of a thin set established by Pollack and Vandehey. There are two corollaries that arise from the result of this article: ${\{10^{\alpha \varphi (n)}\}}_{n=1}^{\infty }$ and ${\{10^{\alpha \sigma (n)}\}}_{n=1}^{\infty }$ are strong Benford sequences for all non-Liouville numbers $\alpha$, and the sequences ${\{F(n)+\alpha \varphi (n)\}}_{n=1}^{\infty }$ and ${\{F(n)+\alpha \sigma (n)\}}_{n=1}^{\infty }$ are uniformly distributed modulo 1 for all non-Liouville numbers $\alpha$ and additive function F.

Two kinds of sequences, which are of interest in problems of uniform distribution and dynamical systems, are considered. The rotation sequences (or Kronecker sequences) (KS) are closely related to the orbits of the rotation map and the oscillation sequences (OS) are a discrete-time form of orbits of the simplest oscillators. The discrepancy of these sequences, which is a measure of deviation of the empirical distribution of a sequence from the ideal uniform distribution, is studied.

Assume that $n$ mobile sensors are thrown uniformly and independently at random with the uniform distribution on the unit interval. We study the expected sum over all sensors $i$ from $1$ to $n,$ where the contribution of the $i^{\mathrm{\text{th}}}$ sensor is its displacement from the current location to the anchor equidistant point $t_i=\frac{i}{n}-\frac{1}{2n},$ raised to the $a^{\mathrm{\text{th}}}$ power, when $a$ is an odd natural number.

As a consequence, we derive the following asymptotic identity. Fix $a$ positive integer. Let $X_{i:n}$ denote the $i^{\mathrm{\text{th}}}$ order statistic from a random sample of size $n$ from the Uniform$(0,1)$ population. Then

The following sections are included:

• INTRODUCTION

• PROBABILITY DISTRIBUTIONS FOR CONTINUOUS RANDOM VARIABLES
  • Continuous Random Variables
  • Probability Distribution Functions for Discrete and Continuous Random Variables

• THE NORMAL AND STANDARD NORMAL DISTRIBUTIONS
  • The Normal Distribution
  • Areas Under the Normal Curve
  • How to Use the Normal Area Table

• THE LOGNORMAL DISTRIBUTION AND ITS RELATIONSHIP TO THE NORMAL DISTRIBUTION (Optional)⁶
  • The Lognormal Distribution
  • Mean and Variance of Lognormal Distribution

• THE NORMAL DISTRIBUTION AS AN APPROXIMATION TO THE BINOMIAL AND POISSON DISTRIBUTIONS
  • Normal Approximation to the Binomial Distribution
  • Normal Approximation to the Poisson Distribution

• BUSINESS APPLICATIONS
  • Analyzing Earnings per Share and Rates of Return
  • Cost-Volume-Profit Analysis Under Uncertainty: The Normal Versus the Lognormal Approach
  • Investment Decision Making Under Uncertainty
  • Determination of Commercial Lending Rates¹³

• Summary

• Appendix 7A Mean and Variance for Continuous Random Variables
  • Areas Under Continuous Probability Density Function
  • Mean of Discrete and Continuous Random Variables
  • Variance for Discrete and Continuous Random Variables

• Appendix 7B Cumulative Normal Distribution Function and the Option Pricing Model

• Appendix 7C Lognormal Distribution Approach to Derive Option Pricing Model
  • Excel Program for Calculating Black–Scholes Call and Put Option Models

• Questions and Problems

The following sections are included:

• INTRODUCTION

• THE UNIFORM DISTRIBUTION
  • An Application of the Uniform Distribution in Quality Control

• STUDENT’S t DISTRIBUTION
  • Using the t Distribution to Analyze Audit Sampling Information

• THE CHI-SQUARE DISTRIBUTION AND THE DISTRIBUTION OF SAMPLE VARIANCE
  • The Chi-Square Distribution
  • The Distribution of Sample Variance

• THE F DISTRIBUTION

• THE EXPONENTIAL DISTRIBUTION
  • “No More Than 8 Items in This Line, Please!”

• MOMENTS AND DISTRIBUTIONS
  • The Second Moment and the Coefficient of Variation
  • The Third Moment and the Coefficient of Skewness
  • Kurtosis and the Coefficient of Kurtosis
  • Skewness and Kurtosis for Normal and Lognormal Distributions

• ANALYZING THE FIRST FOUR MOMENTS OF RATES OF RETURN OF THE 30 DJI FIRMS

• Summary

• Appendix 9A Derivation of the Mean and Variance for a Uniform Distribution
  • Calculating the Mean and Variance of a Uniform Distribution

• Appendix 9B Derivation of the Exponential Density Function
  • The Average Time Required to Find the Next Computer Program Error
  • The Probability of Truck Arrivals

• Appendix 9C The Relationship Between the Moment About the Origin and the Moment About the Mean

• Appendix 9D Derivations of Mean, Variance, Skewness, and Kurtosis for the Lognormal Distribution
  • Mean
  • Variance
  • Skewness
  • Kurtosis

• Appendix 9E Noncentral x² and the Option Pricing Model

• Questions and Problems

• Project II Project for Probability and Important Distributions