We prove that if $X,Y$ are positive, independent, non-Dirac random variables and if for $\alpha,\beta\ge 0$, $\alpha\neq \beta$, $$ \psi_{\alpha,\beta}(x,y)=\left(y\,\tfrac{1+\beta(x+y)}{1+\alpha x+\beta y},\;x\,\tfrac{1+\alpha(x+y)}{1+\alpha x+\beta y}\right), $$ then the random variables $U$ and $V$ defined by $(U,V)=\psi_{\alpha,\beta}(X,Y)$ are independent if and only if $X$ and $Y$ follow Kummer distributions with suitably related parameters. In other words, any invariant measure for a lattice recursion model governed by $\psi_{\alpha,\beta}$ in the scheme introduced by Croydon and Sasada in \cite{CS2020}, is necessarily a product measure with Kummer marginals. The result extends earlier characterizations of Kummer and gamma laws by independence of $$ U=\tfrac{Y}{1+X}\quad\mbox{and}\quad V= X\left(1+\tfrac{Y}{1+X}\right), $$ which corresponds to the case of $\psi_{1,0}$. We also show that this independence property of Kummer laws covers, as limiting cases, several independence models known in the literature: the Lukacs, the Kummer-Gamma, the Matsumoto-Yor and the discrete Korteweg de Vries ones.
相關內容
The Fast Fourier Transform (FFT) over a finite field $\mathbb{F}_q$ computes evaluations of a given polynomial of degree less than $n$ at a specifically chosen set of $n$ distinct evaluation points in $\mathbb{F}_q$. If $q$ or $q-1$ is a smooth number, then the divide-and-conquer approach leads to the fastest known FFT algorithms. Depending on the type of group that the set of evaluation points forms, these algorithms are classified as multiplicative (Math of Comp. 1965) and additive (FOCS 2014) FFT algorithms. In this work, we provide a unified framework for FFT algorithms that include both multiplicative and additive FFT algorithms as special cases, and beyond: our framework also works when $q+1$ is smooth, while all known results require $q$ or $q-1$ to be smooth. For the new case where $q+1$ is smooth (this new case was not considered before in literature as far as we know), we show that if $n$ is a divisor of $q+1$ that is $B$-smooth for a real $B>0$, then our FFT needs $O(Bn\log n)$ arithmetic operations in $\mathbb{F}_q$. Our unified framework is a natural consequence of introducing the algebraic function fields into the study of FFT.
We identify a family of $O(|E(G)|^2)$ nontrivial facets of the connected matching polytope of a graph $G$, that is, the convex hull of incidence vectors of matchings in $G$ whose covered vertices induce a connected subgraph. Accompanying software to further inspect the polytope of an input graph is available.
New lower order $H(\textrm{div})$-conforming finite elements for symmetric tensors are constructed in arbitrary dimension. The space of shape functions is defined by enriching the symmetric quadratic polynomial space with the $(d+1)$-order normal-normal face bubble space. The reduced counterpart has only $d(d+1)^2$ degrees of freedom. In two dimensions, basis functions are explicitly given in terms of barycentric coordinates. Lower order conforming finite element elasticity complexes starting from the Bell element, are developed in two dimensions. These finite elements for symmetric tensors are applied to devise robust mixed finite element methods for the linear elasticity problem, which possess the uniform error estimates with respect to the Lam\'{e} coefficient $\lambda$, and superconvergence for the displacement. Numerical results are provided to verify the theoretical convergence rates.
A periodic temporal graph $\mathcal{G}=(G_0, G_1, \dots, G_{p-1})^*$ is an infinite periodic sequence of graphs $G_i=(V,E_i)$ where $G=(V,\cup_i E_i)$ is called the footprint. Recently, the arena where the Cops and Robber game is played has been extended from a graph to a periodic graph; in this case, the copnumber is also the minimum number of cops sufficient for capturing the robber. We study the connections and distinctions between the copnumber $c(\mathcal{G})$ of a periodic graph $\mathcal{G}$ and the copnumber $c(G)$ of its footprint $G$ and establish several facts. For instance, we show that the smallest periodic graph with $c(\mathcal{G}) = 3$ has at most $8$ nodes; in contrast, the smallest graph $G$ with $c(G) = 3$ has $10$ nodes. We push this investigation by generating multiple examples showing how the copnumbers of a periodic graph $\mathcal{G}$, the subgraphs $G_i$ and its footprint $G$ can be loosely tied. Based on these results, we derive upper bounds on the copnumber of a periodic graph from properties of its footprint such as its treewidth.
We give a strongly explicit construction of $\varepsilon$-approximate $k$-designs for the orthogonal group $\mathrm{O}(N)$ and the unitary group $\mathrm{U}(N)$, for $N=2^n$. Our designs are of cardinality $\mathrm{poly}(N^k/\varepsilon)$ (equivalently, they have seed length $O(nk + \log(1/\varepsilon)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.
A code $C \subseteq \{0, 1, 2\}^n$ of length $n$ is called trifferent if for any three distinct elements of $C$ there exists a coordinate in which they all differ. By $T(n)$ we denote the maximum cardinality of trifferent codes with length. $T(5)=10$ and $T(6)=13$ were recently determined. Here we determine $T(7)=16$, $T(8)=20$, and $T(9)=27$. For the latter case $n=9$ there also exist linear codes attaining the maximum possible cardinality $27$.
We describe a new dependent-rounding algorithmic framework for bipartite graphs. Given a fractional assignment $y$ of values to edges of graph $G = (U \cup V, E)$, the algorithms return an integral solution $Y$ such that each right-node $v \in V$ has at most one neighboring edge $f$ with $Y_f = 1$, and where the variables $Y_e$ also satisfy broad nonpositive-correlation properties. In particular, for any edges $e_1, e_2$ sharing a left-node $u \in U$, the variables $Y_{e_1}, Y_{e_2}$ have strong negative-correlation properties, i.e. the expectation of $Y_{e_1} Y_{e_2}$ is significantly below $y_{e_1} y_{e_2}$. This algorithm is based on generating negatively-correlated Exponential random variables and using them in a contention-resolution scheme inspired by an algorithm Im & Shadloo (2020). Our algorithm gives stronger and much more flexible negative correlation properties. Dependent rounding schemes with negative correlation properties have been used for approximation algorithms for job-scheduling on unrelated machines to minimize weighted completion times (Bansal, Srinivasan, & Svensson (2021), Im & Shadloo (2020), Im & Li (2023)). Using our new dependent-rounding algorithm, among other improvements, we obtain a $1.4$-approximation for this problem. This significantly improves over the prior $1.45$-approximation ratio of Im & Li (2023).
A universal partial cycle (or upcycle) for $\mathcal{A}^n$ is a cyclic sequence that covers each word of length $n$ over the alphabet $\mathcal{A}$ exactly once -- like a De Bruijn cycle, except that we also allow a wildcard symbol $\mathord{\diamond}$ that can represent any letter of $\mathcal{A}$. Chen et al. in 2017 and Goeckner et al. in 2018 showed that the existence and structure of upcycles are highly constrained, unlike those of De Bruijn cycles, which exist for any alphabet size and word length. Moreover, it was not known whether any upcycles existed for $n \ge 5$. We present several examples of upcycles over both binary and non-binary alphabets for $n = 8$. We generalize two graph-theoretic representations of De Bruijn cycles to upcycles. We then introduce novel approaches to constructing new upcycles from old ones. Notably, given any upcycle for an alphabet of size $a$, we show how to construct an upcycle for an alphabet of size $ak$ for any $k \in \mathbb{N}$, so each example generates an infinite family of upcycles. We also define folds and lifts of upcycles, which relate upcycles with differing densities of $\mathord{\diamond}$ characters. In particular, we show that every upcycle lifts to a De Bruijn cycle. Our constructions rely on a different generalization of De Bruijn cycles known as perfect necklaces, and we introduce several new examples of perfect necklaces. We extend the definitions of certain pseudorandomness properties to partial words and determine which are satisfied by all upcycles, then draw a conclusion about linear feedback shift registers. Finally, we prove new nonexistence results based on the word length $n$, alphabet size, and $\mathord{\diamond}$ density.
Austrin showed that the approximation ratio $\beta\approx 0.94016567$ obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Games Conjecture (UGC) and modulo a Simplicity Conjecture that states that the worst performance of the algorithm is obtained on so called simple configurations. We prove Austrin's conjecture, thereby showing the optimality of the LLZ approximation algorithm, relying only on the Unique Games Conjecture. Our proof uses a combination of analytic and computational tools. We also present new approximation algorithms for two restrictions of the MAX 2-SAT problem. For MAX HORN-$\{1,2\}$-SAT, i.e., MAX CSP$(\{x\lor y,\bar{x}\lor y,x,\bar{x}\})$, in which clauses are not allowed to contain two negated literals, we obtain an approximation ratio of $0.94615981$. For MAX CSP$(\{x\lor y,x,\bar{x}\})$, i.e., when 2-clauses are not allowed to contain negated literals, we obtain an approximation ratio of $0.95397990$. By adapting Austrin's and our arguments for the MAX 2-SAT problem we show that these two approximation ratios are also tight, modulo only the UGC conjecture. This completes a full characterization of the approximability of the MAX 2-SAT problem and its restrictions.
In 1986, Flagg and Friedman \cite{ff} gave an elegant alternative proof of the faithfulness of G\"{o}del (or Rasiowa-Sikorski) translation $(\cdot)^\Box$ of Heyting arithmetic $\bf HA$ to Shapiro's epistemic arithmetic $\bf EA$. In \S 2, we shall prove the faithfulness of $(\cdot)^\Box$ without using stability, by introducing another translation from an epistemic system to corresponding intuitionistic system which we shall call \it the modified Rasiowa-Sikorski translation\rm . That is, this introduction of the new translation simplifies the original Flagg and Friedman's proof. In \S 3, we shall give some applications of the modified one for the disjunction property ($\mathsf{DP}$) and the numerical existence property ($\mathsf{NEP}$) of Heyting arithmetic. In \S 4, we shall show that epistemic Markov's rule $\mathsf{EMR}$ in $\bf EA$ is proved via $\bf HA$. So $\bf EA$ $\vdash \mathsf{EMR}$ and $\bf HA$ $\vdash \mathsf{MR}$ are equivalent. In \S 5, we shall give some relations among the translations treated in the previous sections. In \S 6, we shall give an alternative proof of Glivenko's theorem. In \S 7, we shall propose several(modal-)epistemic versions of Markov's rule for Horsten's modal-epistemic arithmetic $\bf MEA$. And, as in \S 4, we shall study some meta-implications among those versions of Markov's rules in $\bf MEA$ and one in $\bf HA$. Friedman and Sheard gave a modal analogue $\mathsf{FS}$ (i.e. Theorem in \cite{fs}) of Friedman's theorem $\mathsf{F}$ (i.e. Theorem 1 in \cite {friedman}): \it Any recursively enumerable extension of $\bf HA$ which has $\mathsf{DP}$ also has $\mathsf{NPE}$\rm . In \S 8, we shall give a proof of our \it Fundamental Conjecture \rm $\mathsf{FC}$ proposed in Inou\'{e} \cite{ino90a} as follows: $\mathsf{FC}: \enspace \mathsf{FS} \enspace \Longrightarrow \enspace \mathsf{F}.$ This is a new type of proofs. In \S 9, I shall give discussions.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191