Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Coupling, and the Darling-Erdos Conjectures
201
0
0.0
(
0
)
Authors
Davar Khoshnevisan
Ask ChatGPT about the research
No Arabic abstract
We derive a new coupling of the running maximum of an Ornstein-Uhlenbeck process and the running maximum of an explicit i.i.d. sequence. We use this coupling to verify a conjecture of Darling and Erdos (1956).
rate research
Read More
Let $mathbf{X}$ be a random variable uniformly distributed on the discrete cube $left{ -1,1right} ^{n}$, and let $T_{rho}$ be the noise operator acting on Boolean functions $f:left{ -1,1right} ^{n}toleft{ 0,1right} $, where $rhoin[0,1]$ is the noise parameter, representing the correlation coefficient between each coordination of $mathbf{X}$ and its noise-corrupted version. Given a convex function $Phi$ and the mean $mathbb{E}f(mathbf{X})=ain[0,1]$, which Boolean function $f$ maximizes the $Phi$-stability $mathbb{E}left[Phileft(T_{rho}f(mathbf{X})right)right]$ of $f$? Special cases of this problem include the (symmetric and asymmetric) $alpha$-stability problems and the Most Informative Boolean Function problem. In this paper, we provide several upper bounds for the maximal $Phi$-stability. Considering specific $Phi$s, we partially resolve Mossel and ODonnells conjecture on $alpha$-stability with $alpha>2$, Li and Medards conjecture on $alpha$-stability with $1<alpha<2$, and Courtade and Kumars conjecture on the Most Informative Boolean Function which corresponds to a conjecture on $alpha$-stability with $alpha=1$. Our proofs are based on discrete Fourier analysis, optimization theory, and improvements of the Friedgut--Kalai--Naor (FKN) theorem. Our improvements of the FKN Theorem are sharp or asymptotically sharp for certain cases.
Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of ErdH{o}s-Renyi random graphs $G(n, p_n)$, where $p_n = n^{-alpha}$ for $0 < alpha < 1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-$1$ neighborhoods, $G$ is exactly reconstructable for $0 < alpha < frac{1}{3}$, but not reconstructable for $frac{1}{2} < alpha < 1$. Given the collection of distance-$2$ neighborhoods, $G$ is exactly reconstructable for $0 < alpha < frac{1}{2}$, but not reconstructable for $frac{3}{4} < alpha < 1$.
Given an unlabeled graph $G$ on $n$ vertices, let ${N_{G}(v)}_{v}$ be the collection of subgraphs of $G$, where for each vertex $v$ of $G$, $N_{G}(v)$ is the subgraph of $G$ induced by vertices of $G$ of distance at most one from $v$. We show that there are universal constants $C,c>0$ with the following property. Let the sequence $(p_n)_{n=1}^infty$ satisfy $n^{-1/2}log^C nleq p_nleq c$. For each $n$, let $Gamma_n$ be an unlabeled $G(n,p_n)$ Erdos-Renyi graph. Then with probability $1-o(1)$, any unlabeled graph $tilde Gamma_n$ on $n$ vertices with ${N_{tilde Gamma_n}(v)}_{v}={N_{Gamma_n}(v)}_{v}$ must coincide with $Gamma_n$. This establishes $p_n= tilde Theta(n^{-1/2})$ as the transition for the density parameter $p_n$ between reconstructability and non-reconstructability of Erdos-Renyi graphs from their $1$--neighborhoods, answering a question of Gaudio and Mossel.
We consider the median dynamics process in general graphs. In this model, each vertex has an independent initial opinion uniformly distributed in the interval [0,1] and, with rate one, updates its opinion to coincide with the median of its neighbors. This process provides a continuous analog of majority dynamics. We deduce properties of median dynamics through this connection and raise new conjectures regarding the behavior of majority dynamics on general graphs. We also prove these conjectures on some graphs where majority dynamics has a simple description.
We prove an Erdos-Feller-Kolmogorov-Petrowsky law of the iterated logarithm for self-normalized martingales. Our proof is given in the framework of the game-theoretic probability of Shafer and Vovk. As many other game-theoretic proofs, our proof is self-contained and explicit.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
