An official website of the United States government
Abstract We provide an algorithm to approximate a finitely supported discrete measureμby a measureνNcorresponding to a set ofNpoints so that the total variation betweenμandνNhas an upper bound. As a consequence ifμis a (finite or infinitely supported) discrete probability measure on [0, 1]dwith a sufficient decay rate on the weights of each point, thenμcan be approximated byνNwith total variation, and hence star-discrepancy, bounded above by (logN)N−1. Our result improves, in the discrete case, recent work by Aistleitner, Bilyk, and Nikolov who show that for any normalized Borel measureμ, there exist finite sets whose star-discrepancy with respect toμis at most {\left( {\log \,N} \right)^{d - {1 \over 2}}}{N^{ - 1}}. Moreover, we close a gap in the literature for discrepancy in the cased=1 showing both that Lebesgue is indeed the hardest measure to approximate by finite sets and also that all measures without discrete components have the same order of discrepancy as the Lebesgue measure.
more »
« less
The Square Root Rule for Adaptive Importance Sampling
In adaptive importance sampling and other contexts, we haveK> 1 unbiased and uncorrelated estimates μ^kof a common quantity μ. The optimal unbiased linear combination weights them inversely to their variances, but those weights are unknown and hard to estimate. A simple deterministic square root rule based on a working model that Var(μ^k) ∝k−1/2gives an unbiased estimate of μ that is nearly optimal under a wide range of alternative variance patterns. We show that if Var(μ^k)∝k−yfor an unknown rate parametery∈[0,1], then the square root rule yields the optimal variance rate with a constant that is too large by at most 9/8 for any 0 ⩽y⩽ 1 and any numberKof estimates. Numerical work shows that rule is similarly robust to some other patterns with mildly decreasing variance askincreases.
more »
« less
- Award ID(s):
- 1837931
- PAR ID:
- 10509467
- Publisher / Repository:
- Association for Computing Machinery
- Date Published:
- Journal Name:
- ACM Transactions on Modeling and Computer Simulation
- Volume:
- 30
- Issue:
- 2
- ISSN:
- 1049-3301
- Page Range / eLocation ID:
- 1 to 12
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Utilizing 956 nights of Na lidar nocturnal mesopause region temperature profiles acquired at Fort Collins, CO (40.6°N, 105.1°W) over a 20‐year period (March 1990–2010), we deduce background nightly mean temperatureand the square of the buoyancy frequencyN2(z) at 2‐km resolution between 83 and 105 km. The temperature climatology reveals the two‐level mesopause structure with clarity and sharp mesopause transitions, resulting in 102 days of summer from Days 121 to 222 of the year. The same data set analyzed at 10‐min and 1‐km resolution gives the gravity wave (GW) temperature perturbationsTi'(z) and the wave varianceVar(T′(z)) and GW potential energyEpm(z) between 85 and 100 km. Seasonal averages of GWVar(T′(z)) andEpm(z) between 90 and 100 km, show thatVar(T′) for spring and autumn are comparable and lower than for summer and winter. Due mainly to the higher background stability, or largerN2(z) in summer,Epm(z) between 85 and 100 km is comparable in spring, summer, and autumn seasons, but ∼30%–45% smaller than the winter values at the same altitude. The uncertainties are about 4% for winter and about 5% for the other three seasons. The values forEpmare (156.0, 176.2, 145.6, and 186.2 J/kg) at 85 km for (spring, summer, autumn, and winter) respectively, (125.4, 120.2, 115.2, and 168.7 J/kg) at 93 km, and (207.5, 180.5, 213.1, and 278.6 J/kg) at 100 km. Going up in altitude, all profiles first decrease and then increase, suggesting that climatologically, GWs break below 85 km.more » « less
-
π-stacking in ground-state dimers/trimers/tetramers ofN-butoxyphenyl(naphthalene)diimide (BNDI) exceeds 50 kcal ⋅ mol−1in strength, drastically surpassing that for the*3[pyrene]2excimer (∼30 kcal ⋅ mol−1; formal bond order = 1) and similar to other weak-to-moderate classical covalent bonds. Cooperative π-stacking in triclinic (BNDI-T) and monoclinic (BNDI-M) polymorphs effects unusually large linear thermal expansion coefficients (αa, αb, αc, β) of (452, −16.8, −154, 273) × 10−6⋅ K−1and (70.1, −44.7, 163, 177) × 10−6⋅ K−1, respectively. BNDI-T exhibits highly reversible thermochromism over a 300-K range, manifest by color changes from orange (ambient temperature) toward red (cryogenic temperatures) or yellow (375 K), with repeated thermal cycling sustained for over at least 2 y.more » « less
-
We study the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in two-player zero-sum matrix games. Fearnley and Savani [18] showed that for any randomized algorithm, there exists ann×ninput matrix where it needs to queryΩ(n2) entries in expectation to compute asingleNash equilibrium. On the other hand, Bienstock et al. [5] showed that there is a special class of matrices for which one can queryO(n) entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in terms of the number of rowsnof the input matrix\(A \in \mathbb {R}^{n \times n} \), row support size\(k_1 := |\bigcup \limits _{x \in \mathcal {X}_\ast } \text{supp}(x)| \), and column support size\(k_2 := |\bigcup \limits _{y \in \mathcal {Y}_\ast } \text{supp}(y)| \). We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)by querying at mostO(nk5· polylog(n)) entries of the input matrix\(A \in \mathbb {R}^{n \times n} \)in expectation, wherek≔ max{k1,k2}. This upper bound is tight up to a factor of poly(k), as we show that for any randomized algorithm, there exists ann×ninput matrix with min {k1,k2} = 1, for which it needs to queryΩ(nk) entries in expectation in order to find the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \).more » « less
-
Abstract We present two decades of new high-angular-resolution near-infrared data from the W. M. Keck Observatory that reveal extreme evolution in X7, an elongated dust and gas feature, presently located half an arcsecond from the Galactic Center supermassive black hole. With both spectro-imaging observations of Br-γline emission andLp(3.8μm) imaging data, we provide the first estimate of its orbital parameters and quantitative characterization of the evolution of its morphology and mass. We find that the leading edge of X7 appears to be on a mildly eccentric (e∼ 0.3), relatively short-period (170 yr) orbit and is headed toward periapse passage, estimated to occur in ∼2036. Furthermore, our kinematic measurements rule out the earlier suggestion that X7 is associated with the stellar source S0-73 or with any other point source that has overlapped with X7 during our monitoring period. Over the course of our observations, X7 has (1) become more elongated, with a current length-to-width ratio of 9, (2) maintained a very consistent long-axis orientation (position angle of 50°), (3) inverted its radial velocity differential from tip to tail from −50 to +80 km s−1, and (4) sustained its total brightness (12.8Lpmagnitudes at the leading edge) and color temperature (425 K), which suggest a constant mass of ∼50MEarth. We present a simple model showing that these results are compatible with the expected effect of tidal forces exerted on it by the central black hole, and we propose that X7 is the gas and dust recently ejected from a grazing collision in a binary system.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3350426
