Log -- David Chess

Thursday, June 4, 2009

Have I mentioned I have the best readers? *8)

On the math problem from last time, a reader writes:

C - S + S((S-1)/S)^C

Which is lovely, and I suspect also correct.

Think about it first in the case where C=S. Imagine that all of the cards are sitting in the slots on the table, one to a slot. The number of not-on-the-felt cards here is zero, of course. If we want to raise that number to one, we take a card from some slot that has exactly one card in it, and put it into another occupied slot; that will leave one slot empty. If we then want to raise it to two, we have to move another card that's all by itself in a slot (moving the card that's already on some other card will either leave the count at one or put it back to zero). If we do move another lone card to a still-occupied slot, there will now be two not-on-the-felt cards, and two empty slots.

And in general every time we want to raise the number of not-on-the-felt cards, we also have to raise the number of empty slots by the same amount. So the number of not-on-the-felt cards is the number of empty slots. And what is the expected number of empty slots? Well that we can figure out!

The probability that a given slot will be empty is just the probability that every card goes into some other slot. The probability that any particular card goes into some other slot is (S-1)/S (if there are ten slots, the probability that the next card dealt will go into some slot other than slot five, say, is 9/10). Since the probabilities here are independant, the probability that all of the cards will go into other slots, leaving this slot empty, is ((S-1)/S)^C (S minus one over S, to the C).

Since there are S slots, the expected number of empty slots is exactly S times that probability, or S((S-1)/S)^C. (I worry that I'm overlooking some assumption here, but if I am it doesn't seem to be an important one.)

Now that was all for the C = S case. I haven't quite convinced myself that the solution is right for the C ≠ S case, but here's the argument: If C is larger than S (you have more cards than slots), then at least (C-S) cards must be in non-empty slots, so you can imagine yourself starting with at least one card in each slot and the rest wherever you like, and then continue the argument above. If C is smaller than S (fewer cards than slots), at least (S-C) slots will always be empty, so imagine starting with every card in a slot by itself, with (S-C) already empty, and again continue the argument above.

Yeah, I think that works. *8)

So thank you very extremely, treasured reader! I'll have to think about whether I can actually use that in the actual larger problem that I'm actually working on, even.

(By the by, I fixed a typo in the previous entry, where I had a "C to the power S" that should have been "S to the power C".)

Oh, and note that the Kind Reader's solution does have, in the C = S case, S^S in the denominator, as prophesied: in that form it's S((S-1)^S) over S^S. And if we evaluate S((S-1)^S) for our test cases, it turns out to be zero for 1, 2 for 2, and 24 for 3, also as expected! The exact solutions for 12 and 24 turn out to be closer to 4.224 and 8.642 than the 4.225 and 8.644 that I got from simulation; I wonder if I have a bug somewhere, hm....

So that has made me smile!

"At one time," the turtle said in didactic tones, "a solar-powered flashlight was considered a sort of oxymoron, an obviously-useless gadget: a light that works only in sunlight.
"But in reality a solar-powered flashlight charges its batteries in the sun, and later uses those batteries to provide light in the dark, and is thereby useful. Now that solar power is no longer an oddity, we have stopped basing jokes around misunderstanding it.
"One could argue that the useful device is not actually a solar-powered flashlight, but instead a battery-powered flashlight coupled to a solar-powered battery charger. But the result of packing together a solar-powered battery charger and a battery-powered flashlight simply is in fact a solar-powered flashlight. There is no alterntive."

I thought of that this morning on the drive to work for some reason. I don't know why it ended up being a turtle saying it. How would a turtle hold a flashlight (solar-powered or not)? In his litle jaws, perhaps. Or maybe this turtle has opposable thumbs.

Then we could talk about how much sense it makes to talk about a turtle with opposable thumbs. Would that still be a turtle? Why or why not? Is not having opposable thumbs more or less central to being a turtle than is, say, being unable to speak? Or not understanding the concept of solar power?

This is really good.

Tuesday, June 2, 2009

So imagine you have a deck of C cards, and on the felt in front of you there are S card-shaped slots or spaces drawn. Now you deal each of the C cards, at random, into the S slots; you place each card into a randomly-chosen slot, paying no attention to whether or not there is already a card in the slot (if there is, you just put the new card on top of it). So the first card that you put down always goes into an empty slot, but the second and the rest of the C cards can go into either an empty slot or one that already has one or more cards in it.

The question is: how many cards are (on average) on top of another card, rather than directly on the felt?

Express your answer in terms of C and S, natch.

If you're in a hurry, you may consider only the cases where C = S (or where c==s, for you programmer types).

In the trivial case where C = S = 1, the answer is zero (the one card will always be sitting there on the felt in the one slot). For C = S = 2, we can look at all four possible cases and determine that the answer is 0.5; half the time the cards will be in two different slots (so the answer is zero) and half the time they'll be in the same slot (so one card will not be on the felt, and half of one is 0.5).

We can easily solve ("solve") this problem in specific small cases by writing a little Perl script or whatever that deals cards at random and counts. For instance for C = S = 12 the answer is around 4.225, and for C = S = 24, it seems to be around 8.644. (Running the program for C = S = 3 suggests that if we were willing to think through all the possible cases there, we'd find the answer was 8/9.)

But what is, y'know, the answer? The closed-form solution? It's gotta be a rational number, and the bottom of the fraction is the number of possible ways to deal the cards, C to the power of S (or when C = S, C to the power C). The top of the fraction is, in all those possible ways of dealing the cards, the total number of cards (just counting up after laying down each deal) that aren't directly on the felt. But that latter number I don't have any clever clue on how to figure out in closed form. For 1, 2, and 3 the numbers are 0, 2, and probably 24.

We could write another program that would exhaustively go through all the cases, and it would be able to tell us the exact number for 4 and 5 and 6; even at 6 there are less than fifty thousand cases, so it wouldn't take too long. Seven to the seventh is getting up toward a million, ten to the tenth is of course ten to the tenth, and for C = S = 24, we probably wouldn't be willing to wait for the answer.

But if someone could write down a nice simple formula... *8)

(That problem came from thinking about a problem at work; but the work problem has enough extra parts that I'm pretty sure no closed-form answer is going to present itself, and there are far too many cases for a program to look at each one, so I am writing the simulation program.)

And here is a picture of Spennix fishing!

Doesn't that look idyllic? That's part of a whole set of recentish Spennix adventures that you can catch up with over on the secret Second Life weblog.

In other news, the little daughter is in a Distant Foreign Land, but we talked to her over "Skype" (funny names these kids come up with, eh?) on the computer, and we could actually see each other, and it was also free.

Pretty weird.

I'm glad I'm not an international long-distance company right now.

("Hm, so I can pay through the nose per minute for a voice-only phone call, or I can get voice and video free over the internet; hmmm, decisions decisions...")

And I'm sure there's other stuff going on *8) but it's getting late and distractions threaten to pull me away from the ol' weblog here and if I wanna get this posted tonight (and I do!), I'd better. So off we go!

Sleep well.

	log (2009/05/29 to 2009/06/04)
older log newer log reply about archive search random home words site news talking place login What's for lunch?	Thursday, June 4, 2009 Have I mentioned I have the best readers? 8) On the math problem from last time, a reader writes: C - S + S((S-1)/S)^C Which is lovely, and I suspect also correct. Think about it first in the case where C=S. Imagine that all of the cards are sitting in the slots on the table, one to a slot. The number of not-on-the-felt cards here is zero, of course. If we want to raise that number to one, we take a card from some slot that has exactly one card in it, and put it into another occupied slot; that will leave one slot empty. If we then want to raise it to two, we have to move another card that's all by itself in a slot (moving the card that's already on some other card will either leave the count at one or put it back to zero). If we do move another lone card to a still-occupied slot, there will now be two not-on-the-felt cards, and two empty slots. And in general every time we want to raise the number of not-on-the-felt cards, we also have to raise the number of empty slots by the same amount. So the number of not-on-the-felt cards is the number of empty slots. And what is the expected number of empty slots? Well that* we can figure out! The probability that a given slot will be empty is just the probability that every card goes into some other slot. The probability that any particular card goes into some other slot is (S-1)/S (if there are ten slots, the probability that the next card dealt will go into some slot other than slot five, say, is 9/10). Since the probabilities here are independant, the probability that all of the cards will go into other slots, leaving this slot empty, is ((S-1)/S)^C (S minus one over S, to the C). Since there are S slots, the expected number of empty slots is exactly S times that probability, or S((S-1)/S)^C. (I worry that I'm overlooking some assumption here, but if I am it doesn't seem to be an important one.) Now that was all for the C = S case. I haven't quite convinced myself that the solution is right for the C ≠ S case, but here's the argument: If C is larger than S (you have more cards than slots), then at least (C-S) cards must be in non-empty slots, so you can imagine yourself starting with at least one card in each slot and the rest wherever you like, and then continue the argument above. If C is smaller than S (fewer cards than slots), at least (S-C) slots will always be empty, so imagine starting with every card in a slot by itself, with (S-C) already empty, and again continue the argument above. Yeah, I think that works. 8) So thank you very extremely, treasured reader! I'll have to think about whether I can actually use that in the actual larger problem that I'm actually working on, even. (By the by, I fixed a typo in the previous entry, where I had a "C to the power S" that should have been "S to the power C".) Oh, and note that the Kind Reader's solution does have, in the C = S case, S^S in the denominator, as prophesied: in that form it's S((S-1)^S) over S^S. And if we evaluate S((S-1)^S) for our test cases, it turns out to be zero for 1, 2 for 2, and 24 for 3, also as expected! The exact solutions for 12 and 24 turn out to be closer to 4.224 and 8.642 than the 4.225 and 8.644 that I got from simulation; I wonder if I have a bug somewhere, hm.... So that has made me smile! "At one time," the turtle said in didactic tones, "a solar-powered flashlight was considered a sort of oxymoron, an obviously-useless gadget: a light that works only in sunlight. "But in reality a solar-powered flashlight charges its batteries in the sun, and later uses those batteries to provide light in the dark, and is thereby useful. Now that solar power is no longer an oddity, we have stopped basing jokes around misunderstanding it. "One could argue that the useful device is not actually a solar-powered flashlight, but instead a battery-powered flashlight coupled to a solar-powered battery charger. But the result of packing together a solar-powered battery charger and a battery-powered flashlight simply is in fact a solar-powered flashlight. There is no alterntive." I thought of that this morning on the drive to work for some reason. I don't know why it ended up being a turtle saying it. How would a turtle hold a flashlight (solar-powered or not)? In his litle jaws, perhaps. Or maybe this turtle has opposable thumbs. Then we could talk about how much sense it makes to talk about a turtle with opposable thumbs. Would that still be a turtle? Why or why not? Is not having opposable thumbs more or less central to being a turtle than is, say, being unable to speak? Or not understanding the concept of solar power? This is really good. Tuesday, June 2, 2009 So imagine you have a deck of C cards, and on the felt in front of you there are S card-shaped slots or spaces drawn. Now you deal each of the C cards, at random, into the S slots; you place each card into a randomly-chosen slot, paying no attention to whether or not there is already a card in the slot (if there is, you just put the new card on top of it). So the first card that you put down always goes into an empty slot, but the second and the rest of the C cards can go into either an empty slot or one that already has one or more cards in it. The question is: how many cards are (on average) on top of another card, rather than directly on the felt? Express your answer in terms of C and S, natch. If you're in a hurry, you may consider only the cases where C = S (or where c==s, for you programmer types). In the trivial case where C = S = 1, the answer is zero (the one card will always be sitting there on the felt in the one slot). For C = S = 2, we can look at all four possible cases and determine that the answer is 0.5; half the time the cards will be in two different slots (so the answer is zero) and half the time they'll be in the same slot (so one card will not be on the felt, and half of one is 0.5). We can easily solve ("solve") this problem in specific small cases by writing a little Perl script or whatever that deals cards at random and counts. For instance for C = S = 12 the answer is around 4.225, and for C = S = 24, it seems to be around 8.644. (Running the program for C = S = 3 suggests that if we were willing to think through all the possible cases there, we'd find the answer was 8/9.) But what is, y'know, the answer? The closed-form solution? It's gotta be a rational number, and the bottom of the fraction is the number of possible ways to deal the cards, C to the power of S (or when C = S, C to the power C). The top of the fraction is, in all those possible ways of dealing the cards, the total number of cards (just counting up after laying down each deal) that aren't directly on the felt. But that latter number I don't have any clever clue on how to figure out in closed form. For 1, 2, and 3 the numbers are 0, 2, and probably 24. We could write another program that would exhaustively go through all the cases, and it would be able to tell us the exact number for 4 and 5 and 6; even at 6 there are less than fifty thousand cases, so it wouldn't take too long. Seven to the seventh is getting up toward a million, ten to the tenth is of course ten to the tenth, and for C = S = 24, we probably wouldn't be willing to wait for the answer. But if someone could write down a nice simple formula... 8) (That problem came from thinking about a problem at work; but the work problem has enough extra parts that I'm pretty sure no closed-form answer is going to present itself, and there are far too many cases for a program to look at each one, so I am writing the simulation program.) And here is a picture of Spennix fishing! Doesn't that look idyllic? That's part of a whole set of recentish Spennix adventures that you can catch up with over on the secret Second Life weblog. In other news, the little daughter is in a Distant Foreign Land, but we talked to her over "Skype" (funny names these kids come up with, eh?) on the computer, and we could actually see each other, and it was also free. Pretty weird. I'm glad I'm not an international long-distance company right now. ("Hm, so I can pay through the nose per minute for a voice-only phone call, or I can get voice and video free over the internet; hmmm, decisions decisions...") And I'm sure there's other stuff going on *8) but it's getting late and distractions threaten to pull me away from the ol' weblog here and if I wanna get this posted tonight (and I do!), I'd better. So off we go! Sleep well.
top	earlier entries