# Permutation with repetitions of a vocabulary

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,

-
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

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.