consider the set of all deterministic state machines of a given number of states, no terminal states and no input. (deterministic Markov chain might be a better description.) choose one of the machines uniformly randomly.
starting from any state, execution must eventually loop. what is the distribution of cycle lengths?
the question might need to be specified more precisely. simplest is distribution over one uniformly randomly chosen start state in one uniformly randomly chosen state machine. another way, considering all possible start states over one machine then all machines, yields a distribution over distributions.
No comments :
Post a Comment