how to test when correct output is "random"?

[Jeff Epler]

My current project, Novelwriting[1] is a knock-off of something called
the Dada Engine[2].  Essentially, you write a file that describes the
structure of a document, and Novelwriting outputs a document that
matches the structure.

I'd like to use this project as an opportunity to teach myself something
about testing methodology, but since the output is based on a random
number generator, how can the normal "unit test" or "doctest" tools work
for me?

Some things are fairly easy to test.  For instance, there are
"concatenation" rules, which read like
    T: A B;
    A: "a";
    B: "b";
I can easily test that str(T) == "ab".

But other parts are based on randomness.  "Alternation rules" are the
foundation on which this is built.  An alternation rule might read
like this:
    S: "a" | "b" | "c";
Then, str(S) would yield one of the alternatives.  Over many runs, it
should yield each choice about an equal number of times.  So how do
I test this?  Run a large number of trials and do a statistical test?
This doesn't seem to fit in with the philosophy of software testing,
which stresses exact repeatability.

Jeff
[1] http://unpythonic.net/jeff/novelwriting/
[2] http://dev.null.org/dadaengine/