Concentration conjecture for the verification decoder's edge-type counts

Let tt denote the discrete decoding time, let Ri,j,k(t)R_{i,j,k}(t) be the number of edges connected to IVNs of type ri,j,kr_{i,j,k}, and let Rˉi,j,k(t)=E[Ri,j,k(t)Ht]\bar{R}_{i,j,k}(t)=E[R_{i,j,k}(t)\mid H_t], where HtH_t is the history up to time tt. Let α0n\alpha_0 n be the lifespan of the random process and let dvd_v be the maximum variable-node degree. Concentration conjecture.

limnPr(sup0tα0nRˉi,j,k(t)Ri,j,k(t)n5/6)=0\lim_{n\rightarrow \infty}\Pr\left(\sup_{0\le t\le \alpha_0 n}\left|\bar{R}_{i,j,k}(t)-R_{i,j,k}(t)\right|\ge n^{5/6}\right)=0

for all {i,j,k:0idv,0jdv,0kdv,0i+j+kdv}\{i,j,k:0\le i\le d_v,0\le j\le d_v,0\le k\le d_v,0\le i+j+k\le d_v\}. This concentration is one of the unproved assumptions needed to establish the correctness of the decoding analysis.

Sources & referencesView supporting material

Primary source

Fan Zhang and Henry D. Pfister, “Analysis of Verification-based Decoding on the q-ary Symmetric Channel for Large q”, arXiv:0806.3243 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.