Markov Chain Simulations of Binary Matrices

Abstract

We consider Markov chains to simulate graphs with a fixed degree sequence and binary matrices with fixed row and column sums. By means of a combinatorial construction, we bound the subdominant eigenvalues of the chains. Under certain additional conditions, we show that the bounds are polynomial functions of the degree sequences and the row and column sums, respectively. Markov chain, spectral estimate, binary matrices, rapid mixing.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1992
Accession Number
ADA249265

Entities

People

  • William B. Krebs

Organizations

  • Florida State University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Birds
  • Computer Science
  • Construction
  • Eigenvalues
  • Graph Theory
  • Habitats
  • Markov Chains
  • Mathematics
  • Notation
  • Numbers
  • Polynomials
  • Probability
  • Random Walk
  • Sequences
  • Simulations
  • Statistical Analysis

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.