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:


*

*What would be an intuitive notation
for $\delta$? 

*Is $\delta$, as I've
    defined it above equivalent to a
    random permutation with repetition
    over the kleene closure of $\Sigma$?


Thank you,
 A: 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.
