-
作者：Alimohammadi, Yeganeh; Diaconis, Persi; Roghani, Mohammad; Saberi, Amin
作者单位：Stanford University; Stanford University
摘要：This paper makes three contributions to estimating the number of per-fect matching in bipartite graphs. First, we prove that the popular sequential importance sampling algorithm works in polynomial time for dense bipartite graphs. More carefully, our algorithm gives a (1 +/- e)-approximation for the number of perfect matchings of a A.-dense bipartite graph, using O (n 1-2A. A. E-2 ) samples. With size n on each side and for 21 > A. > 0, a A.-dense bipartite graph has all degrees greater than (...
-
作者：Christensen, Soren; Strauch, Claudia
作者单位：University of Kiel; Aarhus University
摘要：One of the fundamental assumptions in stochastic control of continuous time processes is that the dynamics of the underlying (diffusion) process is known. This is, however, usually obviously not fulfilled in practice. On the other hand, over the last decades, a rich theory for nonparametric estimation of the drift (and volatility) for continuous time processes has been developed. The aim of this paper is bringing together techniques from stochastic control with methods from statistics for stoc...
-
作者：Claisse, Julien; Ren, Zhenjie; Tan, Xiaolu
作者单位：Universite PSL; Universite Paris-Dauphine; Chinese University of Hong Kong
摘要：Mean field games are concerned with the limit of large-population stochastic differential games where the agents interact through their empir-ical distribution. In the classical setting, the number of players is large but fixed throughout the game. However, in various applications, such as popu-lation dynamics or economic growth, the number of players can vary across time and this may lead to different Nash equilibria. In order to account for this evolution, we introduce a branching mechanism ...
-
作者：Benaych-Georges, Florent; Bouchaud, Jean-Philippe; Potters, Marc
摘要：We give a new algorithm for the estimation of the cross-covariance ma-trix EXY' of two large-dimensional signals X e Rn, Y e Rp in the context where the number T of observations of the pair (X, Y) is large but n/T and p/ T are not supposed to be small. In the asymptotic regime where n, p, T are large, with high probability, this algorithm is optimal for the Frobenius norm among rotationally invariant estimators, that is, estimators derived from the empirical estimator by cleaning the singular ...
-
作者：Hernandez, Camilo; Possamai, Dylan
作者单位：Imperial College London; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We develop a theory for continuous-time non-Markovian stochastic con-trol problems which are inherently time-inconsistent. Their distinguishing feature is that the classical Bellman optimality principle no longer holds. Our formulation is cast within the framework of a controlled non-Markovian for-ward stochastic differential equation, and a general objective functional set-ting. We adopt a game-theoretic approach to study such problems, meaning that we seek for subgame perfect Nash equilibriu...
-
作者：Breden, Maxime; Engel, Maximilian
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Free University of Berlin
摘要：We confirm a long-standing conjecture concerning shear-induced chaos in stochastically perturbed systems exhibiting a Hopf bifurcation. The method of showing the main chaotic property, a positive Lyapunov exponent, is a computer-assisted proof. Using the recently developed theory of conditioned Lyapunov exponents on bounded domains and the modified Furstenberg- Khasminskii formula, the problem boils down to the rigorous computation of eigenfunctions of the Kolmogorov operators describing distr...
-
作者：Grama, Ion; Liu, Quansheng; Pin, Erwan
作者单位：Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI)
摘要：Consider a multitype branching process in a random environment, whose reproduction law of generation n depends on the random environment at time n, unlike a constant distribution assumed in the Galton-Watson process. The famous Kesten-Stigum theorem for a supercritical multitype Galton-Watson process gives a precise description of the exponential increasing rate of the population size via a criterion for the nondegeneracy of the fundamental mar-tingale. Finding the corresponding result in the ...
-
作者：Lacker, Daniel; Ramanan, Kavita; Wu, Ruoyu
作者单位：Columbia University; Brown University; Iowa State University
摘要：We study the limiting behavior of interacting particle systems indexed by large sparse graphs, which evolve either according to a discrete time Markov chain or a diffusion, in which particles interact directly only with their nearest neighbors in the graph. To encode sparsity we work in the framework of local weak convergence of marked (random) graphs. We show that the joint law of the particle system varies continuously with respect to local weak conver-gence of the underlying graph marked wi...
-
作者：Hermon, Jonathan; Salez, Justin
作者单位：University of British Columbia; Universite PSL; Universite Paris-Dauphine; Universite PSL
摘要：We establish universal modified log-Sobolev inequalities for reversible Markov chains on the boolean lattice {0, 1}n, when the invariant law pi sat-isfies a form of negative dependence known as the stochastic covering prop-erty. This condition is strictly weaker than the strong Rayleigh property, and is satisfied in particular by all determinantal measures, as well as the uniform distribution over the set of bases of any balanced matroid. In the special case where pi is k-homogeneous, our resu...
-
作者：Del Moral, Pierre; Horton, Emma
摘要：Despite the widespread usage of discrete generation ensemble Kalman particle filtering methodology to solve nonlinear and high-dimensional fil-tering and inverse problems, little is known about their mathematical foun-dations. As genetic-type particle filters (a.k.a. sequential Monte Carlo), this ensemble-type methodology can also be interpreted as mean-field particle ap-proximations of the Kalman-Bucy filtering equation. In contrast with conven-tional mean-field type interacting particle meth...
