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

Dear all;

Let $\Sigma$={a,b,c,d}, and $\delta$ be a function that returns a string $S$ of infinite length over $\Sigma$, where each character $s \in S$ has been chosen uniformly at random. My questions are the following:

  1. What would be an intuitive notation for $\delta$?
  2. Is $\delta$, as I've defined it above equivalent to a random permutation with repetition over the kleene closure of $\Sigma$?

Thank you,

share|improve this question
You did not tell us what the argument for $\delta$ is... In any case, why is $\delta$ not an intuitive notation? As for your second question: I cannot understand what you mean; maybe youcan b more explicit? –  Mariano Suárez-Alvarez Jul 28 '10 at 23:09

1 Answer 1

up vote 1 down vote accepted

For your first question, I would simply let $X$ be a random infinite string from the alphabet $\Sigma$. I don't see anything wrong with calling it $\delta$, either. I would treat it as a random variable, though. I don't really see the problem with treating it as a nondeterministic function either, but I'm not a computer scientist.

To answer your second question, let $\Sigma$ be any finite alphabet. Then $\Sigma^\star$, the Kleene closure, is the set consisting of the empty string, together with all finite strings consisting of elements of $\Sigma$. it is countably infinite, then: to list the elements, I put an ordering on $\Sigma$, and list the empty string, then the length 1 strings, then the length 2 strings, and so on, in lexicographic order. $\Sigma^\star$ contains no infinite strings.

If each string is chosen with probability $p$, then $\sum_{S \in \Sigma^\star} = 0$ (if $p$ is 0) or is undefined (if $p$ > 0). In either case, we do not have a probability measure -- there is no uniform distribution on any countably infinite set, so you cannot hope to sample uniformly from $\Sigma^\star$ unless $\Sigma = \emptyset$.

The reason this argument doesn't "break" the uniform distribution on $[0,1]$, say, is because we cannot sum over an uncountable index set.

In any case, there is no uniform distribution on $\Sigma^\star$, and your random variable is sampling from a different space.

share|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.