The Linking Probability of Deep Spider-Web Networks
| dc.creator | Pippenger, Nicholas | |
| dc.date | 2005-02-14 | |
| dc.date.accessioned | 2026-07-07T05:17:00Z | |
| dc.date.available | 2026-07-07T05:17:00Z | |
| dc.description | We consider crossbar switching networks with base $b$ (that is, constructed from $b\times b$ crossbar switches), scale $k$ (that is, with $b^k$ inputs, $b^k$ outputs and $b^k$ links between each consecutive pair of stages) and depth $l$ (that is, with $l$ stages). We assume that the crossbars are interconnected according to the spider-web pattern, whereby two diverging paths reconverge only after at least $k$ stages. We assume that each vertex is independently idle with probability $q$, the vacancy probability. We assume that $b\ge 2$ and the vacancy probability $q$ are fixed, and that $k$ and $l = ck$ tend to infinity with ratio a fixed constant $c>1$. We consider the linking probability $Q$ (the probability that there exists at least one idle path between a given idle input and a given idle output). In a previous paper it was shown that if $c\le 2$, then the linking probability $Q$ tends to 0 if $0<q<q_c$ (where $q_c = 1/b^{(c-1)/c}$ is the critical vacancy probability), and tends to $(1-ξ)^2$ (where $ξ$ is the unique solution of the equation $(1-q (1-x))^b=x$ in the range $0<x<1$) if $q_c<q<1$. In this paper we extend this result to all rational $c>1$. This is done by using generating functions and complex-variable techniques to estimate the second moments of various random variables involved in the analysis of the networks. | |
| dc.description | i+21 pp | |
| dc.identifier | https://arxiv.org/abs/math/0502294 | |
| dc.identifier | http://arxiv.org/abs/math/0502294 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/74196 | |
| dc.subject | Probability | |
| dc.subject | Combinatorics | |
| dc.subject | 90B18; 60C05 | |
| dc.title | The Linking Probability of Deep Spider-Web Networks | |
| dc.type | text |