ترغب بنشر مسار تعليمي؟ اضغط هنا

A Note on the Probability of Rectangles for Correlated Binary Strings

71   0   0.0 ( 0 )
 نشر من قبل Or Ordentlich
 تاريخ النشر 2019
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Consider two sequences of $n$ independent and identically distributed fair coin tosses, $X=(X_1,ldots,X_n)$ and $Y=(Y_1,ldots,Y_n)$, which are $rho$-correlated for each $j$, i.e. $mathbb{P}[X_j=Y_j] = {1+rhoover 2}$. We study the question of how large (small) the probability $mathbb{P}[X in A, Yin B]$ can be among all sets $A,Bsubset{0,1}^n$ of a given cardinality. For sets $|A|,|B| = Theta(2^n)$ it is well known that the largest (smallest) probability is approximately attained by concentric (anti-concentric) Hamming balls, and this can be proved via the hypercontractive inequality (reverse hypercontractivity). Here we consider the case of $|A|,|B| = 2^{Theta(n)}$. By applying a recent extension of the hypercontractive inequality of Polyanskiy-Samorodnitsky (J. Functional Analysis, 2019), we show that Hamming balls of the same size approximately maximize $mathbb{P}[X in A, Yin B]$ in the regime of $rho to 1$. We also prove a similar tight lower bound, i.e. show that for $rhoto 0$ the pair of opposite Hamming balls approximately minimizes the probability $mathbb{P}[X in A, Yin B]$.



قيم البحث

اقرأ أيضاً

We study tight projective 2-designs in three different settings. In the complex setting, Zauners conjecture predicts the existence of a tight projective 2-design in every dimension. Pandey, Paulsen, Prakash, and Rahaman recently proposed an approach to make quantitative progress on this conjecture in terms of the entanglement breaking rank of a certain quantum channel. We show that this quantity is equal to the size of the smallest weighted projective 2-design. Next, in the finite field setting, we introduce a notion of projective 2-designs, we characterize when such projective 2-designs are tight, and we provide a construction of such objects. Finally, in the quaternionic setting, we show that every tight projective 2-design for H^d determines an equi-isoclinic tight fusion frame of d(2d-1) subspaces of R^d(2d+1) of dimension 3.
We define a correlated random walk (CRW) induced from the time evolution matrix (the Grover matrix) of the Grover walk on a graph $G$, and present a formula for the characteristic polynomial of the transition probability matrix of this CRW by using a determinant expression for the generalized weighted zeta function of $G$. As applications, we give the spectrum of the transition probability matrices for the CRWs induced from the Grover matrices of regular graphs and semiregular bipartite graphs. Furthermore, we consider another type of the CRW on a graph.
The codewords of weight $10$ of the $[42,21,10]$ extended binary quadratic residue code are shown to hold a design of parameters $3-(42,10,18).$ Its automorphism group is isomorphic to $PSL(2,41)$. Its existence can be explained neither by a transitivity argument, nor by the Assmus-Mattson theorem.
We prove an upper bound on the Shannon capacity of a graph via a linear programming variation. We show that our bound can outperform both the Lovasz theta number and the Haemers minimum rank bound. As a by-product, we also obtain a new upper bound on the broadcast rate of Index Coding.
In this paper, we make some progress towards a well-known conjecture on the minimum weights of binary cyclic codes with two primitive nonzeros. We also determine the Walsh spectrum of $Tr(x^d)$ over $F_{2^{m}}$ in the case where $m=2t$, $d=3+2^{t+1}$ and $gcd(d, 2^{m}-1)=1$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا