Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

My motivation for this question comes from the study of synchronizing automata. There is a general consensus that random automata are synchronizing and have short synchronizing words. I am hoping that this can be made precise.

Let $T_n$ be the monoid of all self-mappings of $\{1,\ldots, n\}$. What would are some natural ways to generate a random subset of $T_n$?

I am particularly interested in models which seem intuitive and for which there is some hope to compute/estimate the following.

  1. The probability the subsemigroup generated by a random set contains a constant map
  2. The expected minimum length of a constant map.

One possible way to choose a random subset is to flip a coin for each element of $T_n$ and add it to the subset if we get a heads, but I don't really like this method.

A second method might be to first flip $n^n$ coins. Let $k$ be the number of heads. Then choose $k$ transformations in some random way. Perhaps one can choose without repetition $k$ iid transformations according to some distribution on elements of $T_n$. Possible distributions would be the uniform distribution or a stationary distribution of some natural random walk on $T_n$ (side note, what is a natural random walk on $T_n$?). Or one can use the distribution based on the method of generating a transformation by choosing the image of each $i\in \{1,\ldots,n\}$ uniformly at random from $\{1,\ldots, n\}$.

Any thoughts?

share|improve this question
    
I must be dense, but what is wrong with Generating a random mapping by picking some element of range(n) for each element of range(n). This gives a random mapping. If you want $k$ such, do it $k$ times. What am I missing? –  Igor Rivin May 26 '12 at 17:56
    
This generates a random mapping but I want a random set of mapping including the size of the set. –  Benjamin Steinberg May 26 '12 at 20:53
    
When you say "flip a coin," what sort of probability are you thinking of for including each self-map? And how would you want to handle the case where there is no constant map in the subsemigroup? –  Douglas Zare May 26 '12 at 21:00
    
I said flip a coin, I meant each element has 50% chance of being included. I don't like this method because it doesn't have anything to do with the specific nature of $T_n$. It is generating a random subset of any set. I suspect under any reasonable model, almost always there will be a constant map. For instance, it is known that any uniform random 2n-tuple from $T_n$ has product a constant map as $n\to \infty$. –  Benjamin Steinberg May 27 '12 at 0:45
    
With positive probability, there will not be a constant map in the semigroup, so how do you want to handle the expected minimum length if there is a positive probability that this is infinite? The reason I asked about the probability is that the type of techniques you might want to use to estimate the minimum length will probably not be the same if there is a high probability that the minimum length is $1$ or $2$ versus if the median length is $\Theta(n)$. –  Douglas Zare May 27 '12 at 1:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.