Displaying similar documents to “On the volume of intersection of three independent Wiener sausages”

Factoring and testing primes in small space

Viliam Geffert, Dana Pardubská (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We discuss how much space is sufficient to decide whether a unary given number is a prime. We show that (log log ) space is sufficient for a deterministic Turing machine, if it is equipped with an additional pebble movable along the input tape, and also for an alternating machine, if the space restriction applies only to its accepting computation subtrees. In other words, the language is a prime is in pebble–DSPACE(log log ) and also in accept–ASPACE(log log ). Moreover, if the given...

An isoperimetric inequality on the ℓp balls

Sasha Sodin (2008)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

The normalised volume measure on the unit ball (1≤≤2) satisfies the following isoperimetric inequality: the boundary measure of a set of measure is at least log(1/), where =min(, 1−).

Large deviations for voter model occupation times in two dimensions

G. Maillard, T. Mountford (2009)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We study the decay rate of large deviation probabilities of occupation times, up to time , for the voter model : ℤ×[0, ∞)→{0, 1} with simple random walk transition kernel, starting from a Bernoulli product distribution with density ∈(0, 1). In [ (1988) 401–413], Bramson, Cox and Griffeath showed that the decay rate order lies in [log(), log()]. In this paper, we establish the true decay rates depending on the level. We show that the decay rates are log() when the deviation...

Almost-sure growth rate of generalized random Fibonacci sequences

Élise Janvresse, Benoît Rittaud, Thierry de la Rue (2010)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

We study the generalized random Fibonacci sequences defined by their first non-negative terms and for ≥1, +2= +1± (linear case) and +2=| +1± | (non-linear case), where each ± sign is independent and either + with probability or − with probability 1− (0<≤1). Our main result is that, when is of the form =2cos(/) for some integer ≥3, the exponential growth of ...

Pointwise ergodic theorems with rate and application to the CLT for Markov chains

Christophe Cuny, Michael Lin (2009)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Let be Dunford–Schwartz operator on a probability space (, ). For ∈ (), >1, we obtain growth conditions on ‖∑ ‖ which imply that (1/ )∑ →0 -a.e. In the particular case that =2 and is the isometry induced by a probability preserving transformation we get better results than in the general case; these are used to obtain a quenched...

A Space Lower Bound for Acceptance by One-Way Π-Alternating Machines

Viliam Geffert, Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that one-way Π-alternating Turing machines cannot accept unary nonregular languages in (log ) space. This holds for an mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ-alternating machines, that are able to accept unary nonregular languages in space (log log ). Thus, Σ-alternation is more powerful than Π-alternation for space bounded one-way machines with...