If we agree that a partial output is a finite string over {H, T}, then the partial outputs are countably infinite (can be listed by a non-halting algorithm), and then cannot be considered as outcomes...
Maybe I need to ask you what an "outcome" is. According to you, there are no outcomes. And if I understand you correctly, the reason there are no outcomes is because the flipping program doesn't stop, not because the partial outputs create a countably infinitely list. That is, the non-outcome nature is tied to the program that actually generates the outcomes, not the program that lists the possible outcomes.
And then I'm still stuck where I can say that the partial output either was or was not {H}, and that at some moment in time it's either true or false that the partial output is {H}, and that this seems describable in some form using probabilistic language.
Quote:
because, in your language, one cannot choose at random from a countably infinite set.
I don't recall using that language. Maybe I did, but if I did it must have been a long time ago. And I don't know if I believe it.
So what are to be the outcomes in the coin flip scenario? I am saying that the partial outputs are a bad choice because they are countably infinite, and so one cannot choose at random from them.
I can't find a good citation for that claim right now, without linking to other online discussion forums, but if you google "random natural number" you will see what I mean.
You can't choose "randomly" from a countable infinite set if by "randomly" you mean, with equal probability for each element in the set. This is easy to see because the probabilities could not add up to 1. However, if by "randomly" you mean according to some probability measure on the set then it's easy to construct such a measure. For example, define P(a_k) = (1/2)^k for k=1,2,...
So what are to be the outcomes in the coin flip scenario? I am saying that the partial outputs are a bad choice because they are countably infinite, and so one cannot choose at random from them.
You are saying that it's a bad choice because the set of outcomes would be countably infinite. I don't think that's a necessary conclusion.
As I said, it seems perfectly reasonable to characterize the partial output of a non-halting program using probabilistic language. At any particular moment, the partial output is some finite sequence of characters. And it seems to make sense to ask what's the probability of that sequence being something and not something else.
For example, I can ask "What's the probability that the partial sequence is {H}?" It seems perfectly reasonable to say that the probability is 0 because we have no idea when the program was started or how fast it's running. Yet, this question can be asked and we can artificially stop the program and discover that the partial sequence really is something.
Quote:
I can't find a good citation for that claim right now, without linking to other online discussion forums, but if you google "random natural number" you will see what I mean.
I see lots of things. I don't know which one specifically you mean.
You can't choose "randomly" from a countable infinite set if by "randomly" you mean, with equal probability for each element in the set. This is easy to see because the probabilities could not add up to 1. However, if by "randomly" you mean according to some probability measure on the set then it's easy to construct such a measure. For example, define P(a_k) = (1/2)^k for k=1,2,...
I'm going to select a random positive integer with the St. Petersburg heuristic. I will flip a coin until I flip a head. At the time I flip the head, I will count the number of times I flipped the coin.
Are you saying that this creates ill-defined probabilities because the set of outcomes is countably infinite?
I'm going to select a random positive integer with the St. Petersburg heuristic.
I thought random in this context means that all outcomes have an equal chance of happening, but I could be wrong, and I don't think it matters to the discussion we were having. Sorry for using the word in the first place.
Quote:
Are you saying that this creates ill-defined probabilities because the set of outcomes is countably infinite?
No. I think there must be a way of rephrasing what PTB said without assuming that countable infinite sets exist. If pressed, I might try to come up with a way, although I'm not sure how interesting that would be.
I am saying that the partial outputs are a bad choice because they are countably infinite, and so one cannot choose at random from them.
This seems to be claiming that you cannot choose "at random" from a countably infinite collection of objects. My heuristic seems to do that.
Quote:
I thought random in this context means that all outcomes have an equal chance of happening, but I could be wrong, and I don't think it matters to the discussion we were having. Sorry for using the word in the first place.
No worries. I'm still trying to figure out what exactly you're saying. I'll note that the St. Petersburg paradox does not have equally likely outcomes, and since you brought it up I assumed that your framework allowed it.
Quote:
No. I think there must be a way of rephrasing what PTB said without assuming that countable infinite sets exist. If pressed, I might try to come up with a way, although I'm not sure how interesting that would be.
Which thing that he said? There are a lot of ideas floating around this thread.
You can't choose "randomly" from a countable infinite set if by "randomly" you mean, with equal probability for each element in the set. This is easy to see because the probabilities could not add up to 1. However, if by "randomly" you mean according to some probability measure on the set then it's easy to construct such a measure. For example, define P(a_k) = (1/2)^k for k=1,2,...
It means I was wrong to say that you cannot assign probabilities to the partial outputs because they are countably infinite.
Quote:
Originally Posted by Aaron W.
I'm still trying to figure out what exactly you're saying.
I'm saying that there is no way to obtain an infinite sequence over {H, T} as the output of a non-halting coin flip program.
I haven't explained why I think that matters, but it matters because it means that there is no way to choose a real number in the unit interval at random.
(I said random again, but I don't see how else to phrase it.)
I'm saying that there is no way to obtain an infinite sequence over {H, T} as the output of a non-halting coin flip program.
I haven't explained why I think that matters, but it matters because it means that there is no way to choose a real number in the unit interval at random.
(I said random again, but I don't see how else to phrase it.)
There is no probability measure on the unit interval reals whereby each real number has non zero probability. However you can put a probability measure on the unit interval, e.g. the uniform measure, where the probability of subintervals is non zero but the probability of any single real number is zero. In this case we talk about picking a real number at random according to such a probability measure even though the number we "pick" has zero probability of having been picked.
I never thought about it before, but you may be right and even though we do this theoretically in the math it may not be possible to actually do it in practice.
I'm saying that there is no way to obtain an infinite sequence over {H, T} as the output of a non-halting coin flip program.
In finite time? Sure.
Quote:
I haven't explained why I think that matters, but it matters because it means that there is no way to choose a real number in the unit interval at random.
(I said random again, but I don't see how else to phrase it.)
I agree that it's impossible in practice to pick a real number in the unit interval with uniform probability. I believe the amount of real numbers in the interval for which we have an explicit way of representing has measure zero.
This reminds me of this 2 color hat puzzle we discussed a few years ago. At the time I objected, pointing out that it's one thing using the Axiom of Choice to give you an indexed collection of arbitrary representative elements to talk about while it's something else to in practice get actual representative elements. The prisoners in the puzzle must put to work actual representative elements.
I think in the version we discussed it was wizards or magicians rather than prisoners and jason1990 insisted they would have that power. In the Wiki article below they appeal to help from an Oracle. I think that's also what you would need to get an actual random real from the unit interval via the uniform probability distribution.
In this variant, a countably infinite number of prisoners, each with an unknown and randomly assigned red or blue hat line up single file line. Each prisoner faces away from the beginning of the line, and each prisoner can see all the hats in front of him, and none of the hats behind. Starting from the beginning of the line, each prisoner must correctly identify the color of his hat or he is killed on the spot. As before, the prisoners have a chance to meet beforehand, but unlike before, once in line, no prisoner can hear what the other prisoners say. The question is, is there a way to ensure that only finitely many prisoners are killed?
Solution:
Spoiler:
The solution[edit]
If one accepts the axiom of choice, and assumes the prisoners each have the (unrealistic) ability to memorize an uncountably infinite amount of information and perform computations with uncountably infinite computational complexity, the answer is yes. In fact, even if we allow an uncountable number of different colors for the hats and an uncountable number of prisoners, the axiom of choice provides a solution that guarantees that only finitely many prisoners must die. The solution for the two color case is as follows, and the solution for the uncountably infinite color case is essentially the same:
The prisoners standing in line form a sequence of 0s and 1s, where 0 is taken to represent blue, and 1 is taken to represent red. Before they are put into the line, the prisoners define the following equivalence relation over all possible sequences that they might be put into: Two sequences are equivalent if they are identical after a finite number of entries. From this equivalence relation, the prisoners get a collection of equivalence classes. Assuming the axiom of choice, there exists a set of representative sequences -- one from each equivalence class. (Almost everywhere is impossible to compute, but the axiom of choice implies that some set of values exists, so we assume that the prisoners have access to an oracle.)
When they are put into their line, each prisoner can see which equivalence class the actual sequence of hats belongs to. (This assumes that each prisoner can perform an uncountably infinite number of comparisons to find a match, with each class comparison requiring a countably infinite number of individual hat-comparisons). They then proceed guessing their hat color as if they were in the representative sequence from the appropriate equivalence class. Because the actual sequence and the representative sequence are in the same equivalence class, their entries are the same after some finite number N of prisoners. All prisoners after these first N prisoners are saved.
Because the prisoners have no information about the color of their own hat and would make the same guess whichever color it has, each prisoner has a 50% chance of being killed. It may seem paradoxical that an infinite number of prisoners each have an even chance of being killed and yet it is certain that only a finite number are killed. However, there is no contradiction here, because this finite number can be arbitrarily large, and no probability can be assigned to any particular number being killed.
This is easiest to see for the case of zero prisoners being killed. This happens if and only if the actual sequence is one of the selected representative sequences. If the sequences of 0s and 1s are viewed as binary representations of a real number between 0 and 1, the representative sequences form a non-measurable set. (This set is similar to a Vitali set, the only difference being that equivalence classes are formed with respect to numbers with finite binary representations rather than all rational numbers.) Hence no probability can be assigned to the event of zero prisoners being killed. The argument is similar for other finite numbers of prisoners being killed, corresponding to a finite number of variations of each representative.
In the Wiki article below they appeal to help from an Oracle. I think that's also what you would need to get an actual random real from the unit interval via the uniform probability distribution.
An equivalence relation such that the probability of distinct elements being equal is zero is pretty cool, I'll admit.
I don't see how an oracle is going to get you from the non-halting program of coin flips to a function from the naturals to {H, T}, i.e. an actual real, which is what the hat problem appears to require.
Consider two such programs, and the proposition that they will always flip the same after a certain point. One interpretation is that this could happen, but probability of it happening is zero. A second is that it happening is unobservable, and it can only be observed not to happen. Both interpretations, I think, treat the programs at generating real numbers. My interpretation would be that the proposition does not make sense since, as you and Aaron appear to have agreed, these programs do not have outputs, only partial outputs, and the proposition concerns outputs.
P.S. Sorry if any of that spoils your spoiler, but I think there is little chance of that.
I don't see how an oracle is going to get you from the non-halting program of coin flips to a function from the naturals to {H, T}, i.e. an actual real, which is what the hat problem appears to require.
Not only do the prisoners need to get an actual real number but an uncountable number of them (in their binary form).
