MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.