<p>This is a question about properties of large directed graphs which are preserved when we randomly sample edges. </p>

<p>Imagine I have an infinite sequence of positively weighted directed graphs.  The graphs are represented by adjacency matrices</p>

<p>$$M_1,M_2,...,M_n,...$$
where each $M_n \in \mathbb{R}^{n \times n}$. The sup-norm $\|M_n\|_{\infty} = \max_{i} \sum_{j=1}^n |M_{n}(i,j)|$ is uniformly bounded by some bound $B$  for all $n \in \mathbb{N}$. Furthermore, for any $\ell &lt; n $ we have $M_{\ell}(i,j) = M_n(i,j)$ as long as $i,j \leq \ell$. </p>

<p>Many times we do not observe the full graph. Instead of observing $M_n$, we observe a random variable $\tilde{M_n}$
where 
$$\tilde{M_n}(i,j) = \begin{cases} M_n(i,j) &amp; \text{ with probability } \pi \\ 0   &amp; \text{ with probability } 1-\pi.\end{cases}$$</p>

<p>Let $\tilde{y_n} = f(\tilde{M_n})$ be a real-valued function of the matrix $\tilde{M_n}$. Using a Chernoff bound, I know that if $f(\tilde{M_{n}}) = \sum_{i,j} a_{ij} \tilde{M_n(i,j)}$ is a linear function, then the value of $f(\tilde{M_{n}})$ is tightly concentrated around its expectation, with the probability of it being ``far away'' form $E[f(\tilde{M_n})]$ decreasing exponentially with $n$.</p>

<p>Is this true for non-linear properties? For example, if $f(\tilde{M_n})$ is a convex function, do we have a similar concentration bound?</p>

CC BY-SA 3.0
2016-10-01T21:47:20.687Z
Is $n$ the size of the support of $M$? You need some information how $M_n$ related to $n$, otherwise there is no way to guarantee tail bounds exponentially small in $n$. Moreover, you need some Lipschitz condition on $f$. Even for a linear $f$, there is not much you can say if the $a_{ij}$ unbounded.
Sasho Nikolov
CC BY-SA 3.0
2016-10-01T21:55:06.520Z
Thanks, I realized my statement was not complete as I wrote it and edited the question. I can see how a Lipschitz condition is necessary, but is it known if it is sufficient?
Asterix
CC BY-SA 3.0
2016-10-02T03:35:57.393Z
If $f$ satisfies a sort of Hamming Lipschitz condition -- that is, $|f(M) - f(M')| \leq c$ if $M$ and $M'$ differ only in one entry -- then I think you should be able to directly apply McDiarmid's inequality, see https://en.wikipedia.org/wiki/Doob_martingale
usul
CC BY-SA 3.0
2016-10-02T03:44:26.317Z
By the way, to get exponential decay, probably either you have to renormalize by $n$ or "far away" should be paramterized by $n$. For example you'd expect results like $\Pr[ | f(M) - E f(M) | > \epsilon n] \leq \exp[ - O(\epsilon^2 n) ]$.
usul
<graph-theory><graph-algorithms><chernoff-bound>
Concentration Bounds for functions of matrices
Asterix
# Concentration Bounds for functions of matrices

(Asked by: username_0 on 2016-10-01)

This is a question about properties of large directed graphs which are preserved when we randomly sample edges.

Imagine I have an infinite sequence of positively weighted directed graphs. The graphs are represented by adjacency matrices

$$M\_1,M\_2,...,M\_n,...$$
where each $M\_n \in \mathbb{R}^{n \times n}$. The sup-norm $\|M\_n\|\_{\infty} = \max\_{i} \sum\_{j=1}^n |M\_{n}(i,j)|$ is uniformly bounded by some bound $B$ for all $n \in \mathbb{N}$. Furthermore, for any $\ell < n $ we have $M\_{\ell}(i,j) = M\_n(i,j)$ as long as $i,j \leq \ell$.

Many times we do not observe the full graph. Instead of observing $M\_n$, we observe a random variable $\tilde{M\_n}$
where
$$\tilde{M\_n}(i,j) = \begin{cases} M\_n(i,j) & \text{ with probability } \pi \\ 0 & \text{ with probability } 1-\pi.\end{cases}$$

Let $\tilde{y\_n} = f(\tilde{M\_n})$ be a real-valued function of the matrix $\tilde{M\_n}$. Using a Chernoff bound, I know that if $f(\tilde{M\_{n}}) = \sum\_{i,j} a\_{ij} \tilde{M\_n(i,j)}$ is a linear function, then the value of $f(\tilde{M\_{n}})$ is tightly concentrated around its expectation, with the probability of it being ``far away'' form $E[f(\tilde{M\_n})]$ decreasing exponentially with $n$.

Is this true for non-linear properties? For example, if $f(\tilde{M\_n})$ is a convex function, do we have a similar concentration bound?

**Tags:** graph-theory, graph-algorithms, chernoff-bound
> **Comments:**
> **username_1**: Is $n$ the size of the support of $M$? You need some information how $M_n$ related to $n$, otherwise there is no way to guarantee tail bounds exponentially small in $n$. Moreover, you need some Lipschitz condition on $f$. Even for a linear $f$, there is not much you can say if the $a_{ij}$ unbounded.  
> **username_0**: Thanks, I realized my statement was not complete as I wrote it and edited the question. I can see how a Lipschitz condition is necessary, but is it known if it is sufficient?  
> **username_2**: If $f$ satisfies a sort of Hamming Lipschitz condition -- that is, $|f(M) - f(M')| \leq c$ if $M$ and $M'$ differ only in one entry -- then I think you should be able to directly apply McDiarmid's inequality, see https://en.wikipedia.org/wiki/Doob_martingale  
> **username_2**: By the way, to get exponential decay, probably either you have to renormalize by $n$ or "far away" should be paramterized by $n$. For example you'd expect results like $\Pr[ | f(M) - E f(M) | > \epsilon n] \leq \exp[ - O(\epsilon^2 n) ]$.  

---

## 0 answers

