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

<p><em>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$.</em> </p>

<p>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| &gt;\epsilon \cdot \mu_S \right\} \leq 2e^{-\epsilon^2 \mu_S /3}.
\end{align*}</p>

<p>I need to find a similar bound for a slightly more complicated process:</p>

<p><em>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}$</em> for all $j$.</p>

<p>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.</p>

CC BY-SA 3.0
2013-05-20T06:55:26.453Z
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|$).
afshi7n
CC BY-SA 3.0
2013-05-20T18:47:38.613Z
See the paper " Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding" which has some results related to this. http://www.cs.uiuc.edu/homes/chekuri/papers/intersection-rounding-soda.pdf
Chandra Chekuri
CC BY-SA 3.0
2013-05-20T19:39:32.857Z
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'.
afshi7n
CC BY-SA 3.0
2013-05-21T04:54:53.540Z
"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.
Chandra Chekuri
<pr.probability><randomized-algorithms><derandomization><chernoff-bound><iterated-rounding>
Concentration Bounds for Dependent Rounding
afshi7n
# Concentration Bounds for Dependent Rounding

(Asked by: username_0 on 2013-05-20)

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.

**Tags:** pr.probability, randomized-algorithms, derandomization, chernoff-bound, iterated-rounding
> **Comments:**
> **username_0**: 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|$).  
> **username_1**: See the paper " Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding" which has some results related to this. http://www.cs.uiuc.edu/homes/chekuri/papers/intersection-rounding-soda.pdf  
> **username_0**: 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'.  
> **username_1**: "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.  

---

## 0 answers

