A tail bound for read‐k families of functions1. Issue 1 (6th March 2014) - Gavinsky, Dmitry; Lovett, Shachar; Saks, Michael; Srinivasan, Srikanth
Abstract We prove a Chernoff‐like large deviation bound on the sum of non‐independent random variables that have the following dependence structure. The variables <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqm21q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Y1, …, Yr</alternatives> are arbitrary [0, 1]‐valued functions of independent random variables <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqm39n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />X1, …, Xm</alternatives>, modulo a restriction that every Xi influences at most k of the variables <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqm3b6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Y1, …, Yr</alternatives>. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 99–108, 2015