See Indistinguishable’s post #9.
-FrL-
Glue 6 coins together into the shape of a die and roll it…
To put some numbers down: with the “Retry on TT” method, the average number of tosses until an answer is the sum over all naturals n of 1/4^n * 3/4 * (2n+2), which is the same as the sum of 6n/4^n, which is 8/3.
With the “Convert binary stream into ternary stream and extract first digit” method, the average number of tosses until an answer is 1 + (1/2 + 1/2^2 + 1/2^3 + …), which is 2. Furthermore, the amortized cost to get multiple outputs is ln(3)/ln(2) (i.e., if one keeps extracting further digits, the average number of tosses between digits approaches ln(3)/ln(2)). By Shannon’s theorem, this is optimal.
I don’t think this can be correct. 2 can’t be the average number of tosses, because 2 is the minimum number of tosses. 50% of the time it will take only 2 tosses, and 50% it will take at least 3 tosses to select a winner. I think this means the average has to be at least 2.5, if I remember my basic math properly.
Er, whoops. I misdid this. The actual answer here is 1 + (1 + 1/2 + 1/4 + …), which is 3. So this method is actually slightly less efficient, in the expected number of tosses sense, than the “Retry on TT” one for getting out the first digit. Its efficiency gains only kick in when one is extracting more than one digit.
ETA: Yeah, jackelope caught my error before I corrected it. The ln(3)/ln(2) amortized cost, though, is rock-solid.
Hm, I haven’t yet found a way to beat 8/3 tosses for one ternary digit, but I can match it, I guess. Toss the coin repeatedly until a tails comes up. Count the number of heads. If this is odd, then output A. If it’s even, then flip the coin again to decide between B and C. Each output has probability 1/3, and the expected number of tosses is 8/3. There’s no great reason to favor this over “Retry on TT”, but I like it anyway. Can anyone prove that 8/3 is the optimal for producing one ternary digit?
Also, I guess it isn’t really fair to say of “Retry on TT” that it tosses away information the way “Retry on TTT and HHH” would if you were trying to get a random number from 1-6 out of a coin, say, since there’s no distinction being lost. Still, it’s not the way to go if you want to produce multiple values. For that, the “Convert from binary to ternary” is still the best.
Assuming a fair die, would opposite faces (1-6, 2-5, and 3-4) be fairer than 1-4, 2-5, 3-6, or does it not matter?
all things absolutely equal? it doesn’t matter.
but, you’re right, it’s not a perfect world, and even a slight weight or center-of-gravity issue would change things up. I’d assume, if it were a center-of-gravity problem, opposite sides would be fairest. if the 1 side is super heavy and the 6 side is precisely oppositely lightweight, they would cancel each other out.
yes?
If the die is completely fair, then any three pairs of numbers will be fair. For any real die, it might make a difference, but not enough to notice without an unreasonably large number of tosses.
At Harvey Mudd College, there’s a campus legend about a student who tossed a coin to determine his major, saying that heads would mean engineering and tails would mean physics. The coin landed on its side in a crack in the sidewalk. He became a chemistry major.
So, in fact, you can do a three-way coin toss.
Stupid answer: use a die instead of a coin
Team A gets 1 and 2, Team B gets 3 and 4, Team C gets 5 and 6
Winning team (let’s say B) is #1
Team A gets 1, 2, and 3, Team C gets 4, 5, and 6
Reroll
If you’re going to use a die to select an ordering of three teams, one roll is precisely enough:
1: ABC
2: ACB
3: BAC
4: BCA
5: CAB
6: CBA
But this is all pretty irrelevant to the actual concerns of the OP.
If a coin had thickness equal to its diameter (i.e. a cylinder with h=d), would that work as a 3-sided coin (i.e. equal probability of landing on “edge” as landing on either side)?
Sounds feasible on the surface, but I’m sure it screws with the probability.
This is how it is (or was) used to break ties in high school football around here, the most famous example being the 1988 Permian Panthers and Abilene Cooper advancing to the playoffs. Midland Lee was the “odd man out.”
I think the probability would be 2/3 of landing on its “edge” and 1/6 for each of the “sides.” Think if it as a modified cube; the “edge” would take the place of four sides of the cube, and each “side” would be one.
An interesting question is what height to diameter ratio would get you three equal outcomes. Not sure how you’d calculate that, or if there is even a single answer. It might depend on how “bouncy” the cylinder is.
If the point that a coin lands on is chosen at random from all the points on its surface, and the probability that each part comes up is equal to the proportion of points that it contains, then you’ll have equal odds if the surface area of the non-faces is equal to the surface area of one face. That gives 2pirh = pir[sup]2[/sup], or h = r/2.
Well, I think it’s fair to say that die-rolling isn’t usually seen as picking a point at random from all those on the surface, since dice don’t usually land on a single point. I’m not sure what a better model would be exactly, though. Something like putting the tossed object in a random orientation and then allowing the object to “settle”.
To a first approximation, I was thinking that the probability might be proportional to the solid angle subtended by each side, but that assumes every angle is equally probable, and that isn’t obviously true.
Every time a die hits the surface it’s rolled on, it loses little of its energy. Once that energy falls below the energy it has when balanced on ts edge, its final side is determined. But it might on average lose different energy when it hits on its circular face than on its side face, if the final potential energy of the face and side states are different. Hence the comment about how “bouncy” the die is.
In short, I think the physics matters, and it’s not just a math question. But I don’t know this.