Conductance (probability)
- Conductance (probability)
For an ergodic reversible Markov chain with an underlying graph "G", the conductance is a way to measure how hard it is to leave a small set of nodes. Formally, the conductance of a graph is defined as the minimum over all sets of the capacity of divided by the ergodic flow out of . Alistair Sinclair showed that conductance is closely tied to mixing time in ergodic reversible Markov chains. We can also view conductance in a more probabilistic way, as the minimal probability of leaving a small set of nodes given that we started in that set to begin with. Writing for the conditional probability of leaving a set of nodes S given that we were in that set to begin with, the conductance is the minimal over sets that have a total stationary probability of at most 1/2.
Conductance is related to Markov chain mixing time in the reversible setting.
ee also
* Percolation
References
* A. Sinclair. Algorithms for Random Generation and Counting: A Markov Chain Approach. Birkhauser, Boston-Basel-Berlin, 1993.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Conductance (graph) — For other uses, see Conductance. In graph theory the conductance of a graph G=(V,E) measures how well knit the graph is: it controls how fast a random walk on G converges to a uniform distribution. The conductance of a graph is often called the… … Wikipedia
Conductance quantum — The conductance quantum (G0) is the quantized unit of conductance. It is defined as G0 = 2e2/h = 7.7480917346(25)×10−5 Ω−1 ≈ 1⁄12900 Ω−1.[1] It appears when measuring the conductance of a quantum point contact. The name conductance… … Wikipedia
List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… … Wikipedia
Quantitative models of the action potential — In neurophysiology, several mathematical models of the action potential have been developed, which fall into two basic types. The first type seeks to model the experimental data quantitatively, i.e., to reproduce the measurements of current and… … Wikipedia
analysis — /euh nal euh sis/, n., pl. analyses / seez /. 1. the separating of any material or abstract entity into its constituent elements (opposed to synthesis). 2. this process as a method of studying the nature of something or of determining its… … Universalium
Scanning tunneling spectroscopy — (STS) is a powerful experimental technique in scanning tunneling microscopy (STM) that uses a scanning tunneling microscope (STM) to probe the local density of electronic states (LDOS) and band gap of surfaces and materials on surfaces at the… … Wikipedia
Action potential — In physiology, an action potential is a short lasting event in which the electrical membrane potential of a cell rapidly rises and falls, following a consistent trajectory. Action potentials occur in several types of animal cells, called… … Wikipedia
Depolarizing pre-pulse — A depolarizing pre pulse (DPP) is an electrical stimulus that causes the potential difference measured across a neuronal membrane to become more positive or less negative, and precedes another electrical stimulus.[1] DPPs may be of either the… … Wikipedia
AMPA receptor — The alpha amino 3 hydroxy 5 methyl 4 isoxazolepropionic acid receptor (also known as AMPA receptor, AMPAR, or quisqualate receptor) is a non NMDA type ionotropic transmembrane receptor for glutamate that mediates fast synaptic transmission in the … Wikipedia
nervous system — Anat., Zool. 1. the system of nerves and nerve centers in an animal or human, including the brain, spinal cord, nerves, and ganglia. 2. a particular part of this system. Cf. autonomic nervous system, central nervous system, peripheral nervous… … Universalium
