# Probability (math.PR)

• We study the Wasserstein metric $W_p$, a notion of distance between two probability distributions, from the perspective of Fourier Analysis and discuss applications. In particular, we bound the Earth Mover Distance $W_1$ between the distribution of quadratic residues in a finite field $\mathbb{F}_p$ and uniform distribution by $\lesssim p^{-1/2}$ (the Polya-Vinogradov inequality implies $\lesssim p^{-1/2} \log{p}$). We also show for continuous $f:\mathbb{T} \rightarrow \mathbb{R}_{}$ with mean value 0 $$(\mboxnumber of roots of~f) ⋅\left( \sum_k=1^∞ \frac |\widehatf(k)|^2k^2\right)^\frac12 ≳\frac\|f\|^2_L^1(\mathbbT)\|f\|_L^∞(\mathbbT).$$ Moreover, we show that for a Laplacian eigenfunction $-\Delta_g \phi_{\lambda} = \lambda \phi_{\lambda}$ on a compact Riemannian manifold $W_p\left(\max\left\{\phi_{\lambda}, 0\right\}dx, \max\left\{-\phi_{\lambda}, 0\right\} dx\right) \lesssim_p \sqrt{\log{\lambda}/\lambda} \|\phi_{\lambda}\|_{L^1}^{1/p}$ which is at most a factor $\sqrt{\log{\lambda}}$ away from sharp. Several other problems are discussed.
• We prove improved bounds on how localized an eigenvector of a high girth regular graph can be, and present examples showing that these bounds are close to sharp. This study was initiated by Brooks and Lindenstrauss (2009) who relied on the observation that certain suitably normalized averaging operators on high girth graphs are hyper-contractive and can be used to approximate projectors onto the eigenspaces of such graphs. Informally, their delocalization result in the contrapositive states that for any $\varepsilon \in (0,1)$ and positive integer $k,$ if a $(d+1)-$regular graph has an eigenvector which supports $\varepsilon$ fraction of the $\ell_2^2$ mass on a subset of $k$ vertices, then the graph must have a cycle of size $\tilde{O}(\log_{d}(k)/\varepsilon^2)$, suppressing logarithmic terms in $1/\varepsilon$. In this paper, we improve the upper bound to $\tilde{O}(\log_{d}(k)/\varepsilon)$ and present a construction showing a lower bound of $\Omega(\log_d(k)/\varepsilon)$. Our construction is probabilistic and involves gluing together a pair of trees while maintaining high girth as well as control on the eigenvectors and could be of independent interest.
• We discuss the asymptotic behaviour of random critical Boltzmann planar maps in which the degree of a typical face belongs to the domain of attraction of a stable law with index $\alpha \in (1,2]$. We prove that when conditioning such maps to have $n$ vertices, or $n$ edges, or $n$ faces, the vertex-set endowed with the graph distance suitably rescaled converges in distribution towards the celebrated Brownian map when $\alpha=2$, and, after extraction of a subsequence, towards another `$\alpha$-stable map' when $\alpha <2$, which improves on a first result due to Le Gall & Miermont who assumed slightly more regularity.
• In this note we consider stochastic heat equation with general additive Gaussian noise. Our aim is to derive some necessary and sufficient conditions on the Gaussian noise in order to solve the corresponding heat equation. We investigate this problem invoking two different methods, respectively based on variance computations and on path-wise considerations in Besov spaces. We are going to see that, as anticipated, both approaches lead to the same necessary and sufficient condition on the noise. In addition, the path-wise approach brings out regularity results for the solution.
• This article focuses on parabolic equations with rough diffusion coefficients which are ill-posed in the classical sense of distributions due to the presense of a singular forcing. Inspired by the philosophy of rough paths and regularity structures, we introduce a notion of modelled distribution which is suitable in this context. We prove two general tools for reconstruction and integration, as well as a product lemma which is tailor made for the reconstruction of the rough diffusion operator. This yields a partially automated deterministic theory, which we apply to obtain an existence and uniqueness theory for parabolic equations with rough diffusion coefficients and a singular forcing in the negative parabolic Hölder space of order larger than $-\frac{3}{2}$.
• We introduce a family of sequence transformations, defined via partial Bell polynomials, that may be used for a systematic study of a wide variety of problems in enumerative combinatorics. This family includes some of the transformations listed in the paper by Bernstein & Sloane, now seen as transformations under the umbrella of partial Bell polynomials. Our goal is to describe these transformations from the algebraic and combinatorial points of view. We provide functional equations satisfied by the generating functions, derive inverse relations, and give a convolution formula. While the full range of applications remains unexplored, in this paper we show a glimpse of the versatility of Bell transformations by discussing the enumeration of several combinatorial configurations, including rational Dyck paths, rooted planar maps, and certain classes of permutations.
• We consider the model of a token-based joint auto-scaling and load balancing strategy, proposed in a recent paper by Mukherjee, Dhara, Borst, and van Leeuwaarden (SIGMETRICS '17, arXiv:1703.08373), which offers an efficient scalable implementation and yet achieves asymptotically optimal steady-state delay performance and energy consumption as the number of servers $N\to\infty$. In the above work, the asymptotic results are obtained under the assumption that the queues have fixed-size finite buffers, and therefore the fundamental question of stability of the proposed scheme with infinite buffers was left open. In this paper, we address this fundamental stability question. The system stability under the usual subcritical load assumption is not automatic. Moreover, the stability may not even hold for all $N$. The key challenge stems from the fact that the process lacks monotonicity, which has been the powerful primary tool for establishing stability in load balancing models. We develop a novel method to prove that the subcritically loaded system is stable for large enough $N$, and establish convergence of steady-state distributions to the optimal one, as $N \to \infty$. The method goes beyond the state of the art techniques -- it uses an induction-based idea and a "weak monotonicity" property of the model; this technique is of independent interest and may have broader applicability.
• The aim of the presented research is to give a rigorous mathematical approach to Feynman path integrals based on strong (pathwise) approximations based on simple random walks.
• We discuss sufficient conditions that guarantee the existence of asymptotic expansions for the Central Limit Theorem for weakly dependent random variables including observations arising from sufficiently chaotic dynamical systems like piece-wise expanding maps, and strongly ergodic Markov chains. We primarily use spectral techniques to obtain the results.
• A family of sets is called $r$-\emphcover free if it does not contain $2\leq\ell+1\leq r+1$ distinct sets $A_0,A_1,\ldots,A_{\ell}$ such that $A_0\subseteq A_1\cup\cdots\cup A_{\ell}$. In particular, a $1$-cover free family of sets is simply an antichain, with respect to set inclusion. Thus, by Sperner's classical result, the maximal cardinality of a $1$-cover free family of subsets of a set of $n$ elements is $\binom{n}{\lfloor n/2\rfloor}$. For $r>1$, the maximal cardinality of an $r$-cover free family of subsets of a set of $n$ elements was studied by Erdős, Frankl and F\"uredi. In this paper we are interested in the following probabilistic variant of this problem. For positive integers $r$ and $n$, how small can the probability that $S_0\subseteq S_1\cup\cdots\cup S_r$ be, where $S_0,S_1,\ldots,S_r$ are i.i.d random subsets of a set of $n$ elements? For $r=1$, we show that for every $n\geq 2$, this probability is minimal when the distributions of $S_0$ and of $S_1$ are uniform on a $1$-cover free family of maximal cardinality. In a complete contrast, we also show that this is not the case for every $r>1$ (and $n$ large enough). Interestingly, finding a probability distribution on subsets of the set $\{1,2,\ldots,n\}$, for which the probability that $S_0\subseteq S_1\cup S_2$ is small (where $S_0,S_1,S_2$ are drawn independently according to this distribution), is useful for analyzing the misuse resistance of one-time signatures.

Danial Dervovic Mar 01 2018 12:08 UTC

Hello again Māris, many thanks for your patience. Your comments and questions have given me much food for thought, and scope for an amended version of the paper -- please see my responses below.

Please if any of the authors of [AST17 [arXiv:1712.01609](https://arxiv.org/abs/1712.01609)] have any fu

...(continued)
Danial Dervovic Feb 05 2018 15:03 UTC

Thank you Māris for the extremely well thought-out and articulated points here.

I think this very clearly highlights the need to think explicitly about the precompute time if using the lifting to directly simulate the quantum walk, amongst other things.

I wish to give a well-considered respons

...(continued)
Māris Ozols Feb 01 2018 17:53 UTC

This paper considers the problem of using "lifted" Markov chains to simulate the mixing of coined quantum walks. The Markov chain has to approximately (in the total variational distance) sample from the distribution obtained by running the quantum walk for a randomly chosen time $t \in [0,T]$ follow

...(continued)
Danial Dervovic Dec 10 2017 15:25 UTC

Thank you for the insightful observations, Simon.

In response to the first point, there is a very short comment in the Discussion section to this effect. I felt an explicit dependence on $T$ as opposed to the diameter would make the implications of the result more clear. Namely, lifting can mix

...(continued)
Simon Apers Dec 09 2017 07:54 UTC

Thanks for the comment, Simone. A couple of observations:

- We noticed that Danial's result can in fact be proved more directly using the theorem that is used from ([arXiv:1705.08253][1]): by choosing the quantum walk Cesaro average as the goal distribution, it can be attained with a lifted Markov

...(continued)
Simone Severini Dec 07 2017 02:51 UTC

Closely related to

Simon Apers, Alain Sarlette, Francesco Ticozzi, Simulation of Quantum Walks and Fast Mixing with Classical Processes, https://scirate.com/arxiv/1712.01609

In my opinion, lifting is a good opportunity to put on a rigorous footing the relationship between classical and quantu

...(continued)
Mile Gu Nov 20 2015 05:04 UTC

Good question! There shouldn't be any contradiction with the correspondence principle. The reason here is that the quantum models are built to simulate the output behaviour of macroscopic, classical systems, and are not necessarily macroscopic themselves. When we compare quantum and classical comple

...(continued)
hong Nov 20 2015 00:40 UTC

Interesting results. But, just wondering, does it contradict to the correspondence principle?

Richard Kueng Jul 28 2015 07:01 UTC

fyi: our quantum implications are presented in Subsection 2.2 (pp 7-9).

Zoltán Zimborás May 28 2014 04:42 UTC

It's a bit funny to look at a formally verified proof of the CLT :), here it is online: