Another view of sequential sampling in the birth process with immigration
Abstract

We explore properties of the family sizes arising in a linear birth process with immigration (BI). In particular, we study the correlation of the number of families observed during consecutive disjoint intervals of time. LettingS(ab) be the number of families observed in (ab), we study the expected sample variance and its asymptotics forpconsecutive sequential samples$$S_p =(S(t_0,t_1),\dots , S(t_{p-1},t_p))$$${S}_{p}=\left(S\left({t}_{0},{t}_{1}\right),\cdots ,S\left({t}_{p-1},{t}_{p}\right)\right)$, for$$0=t_0$0={t}_{0}<{t}_{1}<\cdots <{t}_{p}$. By conditioning on the sizes of the samples, we provide a connection between$$S_p$$${S}_{p}$andpsequential samples of sizes$$n_1,n_2,\dots ,n_p$$${n}_{1},{n}_{2},\cdots ,{n}_{p}$, drawn from a single run of a Chinese Restaurant Process. Properties of the latter were studied in da Silva et al. (Bernoulli 29:1166–1194, 2023.https://doi.org/10.3150/22-BEJ1494). We show how the continuous-time framework helps to make asymptotic calculations easier than its discrete-time counterpart. As an application, for a specific choice of$$t_1,t_2,\dots , t_p$$${t}_{1},{t}_{2},\cdots ,{t}_{p}$, where the lengths of intervals are logarithmically equal, we revisit Fisher’s 1943 multi-sampling problem and give another explanation of what Fisher’s model could have meant in the world of sequential samples drawn from a BI process. more » « less NSF-PAR ID: 10490097 Author(s) / Creator(s): ; ; Publisher / Repository: Springer Science + Business Media Date Published: Journal Name: Journal of Mathematical Biology Volume: 88 Issue: 3 ISSN: 0303-6812 Format(s): Medium: X Sponsoring Org: National Science Foundation ##### More Like this 1. Abstract Given a suitable solutionV(tx) to the Korteweg–de Vries equation on the real line, we prove global well-posedness for initial data$$u(0,x) \in V(0,x) + H^{-1}(\mathbb {R})$$$u\left(0,x\right)\in V\left(0,x\right)+{H}^{-1}\left(R\right)$. Our conditions onVdo include regularity but do not impose any assumptions on spatial asymptotics. We show that periodic profiles$$V(0,x)\in H^5(\mathbb {R}/\mathbb {Z})$$$V\left(0,x\right)\in {H}^{5}\left(R/Z\right)$satisfy our hypotheses. In particular, we can treat localized perturbations of the much-studied periodic traveling wave solutions (cnoidal waves) of KdV. In the companion paper Laurens (Nonlinearity. 35(1):343–387, 2022.https://doi.org/10.1088/1361-6544/ac37f5) we show that smooth step-like initial data also satisfy our hypotheses. We employ the method of commuting flows introduced in Killip and Vişan (Ann. Math. (2) 190(1):249–305, 2019.https://doi.org/10.4007/annals.2019.190.1.4) where$$V\equiv 0$$$V\equiv 0$. In that setting, it is known that$$H^{-1}(\mathbb {R})$$${H}^{-1}\left(R\right)$is sharp in the class of$$H^s(\mathbb {R})$$${H}^{s}\left(R\right)$spaces. more » « less 2. Abstract It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$${L}_{\beta ,\gamma }=-\text{div}{D}^{d+1+\gamma -n}\nabla$associated to a domain$$\Omega \subset {\mathbb {R}}^n$$$\Omega \subset {R}^{n}$with a uniformly rectifiable boundary$$\Gamma $$$\Gamma$of dimension$$d < n-1$$$d, the now usual distance to the boundary$$D = D_\beta $$$D={D}_{\beta }$given by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$${D}_{\beta }{\left(X\right)}^{-\beta }={\int }_{\Gamma }{|X-y|}^{-d-\beta }d\sigma \left(y\right)$for$$X \in \Omega $$$X\in \Omega$, where$$\beta >0$$$\beta >0$and$$\gamma \in (-1,1)$$$\gamma \in \left(-1,1\right)$. In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$${L}_{\beta ,\gamma }$, with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$${D}^{1-\gamma }$, in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$$|D\nabla \left(ln\left(\frac{G}{{D}^{1-\gamma }}\right)\right){|}^{2}$satisfies a Carleson measure estimate on$$\Omega $$$\Omega$. We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear). more » « less 3. Abstract We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to {R}_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$${f}_{1},{f}_{2},\dots ,{f}_{r}$overNand requirements$$k_1,k_2,\ldots ,k_r$$${k}_{1},{k}_{2},\dots ,{k}_{r}$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$${f}_{i}\left(S\right)\ge {k}_{i}$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O\left(log\left(kr\right)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_{i}{k}_{i}$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$\left(1-1/e-\epsilon \right)$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O\left(\frac{1}{ϵ}logr\right)$in the cost. Second, we consider the special case when each$$f_i$$${f}_{i}$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraints Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems. more » « less 4. Abstract Let us fix a primepand a homogeneous system ofmlinear equations$$a_{j,1}x_1+\dots +a_{j,k}x_k=0$$${a}_{j,1}{x}_{1}+\cdots +{a}_{j,k}{x}_{k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$with coefficients$$a_{j,i}\in \mathbb {F}_p$$${a}_{j,i}\in {F}_{p}$. Suppose that$$k\ge 3m$$$k\ge 3m$, that$$a_{j,1}+\dots +a_{j,k}=0$$${a}_{j,1}+\cdots +{a}_{j,k}=0$for$$j=1,\dots ,m$$$j=1,\cdots ,m$and that every$$m\times m$$$m×m$minor of the$$m\times k$$$m×k$matrix$$(a_{j,i})_{j,i}$$${\left({a}_{j,i}\right)}_{j,i}$is non-singular. Then we prove that for any (large)n, any subset$$A\subseteq \mathbb {F}_p^n$$$A\subseteq {F}_{p}^{n}$of size$$|A|> C\cdot \Gamma ^n$$$|A|>C·{\Gamma }^{n}$contains a solution$$(x_1,\dots ,x_k)\in A^k$$$\left({x}_{1},\cdots ,{x}_{k}\right)\in {A}^{k}$to the given system of equations such that the vectors$$x_1,\dots ,x_k\in A$$${x}_{1},\cdots ,{x}_{k}\in A$are all distinct. Here,Cand$$\Gamma $$$\Gamma$are constants only depending onp,mandksuch that$$\Gamma $\Gamma . The crucial point here is the condition for the vectors$$x_1,\dots ,x_k$$${x}_{1},\cdots ,{x}_{k}$in the solution$$(x_1,\dots ,x_k)\in A^k$$$\left({x}_{1},\cdots ,{x}_{k}\right)\in {A}^{k}$to be distinct. If we relax this condition and only demand that$$x_1,\dots ,x_k$$${x}_{1},\cdots ,{x}_{k}$are not all equal, then the statement would follow easily from Tao’s slice rank polynomial method. However, handling the distinctness condition is much harder, and requires a new approach. While all previous combinatorial applications of the slice rank polynomial method have relied on the slice rank of diagonal tensors, we use a slice rank argument for a non-diagonal tensor in combination with combinatorial and probabilistic arguments.

more » « less
5. Abstract

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[{n}^{{\left(\mathrm{log}n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$$C$, by showing that$\mathcal { C}$$C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$$C$. Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$${\sum }_{i}{x}_{i}$. We show that for every sparsef, and for all “typical”$\mathcal { C}$$C$, faster#SAT algorithms for$\mathcal { C}$$C$circuits imply lower bounds against the circuit class$f \circ \mathcal { C}$$f\circ C$, which may bestrongerthan$\mathcal { C}$$C$itself. In particular:

#SAT algorithms fornk-size$\mathcal { C}$$C$-circuits running in 2n/nktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$$\left(f\circ C\right)$-circuits of polynomial size.

#SAT algorithms for$2^{n^{{\varepsilon }}}$${2}^{{n}^{\epsilon }}$-size$\mathcal { C}$$C$-circuits running in$2^{n-n^{{\varepsilon }}}$${2}^{n-{n}^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$$\left(f\circ C\right)$-circuits of polynomial size.

Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJACC0THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

more » « less