7
$\begingroup$

Consider the following symmetric matrix (adjacency matrix): $$A=(a_{ij})_{1\leq i,j\leq n}$$ such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{ij}\leq2, 0<|i-j|<k$. This just means that the adjacency matrix $A$ has a banded structure, i.e. entries far away from the diagonal are 0.

Consider the solution of the following linear system: $$\begin{cases} (\sum_{j\neq1}a_{1j})x_1-\sum_{j\neq1}a_{1j}x_j=1\\ (\sum_{j\neq2}a_{2j})x_2-\sum_{j\neq2}a_{2j}x_j=-1\\ (\sum_{j\neq3}a_{3j})x_3-\sum_{j\neq3}a_{3j}x_j=0\\ (\sum_{j\neq4}a_{4j})x_4-\sum_{j\neq4}a_{4j}x_j=0\\ \vdots\\ (\sum_{j\neq n}a_{nj})x_n-\sum_{j\neq n}a_{nj}x_j=0 \end{cases}$$ In matrix notation, it is just $Lx=e_1-e_2$ where $L=D-A, D=diag\{d_1,...,d_n\}, d_i=\sum_{j\neq i}a_{ij}$. $L$ is just the graph Laplacian. I conjecture that there exists constant $C>0$ independent of $n$ such that $$\sum_{i,j}a_{ij}|x_i-x_j|\leq C$$ The physical meaning of the conjecture is that, if we flow 1 unit of current from node 1 to node 2, the sum of current of each edge in the given electrical network is bounded. Simulation result indicates that this is indeed the case. However, I somehow can only prove bound involving $n$. I think this may be related to the bandwidth of a graph?

This is also related to my previous question: Exponential decay of voltage potential difference

I have an intuitive idea of why this is the case. Since the total current flows out of node 1 is 1, then this 1 unit of current gets split into at least $k$ parts to the neighbors of 1. For each neighbor of 1, when the current flows out, it again gets split into at least $k$ parts and this somehow forms a geometric series that is summable.

Another idea is to use induction. The physical intuition is to examine how will the total current change when we gradually add new nodes and connections to the existing network. Adding new connections will decrease the effective resistance between 1 and 2 but new current will flow in new edges, they can somehow be balanced making the total current bounded.

$\endgroup$
0

1 Answer 1

5
+50
$\begingroup$

Edit: By request, I have added some explanations at the end. The first bullet may be helpful (it introduces a little notation). I also misread the question, and used a constant $k=3$ (instead of $k\ge 3$). This is now fixed, but $k$ must be fixed; for now the resulting bound depends on it...

Edit 2: I have added an idea on how to eliminate this issue, and (in comments) how to sharpen another bound. But the result here still depends on $k$.

Let's think of the problem as occuring on a multigraph (some edges are doubled) and interpret the Laplacian using hitting probabilities of a random walk.

The graph is more or less a long line segment, with edges between some nearby pairs of points. The vertex set is $\{1,\ldots,n\}$. Your solution $x$ is, up to a multiplicative constant $\alpha$ in $[0,1]$, the unique function $h:\{1,\ldots,n\}\rightarrow \mathbb{R}_+$ which is harmonic except at $\{1,2\}$ (by which I mean $(Lh)(k)=0$ for $k\notin \{1,2\}$) and satisfies $h(1)=0,h(2)=1$. This $h$ is nonnegative, taking values in the unit interval.

In fact, $h(i)$ is the probability that a random walk on the graph starting from $i$ will reach $2$ before $1$. You wish to prove $|h(i)-h(j)|$ decays at least exponentially in $\min(i,j)$ at a rate independent of $n$. This can be seen as follows: the probability that a random walk starting from $i$ and one starting from $j$ pass through a common vertex tends exponentially to $1$ in $\min(i,j)$, and if they pass through a common vertex with probability $\ge p$ then $|h(i)-h(j)| \le 2-2p$.

To see the last point, let's denote the random walk starting at $i$ and at $j$ by $W_i$ and $W_j$ respectively. Note that: $$|h(i) - \sum_{u=3}^n P(W_i \text{ intersects $W_j$ at vertex u and at no vertex $\ell > u$})\cdot h(k)| < P(W_i,W_j\text{ do not meet})$$ since the events "intersecting at vertex $k$ and no higher-index vertex" are mutually disjoint and each value of $h$ is in $[0,1]$ (then apply the law of total probability and the fact $h$ is a hitting probability). The same holds for $W_j$ and $h(j)$.

To see that the probability of intersecting does in fact approach $1$ exponentially, suppose $j>i$. Consider the random walk starting from $j$, and look at the first time it reaches a vertex $\ell\le i$. Then $i-\ell <k$ (where $k$ is a constant we fixed ahead of time). Now, if $i=\ell$ they do intersect; otherwise look at the next step of the random walk from $i$. It has a probability of at least $\frac{1}{4k-1}$ of landing at $\ell$ after one step. Observe this walk until the first time it reaches a vertex $i'$ smaller than $\ell$; if they do not intersect until then, then again $\ell - i' < k$, and the process continues... Thus there are at least $\min(i,j)/k$ opportunities for the random walks to intersect, each with probability at least $\frac{1}{4k-1}$ (a gross underestimate, but nevermind). This goes to $1$ exponentially in $\min(i,j)$, since the complement is at most $$\left(\frac{4k-2}{4k-1}\right)^{(\min(i,j)/k)}.$$


The case of $k$ large - an approach

First note that the multiplicative constant $\alpha \rightarrow 0$ when $k\rightarrow \infty$ - $\alpha = O(1/k)$.

Second, consider a vertex among $\{3,\ldots,k\}$. Its probability of landing at $1$ or at $2$ within one step is bounded by $4/k$. So the expected number of steps a random walk makes in $\{3,\ldots,k\}$ is bounded below by something like $k/4$, and the expected number of distinct vertices it hits is $O(k)$, with the probability of just $tk$ being hit being at most $O(t)$ for $t\in(0,\frac{1}{10})$.

Consider two random walks: let $S$ be the set of vertices the first one encounters among $\{3,\ldots,k\}$. Suppose there are $tk$ of these. Then the probability the second does not intersect it is at most $\approx(1-t/3)^s$, where $s$ is the second walk's number of steps among $\{3,\ldots,k\}$ (the $1/3$ appears because the odds of encountering a vertex among $\{3,\ldots,k\}$ need not be uniform, they depend on the matrix entries).

One can use the law of total probability to condition on $t,c$. Carrying this out to the end should show the non-intersection probability is bounded by a function of $k$ which approaches $0$ as $k\rightarrow\infty$, I guess it is something like $\frac{\log(k)}{k}$.

The next natural step is to sharpen the bound on $|h(i)-h(j)|$ given that random walks starting at $i,j$ are likely to intersect. (See comments.) It is hard to tell exactly how good the obtained bounds are without carrying out the computations, but it seems reasonable that this solves at least the cases in which $k$ is allowed to grow, but $n/k$ is bounded (a regime in which $k$ is assumed to be "large"), along with some further cases.


Some more details:

  • We regard the graph laplacian $L$ of a graph $(V,E)$ as an operator $V^\mathbb{R}\rightarrow V^\mathbb{R}$. It takes a function $h:V\rightarrow\mathbb{R}$ to the function $Lh$ defined by $$(Lh)(v)=\sum_{w\text{ a neighbor of $v$}}(h(v)-h(w)).$$ This is consistent with the possibly more familiar definition as a matrix $D-A$, where the $v$-th row of $L$ is given by the vector $$\deg(v)e_v - \sum_{w\text{ a neighbor of $v$}}e_w.$$ As in the question, some entries of the adjacency matrix may be $2$ and not just $1$. In this case, imagine two edges between the appropriate vertices, and sum over the corresponding term $(h(v)-h(w))$ with the appropriate multiplicity. This generalizes to arbitrary weights, though for a probabilistic interpretation we want them nonnegative...

  • If $h:V\rightarrow\mathbb{R}$ is given by $$h(v) = \text{the probability of reaching the vertex 2 before 1 in a random walk},$$ then $h$ is harmonic at every vertex except the vertices $1,2$ by the law of total probability (at the vertices $1$ and $2$, it takes the values $0$ and $1$ respectively regardless of the values of the neighbors). Indeed, denote by $X_{v,w}$ the event that the first step of a random walk starting at $v$ is a step to $w$, and $p_{v,w}=P(X_{v,w}).$ Then using the definition of $h$ we see: $$h(v)=\sum_\text{$w$ a neighbor of $v$}P(\text{the random walk from $w$ reaches 2 before 1}\vert X_{v,w})\cdot P(X_{v,w})$$ $$ = \sum_\text{$w$ a neighbor of $v$}h(w)\cdot p_{v,w},$$ and $p_{v,w}$ is just $$\frac{a_{v,w}}{\sum_\text{$u$ a neighbor of $v$}a_{v,u}}$$ in the language of the question. Hence $h(v)=(Ah)(v)/\deg(v)$, and $(Lh)(v)=0$.

  • Given $h$ defined as above, $h$ assumes only values between $0$ and $1$ (they are all probabilities by definition). Using $h(1)=0$ and $h(2)=1$, we have $$(Lh)(1) = -h(2) - \sum_\text{$x$ another neighbor of $1$} h(x) \le -1,$$ and similarly $$(Lh)(2) = h(2)-0 + \sum_\text{$x$ another neighbor of $2$}(h(2)-h(x)),$$ and each of the $h(x)$ is at most $1=h(2)$. So $(Lh)(2)\ge 1$. Now, the image of $L$ is always orthogonal to the constant function (each column of the matrix sums to $0$,) and $(Lh)(v)=0$ unless $v\in\{1,2\}$. Therefore $(Lh)(1)=-(Lh)(2)$.

  • The inequality $(Lh)(1)\le -1$, together with $(Lh)(1)=-(Lh)(2)$, implies there is some $\alpha \in [0,1]$ such that $f=\alpha\cdot Lh$ satisfies $$f(1)=-1,f(2)=1,$$ so it is the desired solution $x$.

$\endgroup$
25
  • $\begingroup$ How does the multiplicative constant depend on $n$, though? $\endgroup$
    – Kostya_I
    May 26, 2020 at 16:34
  • $\begingroup$ If I understand the question correctly, it doesn't matter: the maximal sum considered in the question occurs when it is 1. $\endgroup$ May 26, 2020 at 16:48
  • $\begingroup$ ah yes, you are right, that's because the conductivity is bounded below by $1$. $\endgroup$
    – Kostya_I
    May 26, 2020 at 16:53
  • $\begingroup$ Thanks! I'm not so familiar with random walks. Could you elaborate more on why is the solution $x$ up to some multiplicative constant the function $h$? $\endgroup$ May 26, 2020 at 18:20
  • 1
    $\begingroup$ @gyashfe Thanks that's very helpful! Another question is about bounding the probability that $W_i$ and $W_j$ do not meet. I do not quite follow. Why the first time $j$ reaches a node $\leq i$ can only be $i$ or $i-1$? $i-2,...,i-k$ should still be possible. $\endgroup$ May 26, 2020 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.