More Like this

1. Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem

   https://doi.org/10.4230/lipics.itcs.2025.77  

   Pettie, Seth; Wang, Dingyu (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   In the d-dimensional turnstile streaming model, a frequency vector 𝐱 = (𝐱(1),…,𝐱(n)) ∈ (ℝ^d)ⁿ is updated entry-wisely over a stream. We consider the problem of f-moment estimation for which one wants to estimate f(𝐱)=∑_{v ∈ [n]}f(𝐱(v)) with a small-space sketch. A function f is tractable if the f-moment can be estimated to within a constant factor using polylog(n) space. The f-moment estimation problem has been intensively studied in the d = 1 case. Flajolet and Martin estimate the F₀-moment (f(x) = 1 (x > 0), incremental stream); Alon, Matias, and Szegedy estimate the L₂-moment (f(x) = x²); Indyk estimates the L_α-moment (f(x) = |x|^α), α ∈ (0,2]. For d ≥ 2, Ganguly, Bansal, and Dube estimate the L_{p,q} hybrid moment (f:ℝ^d → ℝ,f(x) = (∑_{j = 1}^d |x_j|^p)^q), p ∈ (0,2],q ∈ (0,1). For tractability, Bar-Yossef, Jayram, Kumar, and Sivakumar show that f(x) = |x|^α is not tractable for α > 2. Braverman, Chestnut, Woodruff, and Yang characterize the class of tractable one-variable functions except for a class of nearly periodic functions. In this work we present a simple and generic scheme to construct sketches with the novel idea of hashing indices to Lévy processes, from which one can estimate the f-moment f(𝐱) where f is the characteristic exponent of the Lévy process. The fundamental Lévy-Khintchine representation theorem completely characterizes the space of all possible characteristic exponents, which in turn characterizes the set of f-moments that can be estimated by this generic scheme. The new scheme has strong explanatory power. It unifies the construction of many existing sketches (F₀, L₀, L₂, L_α, L_{p,q}, etc.) and it implies the tractability of many nearly periodic functions that were previously unclassified. Furthermore, the scheme can be conveniently generalized to multidimensional cases (d ≥ 2) by considering multidimensional Lévy processes and can be further generalized to estimate heterogeneous moments by projecting different indices with different Lévy processes. We conjecture that the set of tractable functions can be characterized using the Lévy-Khintchine representation theorem via what we called the Fourier-Hahn-Lévy method. 

   more » « less
2. Multi-dimensional Lévy Processes for Multiple Dependent Degradation Processes in Lifetime Analysis

   Shi, Y; Shu, Y; Feng, Q. (May 2018, Proceedings of Industrial and Systems Engineering Research Conference)

   The analysis of multiple dependent degradation processes is a challenging research work in the reliability field, especially for complex degradation with random jumps. To integrally handle the jump uncertainties in degradation and the dependence among degradation processes, we construct multi-dimensional Lévy processes to describe multiple dependent degradation processes in engineering systems. The evolution of each degradation process can be modeled by a one-dimensional Lévy subordinator with a marginal Lévy measure, and the dependence among all dimensions can be described by Lévy copulas and the associated multiple-dimensional Lévy measure. This Lévy measure is obtained from all its one-dimensional marginal Lévy measures and the Lévy copula. We develop the Fokker-Planck equations to describe the probability density in stochastic systems. The Laplace transforms of both reliability function and lifetime moments are derived. Numerical examples are used to demonstrate our models in lifetime analysis. 

   more » « less
3. Limit Theorems for Some Long Range Random Walks on Torsion Free Nilpotent Groups

   Chen, Zhen-Qing; Kumagai, Takashi; Saloff-Coste, Laurent; Wang, Jian; Zheng, Tianyi (July 2023, Springer)

   This book develops limit theorems for a natural class of long range random walks on finitely generated torsion free nilpotent groups. The limits in these limit theorems are Lévy processes on some simply connected nilpotent Lie groups. Both the limit Lévy process and the limit Lie group carrying this process are determined by and depend on the law of the original random walk. The book offers the first systematic study of such limit theorems involving stable-like random walks and stable limit Lévy processes in the context of (non-commutative) nilpotent groups. 

   more » « less
4. Erlang mixture modeling for Poisson process intensities

   https://doi.org/10.1007/s11222-021-10064-0  

   Kim, Hyotae; Kottas, Athanasios (November 2021, Statistics and Computing)

   Abstract We develop a prior probability model for temporal Poisson process intensities through structured mixtures of Erlang densities with common scale parameter, mixing on the integer shape parameters. The mixture weights are constructed through increments of a cumulative intensity function which is modeled nonparametrically with a gamma process prior. Such model specification provides a novel extension of Erlang mixtures for density estimation to the intensity estimation setting. The prior model structure supports general shapes for the point process intensity function, and it also enables effective handling of the Poisson process likelihood normalizing term resulting in efficient posterior simulation. The Erlang mixture modeling approach is further elaborated to develop an inference method for spatial Poisson processes. The methodology is examined relative to existing Bayesian nonparametric modeling approaches, including empirical comparison with Gaussian process prior based models, and is illustrated with synthetic and real data examples. 

   more » « less
5. An instrumental variable method for point processes: generalized Wald estimation based on deconvolution

   https://doi.org/10.1093/biomet/asad005  

   Jiang, Zhichao; Chen, Shizhe; Ding, Peng (January 2023, Biometrika)

   Summary Point processes are probabilistic tools for modelling event data. While there exists a fast-growing literature on the relationships between point processes, how such relationships connect to causal effects remains unexplored. In the presence of unmeasured confounders, parameters from point process models do not necessarily have causal interpretations. We propose an instrumental variable method for causal inference with point process treatment and outcome. We define causal quantities based on potential outcomes and establish nonparametric identification results with a binary instrumental variable. We extend the traditional Wald estimation to deal with point process treatment and outcome, showing that it should be performed after a Fourier transform of the intention-to-treat effects on the treatment and outcome, and thus takes the form of deconvolution. We refer to this approach as generalized Wald estimation and propose an estimation strategy based on well-established deconvolution methods. 

   more » « less