Intersections of random walks with random sets

Two general theorems about the intersections of a random walk with a random set are proved. The result is applied to the cases when the random set is a (deterministic) half-line and a two-sided random walk. Research supported by NSF Grant DMS-8702879 and an Alfred P. Sloan Research Fellowship.     

Distributions of random sets and random selections

Distributions of selections of a random set are characterized in terms of inequalities, similar to the marriage problem. A consequence is that the ensemble of such distributions is convex compact and depends continuously on the distribution of the random set.     

Perfect sets of random reals

We show that the existence of a perfect set of random reals over a modelM ofZFC does not imply the existence of a dominating real overM, thus answering a well-known open question (see [BJ 1] and [JS 2]). We also prove that (the product of two copies of the random algebra) neither adds a dominating real nor adds a perfect set of random reals (this answers a question that A. Miller asked during the logic year at MSRI). The first author would like to thank the MINERVA-foundation for supporting him. The second author would like to thank the Basic Research Foundation (the Israel Academy of Sciences and Humanities) for supporting him.     

Intersections of Markov random sets

Probability Theory and Related Fields -     

Projections of random Cantor sets

Recently Dekking and Grimmett have used the theories of branching processes in a random environment and of superbranching processes to find the almostsure box-counting dimension of certain orthogonal projections of random Cantor sets. This note gives a rather shorter and more direct calculation, and also shows that the Hausdorff dimension is almost surely equal to the box-counting dimension. We restrict attention to one-dimensional projections of a plane set—there is no difficulty in extending the proof to higher-dimensional cases.     

Dimensions of random recursive sets

We prove a theorem that generalizes the equality among the packing, Hausdorff, and upper and lower Minkowski dimensions for a general class of random recursive constructions, and apply it to constructions with finite memory. Then we prove an upper bound on the packing dimension of certain random distribution functions on [0, 1]. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 328, 2005, pp. 20–26.     

Using random sets as oracles

Let R be a notion of algorithmic randomness for individual subsetsof . A set B is a base for R randomness if there is a Z _T Bsuch that Z is R random relative to B. We show that the basesfor 1-randomness are exactly the K-trivial sets, and discussseveral consequences of this result. On the other hand, thebases for computable randomness include every ₂⁰ set that isnot diagonally noncomputable, but no set of PA-degree. As aconsequence, an n-c.e. set is a base for computable randomnessif and only if it is Turing incomplete.     

Combinatorial dimension and random sets

Having defined the combinatorial dimension of an arbitrary subset of a finite dimensional lattice, for every αε(1,2) we produce a set in N² whose dimension equals α. Research partially supported by NSF Grant #MCS8002716. Research supported by a University of Connecticut Research Grant (Sept. 1980).     

On conditional expectation of random sets

Summary Let be a random set with values in closed convex non empty subsets of the dual of a separable Fréchet space. Then its conditional expectation with respect to a sub-tribe is proved to exist and is related to regulat conditional probability.     

Effective conductivity of random homogeneous sets

Translated from Matematicheskii Zametki, Vol. 45, No. 4, pp. 34–45, April, 1989.     

Uncorrelatedness sets of bounded random variables

An uncorrelatedness set of two random variables shows which powers of random variables are uncorrelated. These sets provide a measure of independence: the wider an uncorrelatedness set is, the more independent random variables are. Conditions for a subset of to be an uncorrelatedness set of bounded random variables are studied. Applications to the theory of copulas are given.     

Random sets as imprecise random variables

Given a random set coming from the imprecise observation of a random variable, we study how to model the information about the probability distribution of this random variable. Specifically, we investigate whether the information given by the upper and lower probabilities induced by the random set is equivalent to the one given by the class of the probabilities induced by the measurable selections; together with sufficient conditions for this, we also give examples showing that they are not equivalent in all cases.     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015