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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 1 '16 at 21:47
  • $\begingroup$ 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? $\endgroup$ – Asterix Oct 1 '16 at 21:55
  • 2
    $\begingroup$ 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 en.wikipedia.org/wiki/Doob_martingale $\endgroup$ – usul Oct 2 '16 at 3:35
  • 2
    $\begingroup$ 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) ]$. $\endgroup$ – usul Oct 2 '16 at 3:44

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.