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

At least 17 years old · documented by

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.

lim⁡n→∞Pr⁡(sup⁡0≤t≤α0n∣Rˉ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:0≤i≤dv,0≤j≤dv,0≤k≤dv,0≤i+j+k≤dv}\{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.

References

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.