This article presents a technique for using stochastic Petri nets for real-time realization of Nth-order stochastic compositions (a Markov process). The algorithm makes use of a data structure known as a stochastic Petri table. This table is compact and suitable for interactive performance on small computers. We also show how the inherently concurrent nature of Petri nets can be used to implement real-time MIDI processing. Since readers may be unfamiliar with Petri nets, we present a brief introduction to the basic ideas behind the Petri net and compare it with the finite-state machine.