It is celebrated that a simple random walk on ℤ and ℤ² returns to the initial vertex v infinitely many times during infinitely many transitions, which is said recurrent, while it returns to v only finite times on ℤ^d for d ≥ 3, which is said transient. It is also known that a simple random walk on a growing region on ℤ^d can be recurrent depending on growing speed for any fixed d. This paper shows that a simple random walk on {0,1,…,N}ⁿ with an increasing n and a fixed N can be recurrent depending on the increasing speed of n. Precisely, we are concerned with a specific model of a random walk on a growing graph (RWoGG) and show a phase transition between the recurrence and transience of the random walk regarding the growth speed of the graph. For the proof, we develop a pausing coupling argument introducing the notion of weakly less homesick as graph growing (weakly LHaGG).

Disordered complex networks are of fundamental interest in statistical physics, and they have attracted recent interest as stochastic models for information transmission over wireless networks. While mathematically tractable, a network based on the regulation Poisson point process model offers challenges vis-a-vis network efficiency. Strongly correlated alternatives, such as networks based on random matrix spectra (the Ginibre network), on the other hand offer formidable challenges in terms of tractability and robustness issues. In this work, we demonstrate that network models based on random perturbations of Euclidean latticesinterpolatebetween Poisson and rigidly structured networks, and allow us to achieve thebest of both worlds: significantly improve upon the Poisson model in terms of network efficacy measured by theSignal to Interference plus Noise Ratio(abbrv. SINR) and the related concept ofcoverage probabilities, at the same time retaining a considerable measure of mathematical and computational simplicity and robustness to erasure and noise. We investigate the optimal choice of the base lattice in this model, connecting it to the celebrated problem optimality of Euclidean lattices with respect to the Epstein Zeta function, which is in turn related to notions of lattice energy. This leads us to the choice of the triangular lattice in 2D and face centered cubic lattice in 3D, whose Gaussian perturbations we consider. We provide theoretical analysis and empirical investigations to demonstrate that the coverage probability decreases with increasing strength of perturbation, eventually converging to that of the Poisson network. In the regime of low disorder, our studies suggest an approximate statistical behaviour of the coverage function near a base station as a log-normal distribution with parameters depending on the Epstein Zeta function of the lattice, and related approximate dependencies for a power-law constant that governs the network coverage probability at large thresholds. In 2D, we determine the disorder strength at which the perturbed triangular lattice (abbrv. PTL) and the Ginibre networks are theclosestmeasured by comparing their network topologies via a comparison of theirPersistence Diagramsin the total variation as well as the symmetrized nearest neighbour distances. We demonstrate that, at this very same disorder, the PTL and the Ginibre networks exhibit very similar coverage probability distributions, with the PTL performing at least as well as the Ginibre. Thus, the PTL network at this disorder strength can be taken to be an effective substitute for the Ginibre network model, while at the same time offering the advantages of greater tractability both from theoretical and empirical perspectives.

The determinantal point process (DPP) has been receiving increasing attention in machine learning as a generative model of subsets consisting of relevant and diverse items. Recently, there has been a significant progress in developing efficient algorithms for learning the kernel matrix that characterizes a DPP. Here, we propose a dynamic DPP, which is a DPP whose kernel can change over time, and develop efficient learning algorithms for the dynamic DPP. In the dynamic DPP, the kernel depends on the subsets selected in the past, but we assume a particular structure in the dependency to allow efficient learning. We also assume that the kernel has a low rank and exploit a recently proposed learning algorithm for the DPP with low-rank factorization, but also show that its bottleneck computation can be reduced from O(M2 K) time to O(M K2) time, where M is the number of items under consideration, and K is the rank of the kernel, which can be set smaller than M by orders of magnitude.

We consider the spatial stochastic model of single-tier downlink cellular networks, where the wireless base stations are deployed according to a general stationary point process on the Euclidean plane with general i.i.d. propagation effects. Recently, Ganti & Haenggi (2016) consider the same general cellular network model and, as one of many significant results, derive the tail asymptotics of the signal-to-interference ratio (SIR) distribution. However, they do not mention any conditions under which the result holds. In this paper, we compensate their result for the lack of the condition and expose a sufficient condition for the asymptotic result to be valid. We further illustrate some examples satisfying such a sufficient condition and indicate the corresponding asymptotic results for the example models. We give also a simple counterexample violating the sufficient condition.

Recently, spatial stochastic models based on determinantal point processes (DPP) are studied as promising models for analysis of cellular wireless networks. Indeed, the DPPs can express the repulsive nature of the macro base station (BS) configuration observed in a real cellular network and have many desirable mathematical properties to analyze the network performance. However, almost all the prior works on the DPP based models assume the Rayleigh fading while the spatial models based on Poisson point processes have been developed to allow arbitrary distributions of fading/shadowing propagation effects. In order for the DPP based model to be more promising, it is essential to extend it to allow non-Rayleigh propagation effects. In the present paper, we propose the downlink cellular network model where the BSs are deployed according to the Ginibre point process, which is one of the main examples of the DPPs, over Nakagami-m fading. For the proposed model, we derive a numerically computable form of the coverage probability and reveal some properties of it numerically and theoretically.

Policy gradient reinforcement learning (PGRL) has been receiving substantial attention as a mean for seeking stochastic policies that maximize cumulative reward. However, the learning speed of PGRL is known to decrease substantially when PGRL explores the policies that give the Markov chains having long mixing time. We study a new approach of regularizing how the PGRL explores the policies by the use of the hitting time of the Markov chains. The hitting time gives an upper bound on the mixing time, and the proposed approach improves the learning efficiency by keeping the mixing time of the Markov chains short. In particular, we propose a method of temporal-difference learning for estimating the gradient of the hitting time. Numerical experiments show that the proposed method outperforms conventional methods of PGRL.

Coverage probability is one of the most important metrics for evaluating the performance of wireless networks. However, the spatial stochastic models for which a computable expression of the coverage probability is available are restricted (such as the Poisson based or α-Ginibre based models). Furthermore, even if it is available, the practical numerical computation may be time-consuming (in the case of α-Ginibre based model). In this paper, we propose the application of Padé approximation to the coverage probability in the wireless network models based on general spatial stationary point processes. The required Maclaurin coefficients are expressed in terms of the moment measures of the point process, so that the approximants are expected to be available for a broader class of point processes. Through some numerical experiments for the cellular network model, we demonstrate that the Padé approximation is effectively applicable for evaluating the coverage probability.