On the star-discrepancy of generalized Hammersley sequences in two dimensions

From a previous study in one dimension, precise estimates are deduced for the star discrepancy of some generalized Hammersley sequences in two dimensions, giving the lower constants presently known; also general bounds are obtained, and it is shown that these bounds are reached by the usual Hammersley sequences.     

Point sets with low <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>-discrepancy

In this paper we study the L _p -discrepancy of digitally shifted Hammersley point sets. While it is known that the (unshifted) Hammersley point set (which is also known as Roth net) with N points has L _p -discrepancy (p an integer) of order (log N)/N, we show that there always exists a shift such that the digitally shifted Hammersley point set has L _p -discrepancy (p an even integer) of order which is best possible by a result of W. Schmidt. Further we concentrate on the case p = 2. We give very tight lower and upper bounds for the L ₂-discrepancy of digitally shifted Hammersley point sets which show that the value of the L ₂-discrepancy of such a point set mostly depends on the number of zero coordinates of the shift and not so much on the position of these. This work is supported by the Austrian Research Fund (FWF), Project P17022-N12 and Project S8305.     

Markov random fields,Markov cocycles and the 3-colored chessboard

The well-known Hammersley–Clifford Theorem states (under certain conditions) that any Markov random field is a Gibbs state for a nearest neighbor interaction. In this paper we study Markov random fields for which the proof of the Hammersley–Clifford Theorem does not apply. Following Petersen and Schmidt we utilize the formalism of cocycles for the homoclinic equivalence relation and introduce “Markov cocycles”, reparametrizations of Markov specifications. The main part of this paper exploits this to deduce the conclusion of the Hammersley–Clifford Theorem for a family of Markov random fields which are outside the theorem’s purview where the underlying graph is Z_d. This family includes all Markov random fields whose support is the d-dimensional “3-colored chessboard”. On the other extreme, we construct a family of shift-invariant Markov random fields which are not given by any finite range shift-invariant interaction.     

<Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> discrepancy of generalized two-dimensional Hammersley point sets

We determine the L _p discrepancy of the two-dimensional Hammersley point set in base b. These formulas show that the L _p discrepancy of the Hammersley point set is not of best possible order with respect to the general (best possible) lower bound on L _p discrepancies due to Roth and Schmidt. To overcome this disadvantage we introduce permutations in the construction of the Hammersley point set and show that there always exist permutations such that the L _p discrepancy of the generalized Hammersley point set is of best possible order. For the L ₂ discrepancy such permutations are given explicitly. F.P. is supported by the Austrian Science Foundation (FWF), Project S9609, that is part of the Austrian National Research Network “Analytic Combinatorics and Probabilistic Number Theory”.     

A thorough analysis of the discrepancy of shifted Hammersley and van der Corput point sets

We study the star discrepancy of Hammersley nets and van der Corput sequences which are important examples of low-dimensional quasi-Monte Carlo point sets. By a so-called digital shift, the quality of distribution of these point sets can be improved. In this paper, we advance and extend existing bounds on digitally shifted Hammersley and van der Corput point sets and establish criteria for the choice of digital shifts leading to optimal results. Our investigations are partly based on a close analysis of certain sums of distances to the nearest integer. Mathematics Subject Classi cation (2000) 11K38; 11K09     

A method for exact calculation of the stardiscrepancy of plane sets applied to the sequences of Hammersley

A method is given to calculate exactly the stardiscrepancy of arbitrary finite plane sets. Using this method the stardiscrepancy of the sequences of Hammersley is obtained. The recursive structure of these sets allows for a proof by induction.     

Enlargement of subgraphs of infinite graphs by Bernoulli percolation

We consider changes in properties of a subgraph of an infinite graph resulting from the addition of open edges of Bernoulli percolation on the infinite graph to the subgraph. We give the triplet of an infinite graph, one of its subgraphs, and a property of the subgraphs. Then, in a manner similar to the way Hammersley’s critical probability is defined, we can define two values associated with the triplet. We regard the two values as certain critical probabilities, and compare them with Hammersley’s critical probability. In this paper, we focus on the following cases of a graph property: being a transient subgraph, having finitely many cut points or no cut points, being a recurrent subset, or being connected. Our results depend heavily on the choice of the triplet.Most results of this paper are announced in Okamura (2016) [24] without proofs. This paper gives full details of them.     

On the L2-Discrepancy of the Sobol–Hammersley Net in Dimension 3

With the help of Walsh series analysis we show that the symmetrized Sobol–Hammersley net in base 2 and dimension 3 has almost best possible order of L₂ -discrepancy.     

On the -Discrepancy of the Hammersley Point Set

 We give a formula for the -discrepancy of the 2-dimensional Hammersley point set in base 2 for all integers p, .     

Weighted Uniform Sampling -- a Monte Carlo Technique for Reducing Variance

A new Monte Carlo technique for reducing variance is presentedand analysed. It obtains gains in accuracy comparable to thoserealized by importance sampling (Hammersley & Handscomb,1964), without requiring the use of non-uniform probabilitydistributions. Some numerical examples illustrate the theory.     

Busemann functions and equilibrium measures in last passage percolation models

The interplay between two-dimensional percolation growth models and one-dimensional particle processes has been a fruitful source of interesting mathematical phenomena. In this paper we develop a connection between the construction of Busemann functions in the Hammersley last-passage percolation model with i.i.d. random weights, and the existence, ergodicity and uniqueness of equilibrium (or time-invariant) measures for the related (multi-class) interacting fluid system. As we shall see, in the classical Hammersley model, where each point has weight one, this approach brings a new and rather geometrical solution of the longest increasing subsequence problem, as well as a central limit theorem for the Busemann function.     

Continuous approximation models in freight distribution management

This paper presents an overview of the literature on continuous approximation models in the context of distribution management. It first describes the seminal contributions of Beardwood, Halton and Hammersley, and of Daganzo and Newell. This is followed by a summary of various extensions, and by applications to districting, location, fleet sizing and vehicle routing.     

On an example of finite hybrid quasi-Monte Carlo point sets

In this paper, we consider finite hybrid point sets in the unit cube. The components of these stem from two well known types of low discrepancy point sets, namely Hammersley point sets on the one hand, and lattice point sets in the sense of Korobov and Hlawka on the other hand. As a quality measure, we consider the star discrepancy, which gives information about the quality of distribution of finite or infinite sequences. We present existence results for finite hybrid point sets with low discrepancy. Thereby, we make analogous results for infinite sequences more explicit in the sense that, theoretically, it is now possible to find such finite hybrid low discrepancy point sets.     

On the -Discrepancy of the Hammersley Point Set

 We give a formula for the -discrepancy of the 2-dimensional Hammersley point set in base 2 for all integers p, . Received 18 May 2001; in revised form 18 December 2001     

Traveling in randomly embedded random graphs

We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show a threshold for a pair of points to be connected by a geodesic of length arbitrarily close to their Euclidean distance, and analyze the minimum length Traveling Salesperson Tour, extending the Beardwood‐Halton‐Hammersley theorem to this setting.     

The rolling ball problem on the plane revisited

By a sequence of rollings without slipping or twisting along segments of a straight line of the plane, a spherical ball of unit radius has to be transferred from an initial state to an arbitrary final state taking into account the orientation of the ball. We provide a new proof that with at most 3 moves, we can go from a given initial state to an arbitrary final state. The first proof of this result is due to Hammersley ( 1983). His proof is more algebraic than ours which is more geometric. We also showed that “generically” no one of the three moves, in any elimination of the spin discrepancy, may have length equal to an integral multiple of 2π.     

Euclidean semi-matchings of random samples

A linear programming relaxation of the minimal matching problem is studied for graphs with edge weights determined by the distances between points in a Euclidean space. The relaxed problem has a simple geometric interpretation that suggests the name minimal semi-matching. The main result is the determination of the asymptotic behavior of the length of the minimal semi-matching. It is analogous to the theorem of Beardwood, Halton and Hammersley (1959) on the asymptotic behavior of the traveling salesman problem. Associated results on the length of non-random Euclidean semi-matchings and large deviation inequalities for random semi-matchings are also given.Research supported in part by NSF Grant #DMS-8812868, ARO contract DAAL03-89-G-0092.P001, AFOSR-89-08301.A and NSA-MDA-904-89-2034.     

Hydrodynamic Limit and Viscosity Solutions for a Two-Dimensional Growth Process in the Anisotropic KPZ Class

We study a two-dimensional stochastic interface growth model that is believed to belong to the so-called anisotropic KPZ (AKPZ) universality class [4,5]. It can be seen either as a two-dimensional interacting particle process with drift that generalizes the one-dimensional Hammersley process [1,24], or as an irreversible dynamics of lozenge tilings of the plane [5,29]. Our main result is a hydrodynamic limit: the interface height profile converges, after a hyperbolic scaling of space and time, to the solution of a nonlinear first-order PDE of Hamilton-Jacobi type with nonconvex Hamiltonian (nonconvexity of the Hamiltonian is a distinguishing feature of the AKPZ class). We prove the result in two situations: (1) for smooth initial profiles and times smaller than the time T_shock when singularities (shocks) appear or (2) for all times, including t > T_shock, if the initial profile is convex. In the latter case, the height profile converges to the viscosity solution of the PDE. As an important ingredient, we introduce a Harris-type graphical construction for the process. © 2018 Wiley Periodicals, Inc.     

An extension of the factorization theorem to the non-positive case

This paper presents a method of determining joint distributions by known conditional distributions. A generalization of the Factorization Theorem is proposed. The generalized theorem is proved under the assumption that the support of unknown joint distribution may be divided into a countable number of sets, which all satisfy the relative weak positivity condition. This condition is defined in the paper and it generalizes the positivity condition introduced by Hammersley and Clifford. The theorem is illustrated with three examples. In the first example we determine a joint density in the case when the support of an unknown density is a continuous nonproduct set from Euclidean space . In the second example we seek the joint probability for the number of trials and the number of successes in Bernoulli's scheme. We also examine a simple example given by Kaiser and Cressie (J. Multivariate Anal. 73 (2000) 199).     

Local asymptotic laws for the Brownian convex hull

Summary We prove a general theorem for the precise rate at which the convex hull of Brownian motion gets created. The latter result relates large deviation theory to P. Lévy's geometric proof of Strassen's law of the iterated logarithm. This also answers a question of S. Evans. Moreover, we give a partial solution to a question of J. Hammersley and P. Lévy regarding the slowness of the growth of the hull process. Several examples, some classical and some new, are given to illustrate the theorems. Finally, we present applications to the convex hull of random walks ind dimensions.