DIMACS

Center for Discrete Mathematics & Theoretical Computer Science

DIMACS EDUCATIONAL MODULE SERIES

MODULE 04-1

Probability and Chip Firing Games

Date prepared: September 1, 2004

Lynne L. Doty Marist College

Poughkeepsie, NY 12601 email: Lynne.Doty@Marist.edu

K. Peter Krog Marist College

Poughkeepsie, NY 12601 email: Peter.Krog@Marist.edu

Tracey Baldwin McGrail

Marist College Poughkeepsie, NY 12601

email: Tracey.McGrail@Marist.edu

DIMACS Center, CoRE Bldg., Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854-8018

TEL: 732-445-5928 • FAX: 732-445-5932 • EMAIL: center@dimacs.rutgers.edu

Web: http://dimacs.rutgers.edu/

Founded as a National Science Foundation Science and Technology Center and a Joint Project of Rutgers University,

Princeton University, AT&T Labs - Research, Bell Labs, NEC Laboratories America and Telcordia Technologies with affiliated members Avaya Labs, HP Labs, IBM Research, Microsoft Research.

Module Description Information

• Title:

Probability and Chip Firing Games

• Authors:

Lynne L. Doty, Marist College, Poughkeepsie, NY 12601 K. Peter Krog, Marist College, Poughkeepsie, NY 12601 Tracey Baldwin McGrail, Marist College, Poughkeepsie, NY 12601

• Abstract:

This module investigates the use of chip firing games on finite directed graphs as a “probabilistic abacus” that can be used to solve probability questions that might otherwise appear to require the use of complicated infinite geometric series. The use of chip firing games in this context leads naturally to the introduction of Markov analysis.

• Informal Description:

Probability questions arising from experiments or games of chance can often be difficult to solve due to the complicated nature of the collection of possible outcomes. In certain circumstances, there might be a way to organize what could be an infinite collection of outcomes into a finite form that would offer alternate means of analysis. This module addresses these issues and offers several different approaches to solving probability questions.

• Target Audience:

The intended audience consists of college students enrolled in a course on discrete mathematics or probability at the sophomore or junior level.

• Prerequisites:

Students should be familiar with infinite geometric series and basic discrete probability, including expected value. Section 5 of the module requires that students also be familiar with basic matrix operations.

• Mathematical Field:

Probability, Chip Firing Games, Markov analysis.

• Applications Areas:

Most of the applications in this module deal with games, including both games of chance and children’s board games. There is also an application to genetics in Section 5.

• Mathematics Subject Classification: Primary Classification: 91A43 Secondary Classifications: 91A60, 60J05

• Contact Information:

K. Peter Krog Department of Mathematics Marist College 3399 North Road Poughkeepsie, NY 12601 email: Peter.Krog@Marist.edu • Other DIMACS modules related to this module:

None at this time.