First, it's nVidia, with a capital V, so I'm already suspicious that you don't work there.
Secondly, your "homepage" looks was clearly thrown together in minutes, so I'm wondering if you're even a real person:
It worked! Congratulations on your first Django-powered page.
Of course, you haven't actually done any work yet. Here's what to do next:
* If you plan to use a database, edit the DATABASE_* settings in lexical/settings.py.
* Start your first app by running python lexical/manage.py startapp [appname].
You're seeing this message because you have DEBUG = True in your Django settings file and you haven't configured any URLs. Get to work!
"Generally, they make use of the fact that you can back up one spot by following the most recent loop..."
I contemplated something almost exactly like this, but it started getting complex and I thought I was looking for a known elegant solution! Anyway, it's an interesting problem and I'll let you know if I come up with anything.
The pdf argument doesn't do it for me because it's a theorem of measure theory that you can even use a probability distribution function to represent a measure. I guess it does make sense to me that there isn't a natural way to fairly pick one element from a countable set since countable sets are all the same cardnality. (One might expect that picking a random integer and having it be a multiple of 3 would be probability 1/3, but then the multiples of 3 are in 1-1 correspondence with the non-multiples of 3, so maybe it should be 1/2? etc)
Anyway, nice chatting with you:)
Gah, I typed out a response yesterday and lost it when another user rebooted me. The problem is as I expected it. Your comment about proven optimal times surprises me -- I'm pretty sure that there are problems that are Omega(n^2), but I'm not sure what's proven.
My algorithm is also O(2^n) on your graph, but I never claimed it was good:). I have a some inklings of a better algorithm that keeps track of the number of edges you've seen and the number you've taken, and jots that down by each door. It seems like some scheme such as this should allow you to identify 'dead' paths that loop back to places you aren't interested in. I'm not sure of the details though. I'm interested in hearing your better answer. Do you an algorithm that you believe to be optimal?
Apologies for the lack of spacing. So do most people put '(p)' (but with angle brackets) before each paragraph? And how do I escape out to draw greater than/less than anyway?
Well, you're right -- none of the variants listed here declare a random amount of money was placed in the envelope. So I think I have to agree with your assessment of the core issue - the problem seems to imply the envelope stuffer is going to apply some bounded method to pick a dollar amount. I was interjecting something from a previous encouner with the problem. Sorry:)
Regarding a proof of no uniform distribution over the reals & countable additivity: Additivity refers the standard property of pdfs that for disjoint sets A,B, P(A or B) = P(A)+P(B). Countable additivity means that for a countable collection of sets A_1, A_2,... you have P(union A_i) = sum P(A_i). A 'uniform distribution' should intuitively be translation invariant: P( [0,1) ) should equal P( [1, 2) ) should equal P( [2, 3) ), etc. But the union of these sets is the entire set of (nonnegative) reals. Since a normalized measure should have P( [0,oo) )=1, it's easy to see that P( [i,i+1) ) must be less than any epsilon, and thus zero. But a countable sum of zeros is 0, not 1. This proves there is no normalized, countably additive, translation invariant probability measure.
It's just not clear to me why a probability measure should satisfy this countably additivity condition. (Note: the task of picking a uniformly random natural number shares the essential features and is probably simpler to consider.)
I think you can generalize my previous answer to make sure you do better no matter what number you see. Pick any strictly decreasing function P from [0,oo) to [1,0). When you find dollar amount x, switch with probability P(x).
With three questions there are eight possible cases you could distinguish. Since you're only asking for the order of the gods (six possible permutations), it seems momentarily plausible. But then we remember that Random's answers don't tell us anything, so if (da,da,ja) maps to (False, Random, True), then (da,ja,ja) must also). Similarly, there must be two sets of answers that map to each possible permutation. But we don't have twelve possible outcomes from the questions. Parent is a troll. QED.
By 'problems' I meant objections to the argument advanced as paradoxical. And I agree it's a great puzzle! To answer your question, fix any dollar amount and switch only if you find less than that amount in the envelope.
The reason I don't think the lack of pdf is the crux is because I think the problem did imply a pdf - a uniform distribution over the reals ("a random amount of money"). It's not obvious to me that no such distribution exists -- can you prove it? without assuming countable additivity? (unless you can justify it) I'd love to see this proven.
It *is* clear to me that if such a distribution did exist, it would have infinite expectation, and that this is a sufficient property of a distribution to explain the paradox (any infinite expectation pdf has this issue). So I see this as the crux of the matter!
Well you'll have to tell me how fast you're running if you want to know the run-time.:) But seriously, are we just talking about a directed graph algorithm or do I need to make use of the planar embedding. Cuz if you're looking for me to think about geometry, I'm too lazy:). "small number of numbers" means that you're looking for constant space but I can encode additional constant space data in each node?
A more interesting problem is to generalize this to N people. Cake will get a little messy if you cut it a bunch of times, so let's say it's pudding. Come up with a system whereby N people can fairly divide up a batch of pudding - even if two or more of the people are colluding.
Second problem: Clearly you have to assume that there is a directed path to the exit from any room. With that assumption, you don't need to remember any numbers. Just put a tick next to a door before you go through it and in any room always choose to go through a door with a minimal number of ticks.
Anyone want to furnish the proof of correctness?
I thought about this previously I found there were several problems with the envelope paradox. The first, and least relevant is that people have utility functions. The first million dollars you win is worth much more than the next. So supposing that it's useful to maximize dollar amounts is not a good 'real world' assumption. But no there's need to make real world assumptions to resolve the paradox, so moving on...
The second problem was the lack of a distribution function / proper conditionalizing as explained in your link. However, this flaw was fixable by changing the problem slightly to use a real distribution (such that the paradox remained).
The more fundamental problem was that the expectation of such a distribution was infinite. Consider the following simple game:
Start with $1. Continue to flip a coin until it lands tails. Each time it lands heads triple your money.
This simple game exhibits the same paradox. No matter how much money you get on your first play, you can always increase your expectation by giving up your winnings and playing again.
To make the analogy obvious, suppose someone played this game twice and put the earings into two envelopes. You pick an evelope. After opening it, you'll always improve your expectation (infinitely) by switching, so you'd be willing to pay at least $1 to switch. But you knew that before picking an envelope, so why didn't you just pick the other one.
This is IMO the crux of the paradox - infinite expectation.
Slashdot Mirror
First, it's nVidia, with a capital V, so I'm already suspicious that you don't work there.
Secondly, your "homepage" looks was clearly thrown together in minutes, so I'm wondering if you're even a real person:
It worked!
Congratulations on your first Django-powered page.
Of course, you haven't actually done any work yet. Here's what to do next:
* If you plan to use a database, edit the DATABASE_* settings in lexical/settings.py.
* Start your first app by running python lexical/manage.py startapp [appname].
You're seeing this message because you have DEBUG = True in your Django settings file and you haven't configured any URLs. Get to work!
I contemplated something almost exactly like this, but it started getting complex and I thought I was looking for a known elegant solution! Anyway, it's an interesting problem and I'll let you know if I come up with anything.
The pdf argument doesn't do it for me because it's a theorem of measure theory that you can even use a probability distribution function to represent a measure. I guess it does make sense to me that there isn't a natural way to fairly pick one element from a countable set since countable sets are all the same cardnality. (One might expect that picking a random integer and having it be a multiple of 3 would be probability 1/3, but then the multiples of 3 are in 1-1 correspondence with the non-multiples of 3, so maybe it should be 1/2? etc) Anyway, nice chatting with you :)
My algorithm is also O(2^n) on your graph, but I never claimed it was good :). I have a some inklings of a better algorithm that keeps track of the number of edges you've seen and the number you've taken, and jots that down by each door. It seems like some scheme such as this should allow you to identify 'dead' paths that loop back to places you aren't interested in. I'm not sure of the details though. I'm interested in hearing your better answer. Do you an algorithm that you believe to be optimal?
Apologies for the lack of spacing. So do most people put '(p)' (but with angle brackets) before each paragraph? And how do I escape out to draw greater than/less than anyway?
Well, you're right -- none of the variants listed here declare a random amount of money was placed in the envelope. So I think I have to agree with your assessment of the core issue - the problem seems to imply the envelope stuffer is going to apply some bounded method to pick a dollar amount. I was interjecting something from a previous encouner with the problem. Sorry :)
Regarding a proof of no uniform distribution over the reals & countable additivity: Additivity refers the standard property of pdfs that for disjoint sets A,B, P(A or B) = P(A)+P(B). Countable additivity means that for a countable collection of sets A_1, A_2, ... you have P(union A_i) = sum P(A_i). A 'uniform distribution' should intuitively be translation invariant: P( [0,1) ) should equal P( [1, 2) ) should equal P( [2, 3) ), etc. But the union of these sets is the entire set of (nonnegative) reals. Since a normalized measure should have P( [0,oo) )=1, it's easy to see that P( [i,i+1) ) must be less than any epsilon, and thus zero. But a countable sum of zeros is 0, not 1. This proves there is no normalized, countably additive, translation invariant probability measure.
It's just not clear to me why a probability measure should satisfy this countably additivity condition. (Note: the task of picking a uniformly random natural number shares the essential features and is probably simpler to consider.)
I think you can generalize my previous answer to make sure you do better no matter what number you see. Pick any strictly decreasing function P from [0,oo) to [1,0). When you find dollar amount x, switch with probability P(x).
With three questions there are eight possible cases you could distinguish. Since you're only asking for the order of the gods (six possible permutations), it seems momentarily plausible. But then we remember that Random's answers don't tell us anything, so if (da,da,ja) maps to (False, Random, True), then (da,ja,ja) must also). Similarly, there must be two sets of answers that map to each possible permutation. But we don't have twelve possible outcomes from the questions. Parent is a troll. QED.
By 'problems' I meant objections to the argument advanced as paradoxical. And I agree it's a great puzzle! To answer your question, fix any dollar amount and switch only if you find less than that amount in the envelope. The reason I don't think the lack of pdf is the crux is because I think the problem did imply a pdf - a uniform distribution over the reals ("a random amount of money"). It's not obvious to me that no such distribution exists -- can you prove it? without assuming countable additivity? (unless you can justify it) I'd love to see this proven. It *is* clear to me that if such a distribution did exist, it would have infinite expectation, and that this is a sufficient property of a distribution to explain the paradox (any infinite expectation pdf has this issue). So I see this as the crux of the matter!
Well you'll have to tell me how fast you're running if you want to know the run-time. :) But seriously, are we just talking about a directed graph algorithm or do I need to make use of the planar embedding. Cuz if you're looking for me to think about geometry, I'm too lazy :). "small number of numbers" means that you're looking for constant space but I can encode additional constant space data in each node?
A more interesting problem is to generalize this to N people. Cake will get a little messy if you cut it a bunch of times, so let's say it's pudding. Come up with a system whereby N people can fairly divide up a batch of pudding - even if two or more of the people are colluding.
Second problem: Clearly you have to assume that there is a directed path to the exit from any room. With that assumption, you don't need to remember any numbers. Just put a tick next to a door before you go through it and in any room always choose to go through a door with a minimal number of ticks. Anyone want to furnish the proof of correctness?
It must be 1/3
I thought about this previously I found there were several problems with the envelope paradox. The first, and least relevant is that people have utility functions. The first million dollars you win is worth much more than the next. So supposing that it's useful to maximize dollar amounts is not a good 'real world' assumption. But no there's need to make real world assumptions to resolve the paradox, so moving on...
The second problem was the lack of a distribution function / proper conditionalizing as explained in your link. However, this flaw was fixable by changing the problem slightly to use a real distribution (such that the paradox remained).
The more fundamental problem was that the expectation of such a distribution was infinite. Consider the following simple game:
Start with $1. Continue to flip a coin until it lands tails. Each time it lands heads triple your money.
This simple game exhibits the same paradox. No matter how much money you get on your first play, you can always increase your expectation by giving up your winnings and playing again.
To make the analogy obvious, suppose someone played this game twice and put the earings into two envelopes. You pick an evelope. After opening it, you'll always improve your expectation (infinitely) by switching, so you'd be willing to pay at least $1 to switch. But you knew that before picking an envelope, so why didn't you just pick the other one.
This is IMO the crux of the paradox - infinite expectation.