# Will an arbitrary deterministic algorithm corresponds to a probability distribution

We know from simulation that if you want to generate a sequence of independent identically distributed (i.i.d.) $[0,1]$ uniform random variables, there is a deterministic algorithm denoted by $\mathcal{A}$ to do that such that the sequence generated by this algorithm will pass many statistical tests and hence "looks" like an i.i.d. sequence of uniform $[0,1]$. And from there, we can use this algorithm $\mathcal{A}$ to generate i.i.d. samples from almost any distribution by thinning or inverting the cdf. So the idea is that: if you want to have an i.i.d. sample of a given distribution, then certainly, there is a deterministic algorithm to do that.

Now my question is the following: is the reverse process true? Specifically, if I have an arbitrary deterministic algorithm $\mathcal{B}$ and I use it to generate a long list of numbers ($N$ numbers), then will there be some probability distribution $P_B$ such that this long list of numbers I generated can be viewed as $N$ i.i.d. samples from $P_B$? If the answer is yes, then will $P_B$ be unique?

The reason I am asking this question is because, in reality, when we observe a data set with $N$ observations, I think we can always consider this $N$ observations are generated by some unknown deterministic algorithm $\mathcal{B}$ and hence, it can be viewed as i.i.d. samples from some distribution $P$ that associated with $\mathcal{B}$. And from there, the i.i.d. property justifies many probability and statistics theorems.

• Given your special A is standard uniform distributed random number generator, of course that P is standard uniform distribution. – user158565 May 21 '17 at 19:46
• @a_statistician I guess I did not write the notation clear. I've changed that. I am asking for an arbitrary algorithm, let's call it B, I generates a list of $N$ numbers, then will this algorithm B corresponds to some (may be unique) probability distribution $P_B$ such that I can view my $N$ data points as i.i.d sample from $P_B$? Is there any mathematical foundation for that? – KevinKim May 21 '17 at 19:58
• Then my answer is NO (at least in statistical practice.) For example, I have $B_1$ for standard normal, $B_2$ for t-distribution with df = 1000. I give you a sequence of random number generated by one of them. I think you could not make the judgement which $B$ I used. Maybe when N is in billion level, you can make the judgement. – user158565 May 21 '17 at 20:13
• @a_statistician for the first step, I am thinking about theoretically, whether it is possible. So from your answer, I would consider it as: given an arbitrary deterministic algorithm $B$, and a list of numbers (as many as you wish) generated by $B$, it does correspond to a unique probability distribution $P_B$ such that my list of numbers can be viewed as i.i.d. sample from $P_B$ theoretically. Am I right? – KevinKim May 21 '17 at 20:23
• Yes, you are right. Given A generates iid uniform random number, you can construct B such that the random numbers generated by B are iid from P_B. Of course you can also generate dependent random number following the given distribution. But we just do not know what B or P_B is only based on data, if you do not tell us. – user158565 May 21 '17 at 21:10

for i = 1, 2, ...:

This algorithm will always output the sequence $(1, 2, 3, \dots)$, which cannot reasonably be interpreted as iid samples from any distribution, since they aren't stationary.
• Great! I get it. But let's put some restrictions to exclude this type of cases. What about the algorithm that generates numbers bounded by an interval $[a,b]$? Then will my claim true? – KevinKim May 22 '17 at 0:36
• No – just take $a, a+ \frac12(b-a), a+\frac34 (b-a),\dots$ and it's the same situation. In general, no deterministic algorithm outputs actual iid samples, and whether you can treat the outputs as iid depends very much on what kind of properties you care about. – Dougal May 22 '17 at 4:12