David Bruce Wilson I am a principal researcher at Microsoft Research and an affiliate associate professor at the University of Washington math department. articles gallery of pictures software web site for perfect sampling with Markov chains information resources software sites Northwest Probability Seminar – October 25, 2014 interesting links 425 703-7736 (click for captions)

Pfaffian formulas for spanning tree probabilities, by Greta Panova and David B. Wilson, 2014. arXiv:1407.3748.

A forward-backward single-source shortest paths algorithm, by David B. Wilson and Uri Zwick, 2014. arXiv:1405.7619.
Extended abstract appeared in Proc. 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 707–716, 2013.

The looping rate and sandpile density of planar graphs, by Adrien Kassel and David B. Wilson, 2014. arXiv:1402.4169.

The conformal loop ensemble nesting field, by Jason Miller, Samuel S. Watson, and David B. Wilson, 2013. arXiv:1401.0218.

Extreme nesting in the conformal loop ensemble, by Jason Miller, Samuel S. Watson, and David B. Wilson, 2013. arXiv:1401.0217.

On the asymptotics of dimers on tori, by Richard W. Kenyon, Nike Sun, and David B. Wilson, 2013. arXiv:1310.2603.

The Hausdorff dimension of the CLE gasket, by Jason Miller, Nike Sun, and David B. Wilson. Annals of Probability, 42(4)1644–1665, 2014. arXiv:1206.0725.

Dyck tilings, linear extensions, descents, and inversions, by Jang Soo Kim, Karola Mészáros, Greta Panova, and David B. Wilson, Journal of Combinatorial Theory A 122:9-27, 2014. arXiv:1205.6578.
Extended abstract appeared in DMTCS Proceedings for the 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), pages 769–780, 2012.

The min mean-weight cycle in a random network, by Claire Mathieu and David B. Wilson. Combinatorics, Probability & Computing 22(5):763–782, 2013.

Avoidance coupling, by Omer Angel, Alexander E. Holroyd, James Martin, David B. Wilson, and Peter Winkler. Electronic Communications in Probability, 18(58):1–13, 2013.

Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs, by Richard W. Kenyon and David B. Wilson, 2011. arXiv:1107.3377. To appear in Journal of the American Mathematical Society.

XOR-Ising loops and the Gaussian free field, by David B. Wilson, 2011. arXiv:1102.3782

The dimension of loop-erased random walk in 3D, by David B. Wilson. Physical Review E 82(6):062102, 2010.

Double-dimer pairings and skew Young diagrams, by Richard W. Kenyon and David B. Wilson. Electronic Journal of Combinatorics 18(1) #P130, 2011.

Schramm's proof of Watts' formula, by Scott Sheffield and David B. Wilson. Annals of Probability, 39(5):1844–1863, 2011.

Approach to criticality in sandpiles, by Anne Fey, Lionel Levine, and David B. Wilson. Physical Review E 82, 031121, 2010. (Contains proofs of results announced in below PRL article.)

Driving sandpiles to criticality and beyond, by Anne Fey, Lionel Levine, and David B. Wilson. Physical Review Letters 104:145703, 2010.

Event-chain Monte Carlo algorithms for hard-sphere systems, by Etienne P. Bernard, Werner Krauth and David B. Wilson. Physical Review E 80, 056704, 2009.

Combinatorics of tripartite boundary connections for trees and dimers, by Richard W. Kenyon and David B. Wilson. Electronic Journal of Combinatorics 16(1):R112, 2009.

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks, by Omer Angel, Abraham D. Flaxman, and David B. Wilson. Combinatorica 32(1):1–33, 2012.

“Coupling from the past,” by James G. Propp and David B. Wilson, Chapter 22 of the textbook “Markov Chains and Mixing Times,” by David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, published by the American Mathematical Society, 2009. [download for free] [order from AMS]

Chip-firing and rotor-routing on directed graphs, by Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson. In and Out of Equilibrium 2, eds. Vladas Sidoravicius and Maria Eulália Vares, “Progress in Probability” vol. 60, pages 331–364, Birkhäuser (2008).

Card shuffling and Diophantine approximation, by Omer Angel, Yuval Peres, and David B. Wilson. Annals of Applied Probability, 18(3):1215–1231, 2008.

The electrical response matrix of a regular 2n-gon, by Nathaniel D. Blair-Stahn and David B. Wilson. Proceedings of the American Mathematical Society 137(6):2015–2025, 2009.

Two-player Knock 'em Down, by James A. Fill and David B. Wilson. Electronic Journal of Probability, 9:198–212, 2008.

Conformal radii for conformal loop ensembles, by Oded Schramm, Scott Sheffield, and David B. Wilson. Communications in Mathematical Physics 288(1):43–53, 2009.

Boundary partitions in trees and dimers, by Richard W. Kenyon and David B. Wilson. Transactions of the American Mathematical Society 363(3):1325–1364, 2011.

Tug-of-war and the infinity Laplacian, by Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson. Journal of the American Mathematical Society 22(1):167–210, 2009.

Random-turn Hex and other selection games, by Yuval Peres, Oded Schramm, Scott Sheffield, and David B. Wilson. American Mathematical Monthly, 114:373–387, May 2007.

SLE coordinate changes, by Oded Schramm, and David B. Wilson. New York Journal of Mathematics, 11:659–669, 2005.

Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read, by Itai Benjamini, Oded Schramm, and David B. Wilson. In Proc. 37th ACM Symposium on Theory of Computing, pages 244–250, 2005.

Excited Random Walk, by Itai Benjamini and David B. Wilson. Electronic Communications in Probability, 8:86–92, 2003.

Mixing Time of the Rudvalis Shuffle, by David B. Wilson. Electronic Communications in Probability, 8:77–85, 2003.

Winding angle variance of Fortuin-Kasteleyn contours, by Benjamin Wieland and David B. Wilson. Physical Review E 68, 056101, 2003.

On the Red-Green-Blue Model, by David B. Wilson. Physical Review E 69, 037105, 2004.

Critical resonance in the non-intersecting lattice path model, by Richard W. Kenyon and David B. Wilson. Probability Theory and Related Fields 130(3):289–318, 2004.

Mixing times of lozenge tiling and card shuffling Markov chains, by David B. Wilson. The Annals of Applied Probability, 14(1):274–325, 2004.

On the critical exponents of random k-SAT, by David B. Wilson. Random Structures and Algorithms, 21(2):182–195, 2002.

The Scaling Window of the 2-SAT Transition, by Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, and David B. Wilson. Random Structures and Algorithms 18(3):201–256, 2001.

Diagonal Sums of Boxed Plane Partitions, by David B. Wilson. Electronic Journal of Combinatorics 8(1):N1, 2001.

Layered multishift coupling for use in perfect sampling algorithms (with a primer on CFTP), by David B. Wilson. In Neil Madras, editor, Monte Carlo Methods, volume 26 of Fields Institute Communications, pages 143–179. American Mathematical Society, 2000.

Trees and Matchings, by Richard W. Kenyon, James G. Propp, and David B. Wilson. Electronic Journal of Combinatorics, 7(1):R25, 2000.

How to Couple from the Past Using a Read-Once Source of Randomness, by David B. Wilson. Random Structures and Algorithms 16(1):85–113, 2000.

Scaling Limits for Minimal and Random Spanning Trees in Two Dimensions, by Michael Aizenman, Almut Burchard, Charles M. Newman, and David B. Wilson. Random Structures and Algorithms 15(3&4):319–367, 1999.

Sampling Spin Configurations of an Ising System, by Dana Randall and David B. Wilson. 10th Symposium on Discrete Algorithms (SODA) pp. S959–960, 1999.

Coupling from the past: a user's guide, by James G. Propp and David B. Wilson. In D. Aldous and J. Propp, editors, Microsurveys in Discrete Probability, volume 41 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 181–192. American Mathematical Society, 1998.
Postscript.

How to Get a Perfectly Random Sample From a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph by James G. Propp and David B. Wilson. Journal of Algorithms 27:170–217, 1998.
This article combines two conference articles, the first one appearing in The 1996 ACM-SIAM Symposium on Discrete Algorithms (SODA), and the second one appearing in The 1996 ACM Symposium on the Theory of Computing.

Random Random Walks on Z₂^d, by David B. Wilson. Probability Theory and Related Fields, 108(4):441–457, 1997.

Determinant Algorithms for Random Planar Structures, by David B. Wilson. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pp. 258–267, 1997.

Beyond Islands: Runs in Clone-Probe Matrices, by David S. Greenberg, Cynthia A. Phillips, and David B. Wilson. RECOMB 97, Proceedings of the First Annual International Conference on Computational Molecular Biology, pp. 320–329, 1997.

Learning Foraging Thresholds for Lizards, by Leslie Ann Goldberg, William E. Hart, and David B. Wilson. J. Theoretical Biology, 197:361–369. A preliminary version appeared in Proceedings of the 9th Conference on Computational Learning Theory, pp. 2–9, 1996.

Exact Sampling with Coupled Markov Chains and Applications to Statistical Mechanics, by James G. Propp and David B. Wilson. Random Structures and Algorithms, 9(1&2):223–252, 1996.

On the Number of Graphs Which Lack Small Cycles, by Daniel J. Kleitman and David B. Wilson. To appear in Discrete Mathematics.

Fast Exponentiation with Precomputation: Algorithms and Lower Bounds, by Ernest F. Brickell, Daniel M. Gordon, Kevin S. McCurley, and David B. Wilson. An extended abstract of this paper appeared in Advances in Cryptology: Eurocrypt '92, Lecture Notes in Computer Science #658, pp. 200–207.

Embedding Leveled Hypercube Algorithms into Hypercubes, by David B. Wilson. SPAA '92, 4th Annual ACM Symposium on Parallel Algorithms and Architectures , pp. 264–270, 1992.
This is the article version of my bachelor's thesis, which won the William A. Martin memorial prize for best undergraduate computer science thesis at MIT. (The thesis was supervised by Charles E. Leiserson.)

Hexamania

Play the game of random turn Hex. To learn more about the game, refer to the article “Random-turn and other selection games”. This program runs on Windows, and requires the .NET framework. May be used for non-commerical purposes free of charge.

vaxmacs 1.6e

Given a bipartite planar graph, computes the number of perfect matchings, placement probabilities, and more with an Emacs-19 or Emacs-20 interface. Requires maple and emacs 19.30 or better. This program was inspired by the vaxmaple program (described here), which was originally written by Greg Kuperberg and extended by Jim Propp and myself.

xrc

Generate random cluster states, single-temperature or omnithermal, 2D or 3D, and compute the internal energy, spontaneous magnetization, magnetic susceptibility, or correlation distance. Includes X and PostScript graphics.

PNG and GIF and SVG pictures:

• RGB model
• zooming into a fractal loop
• random lozenge tiling of a hexagon
• CLE₄ gasket
• hypercube routing
• rational resonance diagram
• animation of Dyck tiling bijection
• animation of "Wilson's algorithm" for making random spanning trees
• avoidance coupling

• illustration of monotone coupling from the past
• maze generated via cycle-popping
• animated illustration of cycle-popping and loop-erased random walk
• RGB model conformally mapped to circle
• perfectly equilibrated 2D Ising state at the critical temperature (529k)
• Pictures for the Random Tilings Research Group T-shirt (with contributions from Matt Blum and Henry Cohn)
  • random tiling of Aztec diamond by dominos
  • random tiling of hexagon by lozenges
• A perfectly random lozenge tiling of a much larger hexagon makes the “arctic circle phenomenon” more evident.
• perfectly random 4-state Potts configurations at the critical temperature.
• See also the perfect simulation gallery.
• Routing messages in a hypercube
  • 3-cube node mape and edge maps for dimensions 0, 1, and 2.
  • Edge map for dimension 0 of the 6-cube
• Peano curve and a variation
• mixing rate of random random walks
  • answer and previous bounds for Z₂^d
  • answer for Z_b^d, b fixed
• graphs that don't have small cycles
  • minimal 8-circuits
  • 3-cycle/4-cycle-connected components in a graph with no 6-cycles
• Borromean rings and a variation
• Blueprint for rhombic dodecahedron
• illustration of the generalized Temperley bijection
• placement probabilities in order 40 diabolo-weighted Aztec diamond

• Game theory lecture notes
• Los Alamos Physics E-Print Archive
• Front for the XXX Mathematics Archive
• MathSciNet reviews
• ACM Digital Library
• Inverse Symbolic Calculator
• Integer Sequences
• Mathematical Constants
• Stony Brook Algorithms Repository
• NASA/IPAC Extragalactic Database
• National Center for Biotechnology Information
• People in Probability
• The Electronic Journal of Combinatorics and World Combinatorics Exchange
• The Electronic Journal of Probability and Electronic Communications in Probability
• MIT Science Fiction Society Library and its online catalog
• MIT's RSI Information Page

• GNU Emacs for Windows 95/98/NT/ME/2000/XP
• MiKTeX
• Expect - Expect - Home Page
• Ghostscript, Ghostview and GSview
• gzip Homepage
• GIF file format documentation
• xfig & fig2dev

• MIT Lecture Series Committee
• Random Tilings Research Group
• Jason Woolever's random tiling applets
• Jason Miller's imaginary geometry pictures
• Mike Bostock's animations of Wilson's algorithm and the properties of the resulting uniform spanning tree
  • algorithm on square grid with free boundary conditions
  • depth-first color flood of UST
  • larger-scale depth-first color flood of UST
  • Reingold-Tilford animated layout of UST
  • Reingold-Tilford (nonanimated) layout of UST
  • “maze hover”
• Jim Propp's Mathematical Links
• The Dilbert Zone
• The Lois McMaster Bujold Nexus
• The man who planted trees, L'Homme qui plantait des arbres
• A kind word