Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Tyrrell_McAllister comments on The Absent-Minded Driver - Less Wrong

28 Post author: Wei_Dai 16 September 2009 12:51AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (141)

You are viewing a single comment's thread. Show more comments above.

Comment author: Tyrrell_McAllister 16 September 2009 10:01:26PM 1 point [-]

It's probably better not to think of this as a randomized algorithm. Here is a simpler example of what I mean.

Suppose you have two urns in front of you. One urn is full of N white marbles, and the other urn is empty. Your task is to take a marble out of the first urn, paint it either red or blue, place it in the second urn, and then repeat this process until the first urn is empty. Moreover, when you are done, something very close to two-thirds of the marbles in the second urn must be red.

The catch, of course, is that you have very poor short-term memory, so you can never remember how many marbles you've painted or what colors you've painted them.

The "randomized algorithm" solution would be to use a pseudo-random number generator to produce a number x between 0 and 1 for each marble, and to paint that marble red if and only if x < 2/3.

But there is a non-random way to think of that procedure. Suppose instead that, before you start painting your N marbles, you set out a box of N poker chips, of which you know (that is, have reason to be highly confident) that very nearly two-thirds are red. You then proceed to paint marbles according to the following algorithm. After taking a marble in hand, you select a poker chip non-randomly from the box, and then paint the marble the same color as that poker chip.

This is a non-random algorithm that you can use with confidence, but which requires no memory. And, as I see it, the method with the pseudo-random number generator amounts to the same thing. By deciding to use the generator, you are determining N numbers: the next N numbers that the generator will produce. Moreover, if you know how the generator is constructed, you know (that is, have reason to be highly confident) that very nearly two-thirds of those numbers will be less than 2/3. To my mind, this is functionally identical to the poker chip procedure.

Comment author: SilasBarta 16 September 2009 10:15:53PM 3 points [-]

Very clever! It is indeed true that if you forget all previous marble paintings, the best way to ensure that 2/3 get painted one color is to paint it that color with p = 2/3.

And interestingly, I can think of several examples of my own life when I've been in that situation. For example, when I'm playing Alpha Centauri, I want to make sure I have a good mix of artillery, infantry, and speeders, but it's tedious to keep track of how many I have of each, so I just pick in a roughly random way, but biased toward those that I want in higher proportions.

I'm going to see if I can map the urn/marble-painting problem back onto the absent-minded driver problem.

Comment author: JGWeissman 16 September 2009 10:21:34PM 4 points [-]

This is a non-random algorithm that you can use with confidence, but which requires no memory.

You mean it does not require memory in your brain, because you implemented your memory with the poker chips. It is quite convenient they were available.

Comment author: Tyrrell_McAllister 16 September 2009 10:25:06PM *  5 points [-]

My point is that it's no more convenient than having the pseudo-random number generator available. I maintain that the generator is implementing your memory in functionally the same sense. For example, you are effectively guaranteed not to get the same number twice, just as you are effectively guaranteed not to get the same poker chip twice.

ETA: After all, something in the generator must be keeping track of the passage of the marbles for you. Otherwise the generator would keep producing the same number over and over.

Comment author: DonGeddis 16 September 2009 11:57:33PM 4 points [-]

Rather than using a PRNG (which, as you say, requires memory), you could use a source of actual randomness (e.g. quantum decay). Then you don't really have extra memory with the randomized algorithm, do you?

Comment author: JGWeissman 17 September 2009 12:24:31AM 2 points [-]

I thought of this as well, but it does not really matter because it is the ability to produce the different output in each case event that gives part of the functionality of memory, that is, the ability to distinguish between events. Granted, this is not as effective as deterministically understood memory, where you know in advance which output you get at each event. Essentially, it is memory with the drawback that you don't understand how it works to the extent that you are uncertain how it correlates with what you wanted to remember.

Comment author: gwern 11 August 2010 01:51:07PM 0 points [-]

After all, something in the generator must be keeping track of the passage of the marbles for you. Otherwise the generator would keep producing the same number over and over.

Randomness 'degenerates' (perhaps by action of a malicious daemon) into non-randomness, and so it can do better and no worse than a non-random approach?

(If the environments and agents are identical down to the source of randomness, then the agent defaults to a pure strategy; but with 'genuine' randomness, random sources that are different between instances of the agent, the agent can actually implement the better mixed strategy?)

Comment author: Tyrrell_McAllister 12 August 2010 05:45:51AM *  1 point [-]

I'm having trouble parsing your questions. You have some sentences that end in question marks. Are you asking whether I agree with those sentences? I'm having trouble understanding the assertions made by those sentences, so I can't tell whether I agree with them (if that was what you were asking).

The claim that I was making could be summed up as follows. I described an agent using a PRNG to solve a problem involving painting marbles. The usual way to view such a solution is as

deterministic amnesiac agent PLUS randomness.

My suggestion was instead to view the solution as

deterministic amnesiac agent

PLUS

a particular kind of especially limited memory

PLUS

an algorithm that takes the contents of that memory as input and produces an output that is almost guaranteed to have a certain property.

The especially limited memory is the part of the PRNG that remembers what the next seed should be. If there weren't some kind of memory involved in the PRNG's operation, the PRNG would keep using the same seed over and over again, producing the same "random" number again and again.

The algorithm is the algorithm that the PRNG uses to turn the first seed into a sequence of pseudo-random numbers.

The certain property of that sequence is the property of having two-thirds of its terms being less than 2/3.

Comment author: gwern 12 August 2010 06:20:48AM 0 points [-]

OK, that's clearer. And different from what I thought you were saying.

Comment author: JGWeissman 16 September 2009 10:41:36PM 0 points [-]

I maintain that the generator is implementing your memory in functionally the same sense.

That is fair enough, though the reason I find scenario at all interesting is that it illustrates the utility of a random strategy under certain conditions.

Comment author: Tyrrell_McAllister 17 September 2009 04:55:57PM *  0 points [-]

For me, finding an equivalent nonrandom strategy helps to dispel confusion.

I like your characterization above that the PRNG is "memory with the drawback that you don't understand how it works to the extent that you are uncertain how it correlates with what you wanted to remember." Another way to say it is that the PRNG gives you exactly what you need with near-certainty, while normal memory gives you extra information that happens to be useless for this problem.

What is "random" about the PRNG (the exact sequence of numbers) is extra stuff that you happen not to need. What you need from the PRNG (N numbers, of which two-thirds are less than 2/3) is not random but a near-certainty. So, although you're using a so-called pseudo-random number generator, you're really using an aspect of it that's not random in any significant sense. For this reason, I don't think that the PRNG algorithm should be called "random", any more than is the poker chip algorithm.

Comment author: Luke_A_Somers 06 June 2012 01:41:12PM 2 points [-]

Take 3 marbles out of the urn. Paint one of them blue, and then the other two red. Put all three in the second urn. Repeat

Yeah, yeah - white marbles are half-medusas, so if you can see more than one you die, or something.

Comment author: Tyrrell_McAllister 06 June 2012 02:44:25PM 0 points [-]

Taking more than one marble out of the urn at a time violates the task description. Don't fight the hypothetical!

Comment author: Luke_A_Somers 07 June 2012 03:03:58PM 1 point [-]

... That's what the second paragraph is for...

Comment author: christopherj 04 April 2014 05:43:22PM *  1 point [-]

If you're allowed to use external memory, why not just write down how many you painted of each color? Note that memory is different from a random number generator; for example, a random number generator can be used (imperfectly) to coordinate with a group of people with no communication, whereas memory would require communication but could give perfect results.

Comment author: Tyrrell_McAllister 05 April 2014 04:03:55AM 0 points [-]

Have you read this comment of mine from another branch of this conversation?