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,



Permutation with repetitions of a vocabulary
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.


