Invariance principle for biased bootstrap random walks

Our main goal is to study a class of processes whose increments are generated via a cellular automata rule. Given the increments of a simple biased random walk, a new sequence of (dependent) Bernoulli random variables is produced. It is built, from the original sequence, according to a cellular automata rule. Equipped with these two sequences, we construct two more according to the same cellular automata rule. The construction is repeated a fixed number of times yielding an infinite array ($\{?K,\dots ,K\}\times \mathbb{N}$) of (dependent) Bernoulli random variables. Taking partial sums of these sequences, we obtain a $(2K+1)$-dimensional process whose increments belong to the state space ${\{?1,1\}}^{2K+1}$.The aim of the paper is to study the long term behaviour of this process. In particular, we establish transience/recurrence properties and prove an invariance principle. The limiting behaviour of these processes depends strongly on the direction of the iteration, and exhibits few surprising features. This work is motivated by an earlier investigation (see Collevecchio et al. (2015)), in which the starting sequence is symmetric, and by the related work Ferrari et al. (2000).     

On the range of simple symmetric random walks on the line

This paper is aimed at a detailed study of the behaviors of random walks which is defined by the dyadic expansions of points. More precisely, let $x=({ϵ}_1\left(x\right),{ϵ}_2\left(x\right),\dots )$ be the dyadic expansion for a point $x\in [0,1)$ and $S_n\left(x\right)={\sum }_{k=1}^n(2{ϵ}_k\left(x\right)-1)$, which can be regarded as a simple symmetric random walk on $\mathbb{Z}.$ Denote by $R_n\left(x\right)$ the cardinality of the set $\{S_1\left(x\right),\dots ,S_n\left(x\right)\},$ which is just the distinct position of $x$ passed after $n$ times. The set of points whose behavior satisfies $R_n\left(x\right)\sim c{n}^{\gamma }$ is studied ($c>0$ and $0<\gamma \le 1$ being fixed) and its Hausdorff dimension is calculated.     

Stable-like fluctuations of Biggins’ martingales

Let ${\left(W_n\left(\theta \right)\right)}_{n\in {\mathbb{N}}_0}$ be Biggins’ martingale associated with a supercritical branching random walk, and let $W\left(\theta \right)$ be its almost sure limit. Under a natural condition for the offspring point process in the branching random walk, we show that if the law of $W_1\left(\theta \right)$ belongs to the domain of normal attraction of an $\alpha$-stable distribution for some $\alpha \in (1,2)$, then, as $n\to \infty$, there is weak convergence of the tail process ${(W\left(\theta \right)?W_{n?k}\left(\theta \right))}_{k\in {\mathbb{N}}_0}$, properly normalized, to a random scale multiple of a stationary autoregressive process of order one with $\alpha$-stable marginals.     

Small time convergence of subordinators with regularly or slowly varying canonical measure

We consider subordinators $X_{\alpha }={\left(X_{\alpha }\left(t\right)\right)}_{t\ge 0}$ in the domain of attraction at 0 of a stable subordinator ${\left(S_{\alpha }\left(t\right)\right)}_{t\ge 0}$ (where $\alpha \in (0,1)$); thus, with the property that ${\overline{\Pi }}_{\alpha }$, the tail function of the canonical measure of $X_{\alpha }$, is regularly varying of index $?\alpha \in (?1,0)$ as $x\downarrow 0$. We also analyse the boundary case, $\alpha =0$, when ${\overline{\Pi }}_{\alpha }$ is slowly varying at 0. When $\alpha \in (0,1)$, we show that ${\left(t{\overline{\Pi }}_{\alpha }\left(X_{\alpha }\left(t\right)\right)\right)}^{?1}$ converges in distribution, as $t\downarrow 0$, to the random variable ${\left(S_{\alpha }\left(1\right)\right)}^{\alpha }$. This latter random variable, as a function of $\alpha$, converges in distribution as $\alpha \downarrow 0$ to the inverse of an exponential random variable. We prove these convergences, also generalised to functional versions (convergence in $\mathbb{D}[0,1]$), and to trimmed versions, whereby a fixed number of its largest jumps up to a specified time are subtracted from the process. The $\alpha =0$ case produces convergence to an extremal process constructed from ordered jumps of a Cauchy subordinator. Our results generalise random walk and stable process results of Darling, Cressie, Kasahara, Kotani and Watanabe.     

Cutting sets of continuous functions on the unit interval

For a function $f:[0,1]\to \mathbb{R}$, we consider the set $E\left(f\right)$ of points at which $f$ cuts the real axis. Given $f:[0,1]\to \mathbb{R}$ and a Cantor set $D?[0,1]$ with $\{0,1\}?D$, we obtain conditions equivalent to the conjunction $f\in C[0,1]$ (or $f\in C^{\infty }[0,1]$) and $D?E\left(f\right)$. This generalizes some ideas of Zabeti. We observe that, if $f$ is continuous, then $E\left(f\right)$ is a closed nowhere dense subset of $f^{?1}\left[\left\{0\right\}\right]$. Additionally, if $Int{f}^{?1}\left[\left\{0\right\}\right]=0?$, each $x\in \{0,1\}\cap E\left(f\right)$ is an accumulation point of $E\left(f\right)$. Our main result states that, for a closed nowhere dense set $F?[0,1]$ with each $x\in \{0,1\}\cap F$ being an accumulation point of $F$, there exists $f\in C^{\infty }[0,1]$ such that $F=E\left(f\right)=f^{?1}\left[\left\{0\right\}\right]$.     

Graph switching, 2-ranks,and graphical Hadamard matrices

We study the behavior of the 2-rank of the adjacency matrix of a graph under Seidel and Godsil–McKay switching, and apply the result to graphs coming from graphical Hadamard matrices of order $4^m$. Starting with graphs from known Hadamard matrices of order 64, we find (by computer) many Godsil–McKay switching sets that increase the 2-rank. Thus we find strongly regular graphs with parameters $(63,32,16,16)$, $(64,36,20,20)$, and $(64,28,12,12)$ for almost all feasible 2-ranks. In addition we work out the behavior of the 2-rank for a graph product related to the Kronecker product for Hadamard matrices, which enables us to find many graphical Hadamard matrices of order $4^m$ for which the number of related strongly regular graphs with different 2-ranks is unbounded as a function of $m$. The paper extends results from the article ‘Switched symplectic graphs and their 2-ranks’ by the first and the last author.     

On the centre of mass of a random walk

For a random walk $S_n$ on ${\mathbb{R}}^d$ we study the asymptotic behaviour of the associated centre of mass process $G_n=n^{?1}{\sum }_{i=1}^n{S}_i$. For lattice distributions we give conditions for a local limit theorem to hold. We prove that if the increments of the walk have zero mean and finite second moment, $G_n$ is recurrent if $d=1$ and transient if $d\ge 2$. In the transient case we show that $G_n$ has a diffusive rate of escape. These results extend work of Grill, who considered simple symmetric random walk. We also give a class of random walks with symmetric heavy-tailed increments for which $G_n$ is transient in $d=1$.     

Complex surfaces of general type with K2 = 3,4 and pg = q = 0

We construct complex surfaces of general type with $p_g=0$ and $K^2=3,4$ as double covers of Enriques surfaces (called Keum–Naie surfaces) with a different way to the original constructions of Keum and Naie. As a result, we show that there is a $(?4)$-curve on the example with $K^2=3$, which might imply a special relation between Keum–Naie surfaces with $K^2=3$ and $K^2=4$.     

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.