PDA

View Full Version : Is random sampling impossible? - from continuous random variables.



tashirosgt
2012-Sep-06, 03:15 AM
Much of the theory of statistics deals with random samples from continuous random variables. Is such sampling actually possible?

Sampling a continouous random variable is impossible in a trivial sense, in the same way that exactly bisecting an angle with a physical appartus is impossible. It's due to the limited precision of physical devices. Physical sources of random "noise" measured by physical devices produce approximate outputs.

There is a purely mathematical type of impossibility, for example, the impossibility of trisecting an angle "with a ruler and compass". The phrase "with a ruler and compass" restricts the operation to certain mathematical methods. The impossiblity of accomplishing the task is just as much a mathematical fact as the non-existence of a largest real number. It's interesting to consider whether sampling a continuous random variable is impossible in this mathematical sense.

To determine this, we must specify what methods are allowed. A common scenario in the theory of computability is to assume we use an idealization of a computer, such a Turning machine. For computations involving randomness, it's common to assume the algorithm can have external inputs of "real" randomness. These have limited precision. For example, an input might be a 0 or 1 representing the result of tossing a fair coin.

I'm not an expert in the the theory of computability, but it seems to me that, with those restrictions, an algorithm that terminates in a finite length of time cannot generate samples from a continuous random variable. The cardinality of the possible outputs appears to be a "countable" infinity and the cardinality of an interval of real numbers is an "uncountable" infinity.

Some may say "We can't trisect angles, but we can still define the trisectors of an angle as mathematical objects. We ave methods that approximate the trisectors to any desired degree of accuracy. We can't randomly sample continous random variables, but we can conceive of such samples and we can approximate sampling from a continuous random variable to any desired degree of accuracy".

You can define angle trisectors and approximate them, but how do you even define doing continuous random sampling "to any desired degree of accuracy"? Try to specify a rigorous epsilon-delta type definition. I can make one that "works" for the uniform distribution on [0,1], but I don't see how to do it for distributions like the Gaussian which have an unbounded range of values.

There are sources on the web that discuss "samplable" probability distributions from the point of view of the theory of computability but I haven't found one that deigns to explain what the various definitions of "samplable" say when applied to continouous real valued random variables. If anyone can give an interpretation, I'd like to hear it.

HenrikOlsen
2012-Sep-06, 10:57 AM
The thing is that finite random sampling can be shown to be a mathematically stable operation under the normally reasonable assumption that the probability distribution is continuous.

tashirosgt
2012-Sep-06, 02:18 PM
The thing is that finite random sampling can be shown to be a mathematically stable operation under the normally reasonable assumption that the probability distribution is continuous.

What do you mean by "finite sampling"? - taking a finite number of samples? It isn't clear that you can even take one sample. The mathematical theorems about sampling simply assume you can take samples. They say "if ... are random samples from ....then.....".

Or do you mean taking a finite number of samples, each of which has a finite precision? That is possible and it's the only situation that actually arises, but remarkably little mathematics is written about it. What is done falls under the heading of dealing with "censored data".

I don't think "mathematically stable operation" has a standard definition, but I appreciate the concept that samples can ("probably") be used to estimate the parameters of probability distributions. Theorems to that effect simply assume sampling can be done. They assume each sample value is known exactly - i.e. it has infinite precision.

orionjim
2012-Sep-06, 02:56 PM
...

I don't think "mathematically stable operation" has a standard definition, but I appreciate the concept that samples can ("probably") be used to estimate the parameters of probability distributions. Theorems to that effect simply assume sampling can be done. They assume each sample value is known exactly - i.e. it has infinite precision.

Indeed it does! Look at the work of Walter Shewhart, also the difference between enumerative and analytic studies.

The outputs of the random samples are numbers that the average and standard deviation are calculated from. This output is an estimate of the distribution of the population plus the error in the system of measuring that you are talking about.

There are ways of calculating measurement error and removing itsí estimated error from the total estimated distribution. This will get you closer but itís still an estimation.

tashirosgt
2012-Sep-06, 03:25 PM
Indeed it does! Look at the work of Walter Shewhart, also the difference between enumerative and analytic studies.


If it has a mathematical definition, please state it.




The outputs of the random samples are numbers that the average and standard deviation are calculated from. This output is an estimate of the distribution of the population plus the error in the system of measuring that you are talking about.

There are ways of calculating measurement error and removing its’ estimated error from the total estimated distribution. This will get you closer but it’s still an estimation.

That has nothing to do with the question of whether sampling from continous distributions is possible.

HenrikOlsen
2012-Sep-06, 03:31 PM
What I meant with finite samples was both finite number of samples and finite precision.
What I meant with mathematically stable is that that more samples mean an increase in confidence aka reduced likely error.
That said, it's easy to come up with degenerate cases where no amount of extra samples will make the result more sensible.

orionjim
2012-Sep-06, 05:11 PM
...
To determine this, we must specify what methods are allowed. A common scenario in the theory of computability is to assume we use an idealization of a computer, such a Turning machine. For computations involving randomness, it's common to assume the algorithm can have external inputs of "real" randomness. These have limited precision. For example, an input might be a 0 or 1 representing the result of tossing a fair coin.

....

My Bold

I'll bet you meant Turing Machine not Turning Machine.

tashirosgt
2012-Sep-06, 07:07 PM
What I meant with finite samples was both finite number of samples and finite precision.
What I meant with mathematically stable is that that more samples mean an increase in confidence aka reduced likely error.
That said, it's easy to come up with degenerate cases where no amount of extra samples will make the result more sensible.

I understand your assertion. However, the topic of the thread concerns whether it is possible to take random samples from a continuous random variable - meaning the type of sampling that is usually assumed in statistics. In that type of sampling, there is no limit on the precison of the sample values. They are assumed to be exact.

I suspect it isn't hard to prove a variation of The Central Limit Theorem where the samples have finite precision, but that isn't one of the assumptions of the Central Limit Theorem itself.

This thread isn't about all the nice things you can do if you have random samples. It's about whether you can take random samples. It isn't about the precision of the quantity that is estimated from the samples.

tashirosgt
2012-Sep-06, 07:20 PM
My Bold

I'll bet you meant Turing Machine not Turning Machine.

You're correct! I hope my question is clear now.

Ivan Viehoff
2012-Sep-07, 09:24 AM
The real number line is a mathematical construct that doesn't exist in the physical world. Nevertheless it is a useful tool, because it is a lot easier to do calculations on continuous variables than to treat them all as discrete variables with an interval at the level of precision of physical measurement. In the usual case the continuous treatment will be a very good approximation to discrete reality, assuming there is sufficient precision of measurement, and the continuous integrations are usually a lot easier than summing the discrete series.

Pointing out that you can't really take samples of continuous random variables because of a lack of infinite precision measurement is throwing the baby out with the bathwater.

tashirosgt
2012-Sep-07, 04:36 PM
. In the usual case the continuous treatment will be a very good approximation to discrete reality


It's easy to agree with the spirit of that statement,but I don't think it's simple to give it "very good approximation" a mathematical definition. It's rather like knowing the intutitive meaning of a limit versus the epsilon-delta definition of a limit.



Pointing out that you can't really take samples of continuous random variables because of a lack of infinite precision measurement is throwing the baby out with the bathwater.

My questions are 1) Whether it is mathematically possible (in the framework of the theory of computability) to take samples of a continouos random variable , 2) Whether "samplable" distributions, as defined in the theory of computability, include continouous probability distributions 3) How to mathematically define the concept that sampling from a continuous probability distribution can be adequately approximated by sampiing from a discrete distribution.

I haven't advocated "throwing out" any statistical procedures if that's what you were implying.

Ivan Viehoff
2012-Sep-10, 03:43 PM
My questions are 1) Whether it is mathematically possible (in the framework of the theory of computability) to take samples of a continouos random variable , 2) Whether "samplable" distributions, as defined in the theory of computability, include continouous probability distributions 3) How to mathematically define the concept that sampling from a continuous probability distribution can be adequately approximated by sampiing from a discrete distribution.
Qs 1 & 2, I expect you will find the answer in these lecture notes on advanced computational complexity theory, which is beyond what I have studied. http://dimacs.rutgers.edu/~adib/538/lec12.pdf If you want more assistance, I suggest you go lurk in some mathematician's forum.

If computability interests you, my recent post here might amuse you. http://cosmoquest.org/forum/showthread.php/138009-Monopoly-Game-new-special-Alan-Turing-version

Q3. The Riemann integral is based upon an approximation of the area by lots of little columns (though of course famously the Lebesgue integral gives stronger results on weaker assumptions). So I expect it is closely bound up with whether the density function is Riemann-integrable or not. Any particular case will require case-by-case examination, have your epsilons and deltas to hand.

Jerry
2012-Sep-11, 05:37 AM
Random sampling produces a statistically correct answer about a population. The confidence of the answer is limited by the size of the population, the size of the sample, and any erroneous assumptions or measurements.

Assuming the basic assumptions are sound and the sample size is large enough, the laws of probability come in to play. But the answer can still be wrong: a 'random' sample of ~2000 voters in the US can give you a set of presidental predictions that are within ~3% of being correct ~99.7 percent of the time; But 0.03% of the time the answer will be wrong.

tashirosgt
2012-Sep-12, 09:33 PM
Random sampling produces a statistically correct answer about a population..

That isn't relevant to the question of whether you can do random sampling.

Jerry
2012-Sep-13, 07:19 AM
That isn't relevant to the question of whether you can do random sampling.

Random sampling is only defined within a statistical context - without context the term is ambiguous.

Randomly, I can sample the air, the water or core bore a tree, and without a test objective within a statistical framework, I have nothing. That is my point - Within a population, there is a definition of a random sample that will give you statistically valid results, even if the answer is wrong.

By the way, a random sample that includes every member of a population will yield an answer that is significant with a confidence level of one, and yes, you can 'do' this random sample.

tashirosgt
2012-Sep-13, 07:25 AM
Random sampling is only defined within a statistical context - without context the term is ambiguous.


Random sampling from a given continuous probability distribution is "a statistical context". The topic of the thread whether that sort of random sampling is possible. This is a question of computability theory not a question of statistical inference.

Ivan Viehoff
2012-Sep-13, 08:57 AM
This is a question of computability theory not a question of statistical inference.
Although your first post did proceed to discuss computability theory, nearly everyone here would fail to see the relevance. I did too, even though I have studied computability theory, albeit not to the required level to realise that it does address the point you are interested in, until you clarified. I would be surprised if you found anyone here who has sufficient knowledge/competence in the required level of computability theory to address the point you are interested in. I think you will find more joy somewhere that mathematicians congregate.

tashirosgt
2012-Sep-13, 02:53 PM
I think you will find more joy somewhere that mathematicians congregate.

I'm not lacking in joy and I already visit several math forums on the internet.

Your estimate of the current membership of Cosmo Quest may be correct. In fact, since bautforum was absorbed, the "Science And Technoglogy" section has, shall we say, "broadened in scope", so it is dominated by threads on Futurism, debunking, discussions of scenarios useful to writers, etc. Perhaps the "Science and Technology" section on Cosmo Quest has always been that way.

I don't mind not getting answers. As to irrelevant answers, the originator of a thread usually has no control on the content of the thread, but tradition allows him to keep trying!

People who find no joy in thread don't have to read it or contribute to it.

grapes
2012-Sep-13, 03:23 PM
People who find no joy in thread don't have to read it or contribute to it.I been busy :)

Much of the theory of statistics deals with random samples from continuous random variables. Is such sampling actually possible?

Sampling a continouous random variable is impossible in a trivial sense, in the same way that exactly bisecting an angle with a physical appartus is impossible. It's due to the limited precision of physical devices. Physical sources of random "noise" measured by physical devices produce approximate outputs.

There's an even more trivial sense in which it is impossible--there is no *physical* continuous random variable.


There is a purely mathematical type of impossibility, for example, the impossibility of trisecting an angle "with a ruler and compass". The phrase "with a ruler and compass" restricts the operation to certain mathematical methods. The impossiblity of accomplishing the task is just as much a mathematical fact as the non-existence of a largest real number. It's interesting to consider whether sampling a continuous random variable is impossible in this mathematical sense.

To determine this, we must specify what methods are allowed. A common scenario in the theory of computability is to assume we use an idealization of a computer, such a Turning machine. For computations involving randomness, it's common to assume the algorithm can have external inputs of "real" randomness. These have limited precision. For example, an input might be a 0 or 1 representing the result of tossing a fair coin.

I'm not an expert in the the theory of computability, but it seems to me that, with those restrictions, an algorithm that terminates in a finite length of time cannot generate samples from a continuous random variable. The cardinality of the possible outputs appears to be a "countable" infinity and the cardinality of an interval of real numbers is an "uncountable" infinity.

Some may say "We can't trisect angles, but we can still define the trisectors of an angle as mathematical objects.
And I would say, we can trisect angles, in the mathematical sense. The limitations are not absolute. We can allow more than just a compass and straightedge, for instance. Even better, it is possible to trisect an angle using just a compass and straightedge: http://cosmoquest.org/forum/showthread.php/95912-A-singularity-free-N-Body-problem-%E2%80%93-solution?p=1624338#post1624338


We ave methods that approximate the trisectors to any desired degree of accuracy. We can't randomly sample continous random variables, but we can conceive of such samples and we can approximate sampling from a continuous random variable to any desired degree of accuracy".

You can define angle trisectors and approximate them, but how do you even define doing continuous random sampling "to any desired degree of accuracy"? Try to specify a rigorous epsilon-delta type definition. I can make one that "works" for the uniform distribution on [0,1], but I don't see how to do it for distributions like the Gaussian which have an unbounded range of values.

If you can do it for the uniform distribution, you can do it for almost any other distribution. There is a mathematical function that transforms one into the other.

http://www.spacetimeandtheuniverse.com/groups/mathemagic-d9-knuth-papoulis.html

tashirosgt
2012-Sep-13, 05:06 PM
There's an even more trivial sense in which it is impossible--there is no *physical* continuous random variable.


Is that "true", in the sense that there is some theory of physics which uses probability and disallows continuous randm variables? Quantum mechanics insists that some (physical) random variables be discrete, but does it say that all physical random variables have discrete distributions?



And I would say, we can trisect angles, in the mathematical sense. The limitations are not absolute. We can allow more than just a compass and straightedge, for instance.


I agree that mathematical "impossibility" is always defined within some framework. Even the "impossibility" of have a largest real number is established within a framework of a set of axioms. There are several ways to define computability, and I'd like to know if any of them make it possible to sample from a continuous random variable. As to going to other frameworks, I'm not interested in them since they don't embody what is possible with refinements of current computers.



Even better, it is possible to trisect an angle using just a compass and straightedge: http://cosmoquest.org/forum/showthread.php/95912-A-singularity-free-N-Body-problem-%E2%80%93-solution?p=1624338#post1624338


If so (in the sense that "with a ruler and compass" is meant in traditional math), it would make a nice ATM thread on a math forum.



If you can do it for the uniform distribution, you can do it for almost any other distribution. There is a mathematical function that transforms one into the other.


That depends on what "it" is. First, we must define what it means to approximate a continuous random variable by a discrete random variable. For example, take the unform distribution on [0,1]. The follwing is possible: For each epsilon > 0 there exists a discrete distribution with N (a finite number of ) values v[i] in the interval [0,1] such that the probability of each v[i] is 1/N and for each x in [0,1] some v[i] is within epsilon of x.

The same type of approximation is not possible for a normal (i.e. gaussian) distribution. You can't find a finite set of values v[i] such that each x in (-infinity, +infinity) is within some epsilon of v[i].

The fact that a uniform distribution can be transformed into another distribution doesn't mean that the approximating properties of an associated discrete distribution are preserved under the same transformation.

grapes
2012-Sep-14, 03:01 AM
Is that "true", in the sense that there is some theory of physics which uses probability and disallows continuous randm variables?
No, it's just that there are no continuous values that we, as observers, can sample.


If so (in the sense that "with a ruler and compass" is meant in traditional math), it would make a nice ATM thread on a math forum.
There's absolutely nothing ATM about it--most people don't realize what is involved in the classical restrictions to compass and ruler. That construction at that link uses nothing but compass and ruler, but it doesn't satisfy the classical requirements. It's a construction that is attributed to Archimedes, I think.


That depends on what "it" is.
"define doing continuous random sampling 'to any desired degree of accuracy'"
:)


First, we must define what it means to approximate a continuous random variable by a discrete random variable. For example, take the unform distribution on [0,1]. The follwing is possible: For each epsilon > 0 there exists a discrete distribution with N (a finite number of ) values v[i] in the interval [0,1] such that the probability of each v[i] is 1/N and for each x in [0,1] some v[i] is within epsilon of x.

The same type of approximation is not possible for a normal (i.e. gaussian) distribution. You can't find a finite set of values v[i] such that each x in (-infinity, +infinity) is within some epsilon of v[i].
You don't really use the distribution in that definition. How would you use your method to approximate a distribution that was not uniform, but finite?


The fact that a uniform distribution can be transformed into another distribution doesn't mean that the approximating properties of an associated discrete distribution are preserved under the same transformation.In a sense, yes it does. I think that might become clearer as you try to use your method to approximate more complicated distributions.

tashirosgt
2012-Sep-14, 03:46 AM
You don't really use the distribution in that definition. How would you use your method to approximate a distribution that was not uniform, but finite?

A definition isn't really a method, but I suppose it defines when a method is successful. So, we can try this:

The continuous random variable X with probability density f(x) is "finitely approximable by discrete distributions" shall mean that for each real number epsilon > 0 there exists a discrete distribution g(k) that is non-zero on a finite set of N distinct values v[1], v[2],...v[N] and such that for each x if f(x) > 0 then x is within epsilon some v[i] and such that the following hold:
for k = 1, g[k] = Integral from -infinity to (v[1] + v[2])/2 of f(x) dx
for k = N, g[k] = integral from (v[N-1) + V[N])/2 to infinity of f(x) dx
For 1 < k < N, g[k] = integral from (V(k-1) to V[k])/2 to (V(k) + V(k+1))/2 of f(x) dx

"The fact that a uniform distribution can be transformed into another distribution doesn't mean that the approximating properties of an associated discrete distribution are preserved under the same transformation. "


In a sense, yes it does.

OK, but "in a sense" and actually it doesn't. Perhaps you mean that we can come up with another definition of approximation that will be preserved under transformation.

I think it's impossible to effectively estimate all properties of a given distribution by sampling it (exactly or approximately). For example, one property of a given gaussian distribution is whether its mean is a rational number. There is no version of the Central Limit Theorem that says you can answer that question with a large number of samples.

So another stratetgy for defining "finitely approximable by discrete distributions" would be for it to mean that whenever we can effectively estimate some property by (exact) random sampling from a continuous distribution, we can also estimate the same property just as effectively by sampling from some discrete distribution. Of course, what it means to estimate "effectively" would have to be specified. (And there is the possibility that by that definition, no commonly used continuous probability distribution is finitely approximable by discrete distributions. )

grapes
2012-Sep-14, 04:25 AM
Approximating a density function is not the same thing as "doing continuous random sampling 'to any desired degree of accuracy'"

How would you produce those random samples with that distribution?


I think it's impossible to effectively estimate all properties of a given distribution by sampling it (exactly or approximately). For example, one property of a given gaussian distribution is whether its mean is a rational number. There is no version of the Central Limit Theorem that says you can answer that question with a large number of samples.
What question?

It is certainly possible to *estimate* the mean of the distribution by sampling. By "all properties" you're including whether or not the mean is rational or not? :)

So another stratetgy for defining "finitely approximable by discrete distributions"

"define doing continuous random sampling 'to any desired degree of accuracy'" is a different goal. Maybe.

tashirosgt
2012-Sep-14, 02:18 PM
Approximating a density function is not the same thing as "doing continuous random sampling 'to any desired degree of accuracy'"


That's an interesting assertion, but impossible to confirm until "to any desired degree of accuracy" is precisely defined.




How would you produce those random samples with that distribution?

I'm assuming we are permitted to do sampling by using an algorithm which has, as inputs, random samples from discrete distributions. (A common model for these inputs in computatbility theory is the results of coin-flips.) We I would have to demonstrate a way to transform the results of such inputs to samples from a discrete distribution that has the probabilities that the definition specifies. I don't know if such a transformation is always possible. ( My attempt at a definition is a definition, not an assertion of a theorem. And there could be alternative approaches to the definition that allow an "epsilon of error" in the probabilities of the discrete samples as well as in their values.)



What question?

The question of whether the mean is a rational number.



It is certainly possible to *estimate* the mean of the distribution by sampling. By "all properties" you're including whether or not the mean is rational or not?


By taking random samples, It is possible to effectively estimate an interval containing the value of the mean. It is not, as far as I know, possible to effectively estimate whether the mean is a rational number or not.

I'm suggesting that another idea for defining "approximates to any desired degree of accuracy" is express the general notion that a property that can be effectively estimated by random sampling a finitely approximable continuous distribution should be effectively estimable by sampling some related discrete distribution. (Note: "a property that....", not simply "a property". So such a definition would exclude the requirement that the discrete distribution be usable for determining whether the mean of the continuous distribution was a rational number.)

grapes
2012-Sep-14, 07:33 PM
That's an interesting assertion, but impossible to confirm until "to any desired degree of accuracy" is precisely defined.
No, I didn't mean it as an assertion. I meant, the density function is a mathematical function, but the sampling is not the function. It's the difference between the shape of a cow (on paper!), and the cow itself.


I'm assuming we are permitted to do sampling by using an algorithm which has, as inputs, random samples from discrete distributions. (A common model for these inputs in computatbility theory is the results of coin-flips.) We I would have to demonstrate a way to transform the results of such inputs to samples from a discrete distribution that has the probabilities that the definition specifies. I don't know if such a transformation is always possible.
That link was to two transformations, to the Rayleigh distribution, and to the Normal distribution. The fundamental theorem describes how to do it.


( My attempt at a definition is a definition, not an assertion of a theorem. And there could be alternative approaches to the definition that allow an "epsilon of error" in the probabilities of the discrete samples as well as in their values.)



The question of whether the mean is a rational number.
That's what I thought! :)

That doesn't usually come up in statistics. :)


By taking random samples, It is possible to effectively estimate an interval containing the value of the mean. It is not, as far as I know, possible to effectively estimate whether the mean is a rational number or not. As far as I know, producing an estimate to determine whether any number is rational or not, doesn't make sense. :)

tashirosgt
2012-Sep-14, 09:03 PM
No, I didn't mean it as an assertion. I meant, the density function is a mathematical function, but the sampling is not the function. It's the difference between the shape of a cow (on paper!), and the cow itself.


I agree with that point.



That link was to two transformations, to the Rayleigh distribution, and to the Normal distribution. The fundamental theorem describes how to do it.


"it"? (The link to the "Space,Time and The Universe" wants me to login.) I agree that 1)A random variable may be tranformed to another, by defining the second to be a function of the first 2) The distribution of a random variable determines the distribution of independent samples of it and functions of the values of those independent samples, and these may not be the same as the distribution of the random variable itself.

However, nothing I'm attempting to define contradicts those facts.



As far as I know, producing an estimate to determine whether any number is rational or not, doesn't make sense. :)

It may not make practical sense, but I'm talking about mathematics, not engineering. Any statement that can be made about a distribution is fair game for a "property" of the distribution. Perhaps we could define "sensible" properties of a distribution as those that can be effectively estimated by taking random samples of it.

In statistics an "estimator" is a function of the values in a random sample. (The term "random sample" can refer to more than one or more realizations of a random variable. The number of realizations in sample is called the "size" of the sample.) By this definition, It's isn't necessary to declare what, if anything, the estimator is trying to estimate. Practical applications of estimators so rely on theorems about how particular estimators estimate particular things. An estimator doesn't have to be a continuous function of the sample values. It can be a function that takes on only the values 0 or 1. So it can be a "yes" or "no" kind of estimate.

grapes
2012-Sep-14, 10:01 PM
"it"? Given two continuous probability distributions, construct the function that transforms one to the other.

If you've set up a way to generate a Uniform random variable, the corresponding transform will generate a Normal random variable. That was the goal of the OP, as I understood it.

It may not make practical sense, but I'm talking about mathematics, not engineering.
I was talking about math as well. :)

If you approximate a real number--and the discussion has been about continuous distributions--no matter how close to the number you get, there will always be a rational number, and an irrational number, nearby. Unless you've figured out a way to determine the number exactly--in which case, you probably can tell whether it's rational or not.

Paul Wally
2012-Sep-14, 10:43 PM
Much of the theory of statistics deals with random samples from continuous random variables. Is such sampling actually possible?

I'm trying to understand the question. What does it mean to take "random samples from a continuous random variable"? As I understand it sampling is an empirical operation performed in the physical world and a continuous random variable is a purely mathematical construct. Do you mean by "sampling", generating a set of data points from a probability density function with that same corresponding statistical properties?

tashirosgt
2012-Sep-15, 01:15 AM
Given two continuous probability distributions, construct the function that transforms one to the other.

If you've set up a way to generate a Uniform random variable, the corresponding transform will generate a Normal random variable. That was the goal of the OP, as I understood it.


I agree the transformation is possible. The usual method for sampling from a continuous distribution with cumulative distribution F(x) is to pick a sample x from a uniform random variable on [0,1] and then take F^-1(x), the inverse function of F evaluated a x.

Is your point: "if you can find a computable way to take random samples from a uniform distribution then this gives you a way to take random samples from any continuous distribution"? I agree with the proviso (seeing as my question involves computability) that we also must ask if the inverse function of F is a computable function.



If you approximate a real number--and the discussion has been about continuous distributions--no matter how close to the number you get, there will always be a rational number, and an irrational number, nearby. Unless you've figured out a way to determine the number exactly--in which case, you probably can tell whether it's rational or not.

I agree. That's why I don't think question of whether the mean of a particular gaussian distribution is a rational number can be effectively estimated by sampling the distribution. The fact the question can't be answered by random sampling doesn't imply that the answer to the question is not a property of the distribution. My point is that not all properties of a distribution are estimable by sampling. So if we want to define what it means to do approximate sampling of a continuous distribution, we shouldn't pursue the idea that "all properties" of the continuous distribution must be estimable from the approximate samples.

tashirosgt
2012-Sep-15, 01:50 AM
As I understand it sampling is an empirical operation performed in the physical world and a continuous random variable is a purely mathematical construct

No, there is well developed mathematical theory of random sampling. Random sampling also exists as a "purely mathematical construct".

The mathematical theory of random sampling taught in statistics courses assumes that continuous random variables can be sampled exactly. There are other fields of mathematics that use a framework of assumptions that is a closer imitation of physical reality. Some versions fo computability theory assume we can only use finite strings of symbols to represent things. My questions involve various ways to apply this outlook to random sampling.

tashirosgt
2012-Sep-15, 08:00 PM
A remark on the link that Ivan gave: http://dimacs.rutgers.edu/~adib/538/lec12.pdf

I've found a number of similar definitions and I haven't found a link where the notation being used is explained.

The definition in those notes says:

Definition 1. An ensemble of probability distributions \mu is polynomial-time samplable if there exists an expected polynomial-time randomized algorithm S the, on inputs of the form 1^n, outputs each x in [0,1]^n with probability \mu_n (x) .

I think [0,1]^n might denote the collection of sequences of length n , each of whose terms is either a 0 or a 1 .
I'm not sure whether "ensemble" is a synonym for a generic collection of things or whether it has a more technical meaning.