In causal inference on directed acyclic graphs, the orientation of edges is in general only recovered up to Markov equivalence classes. We study Markov equivalence classes of uniformly random directed acyclic graphs. Using a tower decomposition, we show that the ratio between the number of Markov equivalence classes and directed acyclic graphs approaches a positive constant when the number of sites goes to infinity. For a typical directed acyclic graph, the expected number of elements in its Markov equivalence class remains bounded. More precisely, we prove that for a uniformly chosen directed acyclic graph, the size of its Markov equivalence class has super-polynomial tails.
相關內容
We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing $t$-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients $\left(\frac{\pi}{4}-\frac{1}{8}\arccos(\frac{1}{5}),\frac{\pi}{8},\frac{1}{8}\arccos(\frac{1}{5})\right)$ (which we call $\chi$ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.
The Johnson--Lindenstrauss (JL) lemma is a powerful tool for dimensionality reduction in modern algorithm design. The lemma states that any set of high-dimensional points in a Euclidean space can be flattened to lower dimensions while approximately preserving pairwise Euclidean distances. Random matrices satisfying this lemma are called JL transforms (JLTs). Inspired by existing $s$-hashing JLTs with exactly $s$ nonzero elements on each column, the present work introduces an ensemble of sparse matrices encompassing so-called $s$-hashing-like matrices whose expected number of nonzero elements on each column is~$s$. The independence of the sub-Gaussian entries of these matrices and the knowledge of their exact distribution play an important role in their analyses. Using properties of independent sub-Gaussian random variables, these matrices are demonstrated to be JLTs, and their smallest and largest singular values are estimated non-asymptotically using a technique from geometric functional analysis. As the dimensions of the matrix grow to infinity, these singular values are proved to converge almost surely to fixed quantities (by using the universal Bai--Yin law), and in distribution to the Gaussian orthogonal ensemble (GOE) Tracy--Widom law after proper rescalings. Understanding the behaviors of extreme singular values is important in general because they are often used to define a measure of stability of matrix algorithms. For example, JLTs were recently used in derivative-free optimization algorithmic frameworks to select random subspaces in which are constructed random models or poll directions to achieve scalability, whence estimating their smallest singular value in particular helps determine the dimension of these subspaces.
In this work is considered an elliptic problem, referred to as the Ventcel problem, involvinga second order term on the domain boundary (the Laplace-Beltrami operator). A variationalformulation of the Ventcel problem is studied, leading to a finite element discretization. Thefocus is on the construction of high order curved meshes for the discretization of the physicaldomain and on the definition of the lift operator, which is aimed to transform a functiondefined on the mesh domain into a function defined on the physical one. This lift is definedin a way as to satisfy adapted properties on the boundary, relatively to the trace operator.The Ventcel problem approximation is investigated both in terms of geometrical error and offinite element approximation error. Error estimates are obtained both in terms of the meshorder r $\ge$ 1 and to the finite element degree k $\ge$ 1, whereas such estimates usually have beenconsidered in the isoparametric case so far, involving a single parameter k = r. The numericalexperiments we led, both in dimension 2 and 3, allow us to validate the results obtained andproved on the a priori error estimates depending on the two parameters k and r. A numericalcomparison is made between the errors using the former lift definition and the lift defined inthis work establishing an improvement in the convergence rate of the error in the latter case.
We consider linear models with scalar responses and covariates from a separable Hilbert space. The aim is to detect change points in the error distribution, based on sequential residual empirical distribution functions. Expansions for those estimated functions are more challenging in models with infinite-dimensional covariates than in regression models with scalar or vector-valued covariates due to a slower rate of convergence of the parameter estimators. Yet the suggested change point test is asymptotically distribution-free and consistent for one-change point alternatives. In the latter case we also show consistency of a change point estimator.
This work deals with the numerical approximation of plasmas which are confined by the effect of a fast oscillating magnetic field (see \cite{Bostan2012}) in the Vlasov model. The presence of this magnetic field induces oscillations (in time) to the solution of the characteristic equations. Due to its multiscale character, a standard time discretization would lead to an inefficient solver. In this work, time integrators are derived and analyzed for a class of highly oscillatory differential systems. We prove the uniform accuracy property of these time integrators, meaning that the accuracy does not depend on the small parameter $\varepsilon$. Moreover, we construct an extension of the scheme which degenerates towards an energy preserving numerical scheme for the averaged model, when $\varepsilon\to 0$. Several numerical results illustrate the capabilities of the method.
Eigenvalue transformations, which include solving time-dependent differential equations as a special case, have a wide range of applications in scientific and engineering computation. While quantum algorithms for singular value transformations are well studied, eigenvalue transformations are distinct, especially for non-normal matrices. We propose an efficient quantum algorithm for performing a class of eigenvalue transformations that can be expressed as a certain type of matrix Laplace transformation. This allows us to significantly extend the recently developed linear combination of Hamiltonian simulation (LCHS) method [An, Liu, Lin, Phys. Rev. Lett. 131, 150603, 2023; An, Childs, Lin, arXiv:2312.03916] to represent a wider class of eigenvalue transformations, such as powers of the matrix inverse, $A^{-k}$, and the exponential of the matrix inverse, $e^{-A^{-1}}$. The latter can be interpreted as the solution of a mass-matrix differential equation of the form $A u'(t)=-u(t)$. We demonstrate that our eigenvalue transformation approach can solve this problem without explicitly inverting $A$, reducing the computational complexity.
There has been a surge of interest in uncertainty quantification for parametric partial differential equations (PDEs) with Gevrey regular inputs. The Gevrey class contains functions that are infinitely smooth with a growth condition on the higher-order partial derivatives, but which are nonetheless not analytic in general. Recent studies by Chernov and Le (Comput. Math. Appl., 2024, and SIAM J. Numer. Anal., 2024) as well as Harbrecht, Schmidlin, and Schwab (Math. Models Methods Appl. Sci., 2024) analyze the setting wherein the input random field is assumed to be uniformly bounded with respect to the uncertain parameters. In this paper, we relax this assumption and allow for parameter-dependent bounds. The parametric inputs are modeled as generalized Gaussian random variables, and we analyze the application of quasi-Monte Carlo (QMC) integration to assess the PDE response statistics using randomly shifted rank-1 lattice rules. In addition to the QMC error analysis, we also consider the dimension truncation and finite element errors in this setting.
We propose a novel, highly efficient, second-order accurate, long-time unconditionally stable numerical scheme for a class of finite-dimensional nonlinear models that are of importance in geophysical fluid dynamics. The scheme is highly efficient in the sense that only a (fixed) symmetric positive definite linear problem (with varying right hand sides) is involved at each time-step. The solutions to the scheme are uniformly bounded for all time. We show that the scheme is able to capture the long-time dynamics of the underlying geophysical model, with the global attractors as well as the invariant measures of the scheme converge to those of the original model as the step size approaches zero. In our numerical experiments, we take an indirect approach, using long-term statistics to approximate the invariant measures. Our results suggest that the convergence rate of the long-term statistics, as a function of terminal time, is approximately first order using the Jensen-Shannon metric and half-order using the L1 metric. This implies that very long time simulation is needed in order to capture a few significant digits of long time statistics (climate) correct. Nevertheless, the second order scheme's performance remains superior to that of the first order one, requiring significantly less time to reach a small neighborhood of statistical equilibrium for a given step size.
The paper studies asymptotic properties of estimators of multidimensional stochastic differential equations driven by Brownian motions from high-frequency discrete data. Consistency and central limit properties of a class of estimators of the diffusion parameter and an approximate maximum likelihood estimator of the drift parameter based on a discretized likelihood function have been established in a suitable scaling regime involving the time-gap between the observations and the overall time span. Our framework is more general than that typically considered in the literature and, thus, has the potential to be applicable to a wider range of stochastic models.
The gradient bounds of generalized barycentric coordinates play an essential role in the $H^1$ norm approximation error estimate of generalized barycentric interpolations. Similarly, the $H^k$ norm, $k>1$, estimate needs upper bounds of high-order derivatives, which are not available in the literature. In this paper, we derive such upper bounds for the Wachspress generalized barycentric coordinates on simple convex $d$-dimensional polytopes, $d\ge 1$. The result can be used to prove optimal convergence for Wachspress-based polytopal finite element approximation of, for example, fourth-order elliptic equations. Another contribution of this paper is to compare various shape-regularity conditions for simple convex polytopes, and to clarify their relations using knowledge from convex geometry.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191