Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$:

At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its value to $x'_i$ such that $0\leq x'_i \leq 1$ and $E[x'_i]=x_i$. We stop the process when all the numbers are either $0$ or $1$.

Given that the process is stopped, it is easy to verify that Chernoff bounds hold in the following sense: Let the outcome of the process be the binary numbers $y_1,\ldots,y_n$. For any subset $S$ of indices define $\mu_S=\sum_{i\in S} x_i$, then we have \begin{align*} \Pr\left\{\biggm|\mu_S - \sum_{i\in S} y_i\biggm| >\epsilon \cdot \mu_S \right\} \leq 2e^{-\epsilon^2 \mu_S /3}. \end{align*}

I need to find a similar bound for a slightly more complicated process:

At each step, pick a subset of numbers of size at most $d$, say $\{x_{i_1},\ldots,x_{i_d}\}$, and change their values to $\{x'_{i_1},\ldots,x'_{i_d}\}$ by either increasing all of these numbers or decreasing all of them. This is done in such a way that $0\leq x'_{i_j}\leq 1$ and $E[x'_{i_j}]=x_{i_j}$ for all $j$.

Can we get a similar result for this process too? For instance, is it possible to replace the right-hand side of the above bound with $2e^{-\epsilon^2 \mu/O(d)}$? Thank you very much.

  • $\begingroup$ Note: I have tried Azuma's inequality but unfortunately I could not get a bound which is only dependent to $\mu_S$ (and not $|S|$). $\endgroup$ – afshi7n May 20 '13 at 6:55
  • $\begingroup$ See the paper " Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding" which has some results related to this. cs.uiuc.edu/homes/chekuri/papers/intersection-rounding-soda.pdf $\endgroup$ – Chandra Chekuri May 20 '13 at 18:47
  • $\begingroup$ thanks, Chandra. I have read this very nice paper, if I change the rounding method, then this paper helps; I was also thinking of using your analysis there to get something similar here; Still I thought there might be a more standard solution since my question deals with dependencies of 'degree d'. $\endgroup$ – afshi7n May 20 '13 at 19:39
  • $\begingroup$ "Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds" by Panconesi and Srinivasan and "Chernoff-Hoeffding Bounds for Applications with Limited Independence" by Schmidt, Siegel and Srinivasan may be relevant. Writing to Aravind Srinivasan is also a good idea. $\endgroup$ – Chandra Chekuri May 21 '13 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.