Can a bounded agent actually do this? I’m not entirely sure.
First write 1 on a piece of paper. Then start flipping coins. For every head, write a 0 after the 1. If you run out of space on the paper, ask Omega for more. When you get a tail, stop and hand the pieces of paper to Omega. This has expected value of 1⁄2 1 + 1⁄4 10 + 1⁄8 * 100 + … which is infinite.
How does that relate to the claim in http://en.wikipedia.org/wiki/Turing_machine#Concurrency that “there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape”?
I think my procedure does not satisfy the definition of “always-halting” used in that theorem (since it doesn’t halt if you keep getting heads) even though it does halt with probability 1.
That’s probably the answer, as your solution seems solid to me.
That still doesn’t change my main point: if we posit that certain infinite expectations are better than others (St Petersburg + $1 being better that St Petersburg), you still benefit from choosing your distribution as best you can.
Can you give a mathematical definition of how to compare two infinite/divergent expectations and conclude which one is better? If you can’t, then it might be that such a notion is incoherent, and it wouldn’t make sense to posit it as an assumption. (My understanding is that people have previously assumed that it’s impossible to compare such expectations. See http://singularity.org/files/Convergence-EU.pdf for example.)
Not all infinite expectations can be compared (I believe) but there’s lots of reasonable ways that one can say that one is better than another. I’ve been working on this at the FHI, but let it slide as other things became more important.
One easy comparison device: if X and Y are random variables, you can often calculate the mean of X-Y using the Cauchy principal value (http://en.wikipedia.org/wiki/Cauchy_principal_value). If this is positive, then Y is better than X.
This gives a partial ordering on the space of distributions, so one can always climb higher within this partial ordering.
Assuming you want to eventually incorporate the idea of comparing infinite/divergent expectations into decision theory, how do you propose to choose between choices that can’t be compared with each other?
Random variables form a vector space, since X+Y and rX are both defined. Let V be this whole vector space, and let’s define a subspace W of comparable random variables. ie if X and Y are in W, then either X is better than Y, worse, or they’re equivalent. This can include many random variables with infinite or undefined means (got a bunch of ways of comparing them).
Then we simply need to select a complementary subspace W^perp in V, and claim that all random variables on it are equally worthwhile. This can be either arbitrary, or we can use other principles (there are ways of showing that even if we can’t say that Z is better than X, we can still find a Y that is worse than X but incomparable to Y).
Let V be this whole vector space, and let’s define a subspace W of comparable random variables.
What exactly are you doing in this step? Are you claiming that there is a unique maximal set of random variables which are all comparable, and it forms a subspace? Or are you taking an arbitrary set of mutually comparable random variables, and then picking a subspace containing it?
EDIT: the concept has become somewhat complicated to define, and needs a rethink before fomalisation, so I’m reworking this post.
The key assumption I’ll use: if X and Y are both equivalent with 0 utility, then they are equivalent with each other and with rX for all real r.
Redefine W to the space of all utility-valued random variables that are equivalent to zero utility, according to our various rules. If W is not a vector space, I extend to be so by taking any linear combinations. Let C be the line of constant-valued random variables.
Then a total order requires:
A space W’, complementary to W and C, such that all elements of W’ are defined to be equivalent with zero utility. W’ is defined up to W, and again we can extend it by linear combinations. Let U= W+W’+C. Thus V/U corresponds to random variables with infinite utility (positive or negative). Because of what we’ve done, no two elements of V/U can have the same value (if so, their difference would be in W+W’), and no two elements can differ by a real number. So a total order on V/U unambiguously gives one on V. And the total order on V/U is a bit peculiar, and non-archimedean: if X>Y>0, the X>rY for all real r. Such an order can be given (non-uniquely) by an ordered basis (or a complete flag) ).
Again, the key assumption is that if two things are equivalent to zero, they are equivalent to each other—this tends to generate subspaces.
It’s mainly the subspace part of your statement that I’m concerned about. I see no reason why the space of totally ordered random variables should be closed under taking linear combinations.
Because that’s a requirement of the approach—once it no longer holds true, we no longer increase W.
Maybe this is a better way of phrasing it: W is the space of all utility-valued random variables that have the same value as some constant (by whatever means we establish that).
Then I get linear closure by fiat or assumption: if X=c and Y=d, then X+rY=c+rd, for c, d and r constants (and overloading the = sign to mean “<= and >=”).
But my previous post was slightly incorrect—it didn’t consider infinite expectations. I will rework that a bit.
First write 1 on a piece of paper. Then start flipping coins. For every head, write a 0 after the 1. If you run out of space on the paper, ask Omega for more. When you get a tail, stop and hand the pieces of paper to Omega. This has expected value of 1⁄2 1 + 1⁄4 10 + 1⁄8 * 100 + … which is infinite.
How does that relate to the claim in http://en.wikipedia.org/wiki/Turing_machine#Concurrency that “there is a bound on the size of integer that can be computed by an always-halting nondeterministic Turing machine starting on a blank tape”?
I think my procedure does not satisfy the definition of “always-halting” used in that theorem (since it doesn’t halt if you keep getting heads) even though it does halt with probability 1.
That’s probably the answer, as your solution seems solid to me.
That still doesn’t change my main point: if we posit that certain infinite expectations are better than others (St Petersburg + $1 being better that St Petersburg), you still benefit from choosing your distribution as best you can.
Can you give a mathematical definition of how to compare two infinite/divergent expectations and conclude which one is better? If you can’t, then it might be that such a notion is incoherent, and it wouldn’t make sense to posit it as an assumption. (My understanding is that people have previously assumed that it’s impossible to compare such expectations. See http://singularity.org/files/Convergence-EU.pdf for example.)
Not all infinite expectations can be compared (I believe) but there’s lots of reasonable ways that one can say that one is better than another. I’ve been working on this at the FHI, but let it slide as other things became more important.
One easy comparison device: if X and Y are random variables, you can often calculate the mean of X-Y using the Cauchy principal value (http://en.wikipedia.org/wiki/Cauchy_principal_value). If this is positive, then Y is better than X.
This gives a partial ordering on the space of distributions, so one can always climb higher within this partial ordering.
Assuming you want to eventually incorporate the idea of comparing infinite/divergent expectations into decision theory, how do you propose to choose between choices that can’t be compared with each other?
Random variables form a vector space, since X+Y and rX are both defined. Let V be this whole vector space, and let’s define a subspace W of comparable random variables. ie if X and Y are in W, then either X is better than Y, worse, or they’re equivalent. This can include many random variables with infinite or undefined means (got a bunch of ways of comparing them).
Then we simply need to select a complementary subspace W^perp in V, and claim that all random variables on it are equally worthwhile. This can be either arbitrary, or we can use other principles (there are ways of showing that even if we can’t say that Z is better than X, we can still find a Y that is worse than X but incomparable to Y).
What exactly are you doing in this step? Are you claiming that there is a unique maximal set of random variables which are all comparable, and it forms a subspace? Or are you taking an arbitrary set of mutually comparable random variables, and then picking a subspace containing it?
EDIT: the concept has become somewhat complicated to define, and needs a rethink before fomalisation, so I’m reworking this post.
The key assumption I’ll use: if X and Y are both equivalent with 0 utility, then they are equivalent with each other and with rX for all real r.
Redefine W to the space of all utility-valued random variables that are equivalent to zero utility, according to our various rules. If W is not a vector space, I extend to be so by taking any linear combinations. Let C be the line of constant-valued random variables.
Then a total order requires:
A space W’, complementary to W and C, such that all elements of W’ are defined to be equivalent with zero utility. W’ is defined up to W, and again we can extend it by linear combinations. Let U= W+W’+C. Thus V/U corresponds to random variables with infinite utility (positive or negative). Because of what we’ve done, no two elements of V/U can have the same value (if so, their difference would be in W+W’), and no two elements can differ by a real number. So a total order on V/U unambiguously gives one on V. And the total order on V/U is a bit peculiar, and non-archimedean: if X>Y>0, the X>rY for all real r. Such an order can be given (non-uniquely) by an ordered basis (or a complete flag) ).
Again, the key assumption is that if two things are equivalent to zero, they are equivalent to each other—this tends to generate subspaces.
It’s mainly the subspace part of your statement that I’m concerned about. I see no reason why the space of totally ordered random variables should be closed under taking linear combinations.
Because that’s a requirement of the approach—once it no longer holds true, we no longer increase W.
Maybe this is a better way of phrasing it: W is the space of all utility-valued random variables that have the same value as some constant (by whatever means we establish that).
Then I get linear closure by fiat or assumption: if X=c and Y=d, then X+rY=c+rd, for c, d and r constants (and overloading the = sign to mean “<= and >=”).
But my previous post was slightly incorrect—it didn’t consider infinite expectations. I will rework that a bit.
I would assume the former, using Zorn’s lemma. That doesn’t yield uniqueness, though.