Love this problem. I studied it years ago. I didn't come up with the solution on my own, but I learned a lot from looking at the answer. It's wonderfully simple and ingenious.
So in practice what we will do is write the decimal expansion of α in binary. Then we will construct a new number, term by term of its binary decimal expansion by flipping a coin, say heads is 1 and tails is zero. We keep flipping the coin until the nth toss where the nth digit of our constructed number differs from the nth digit of α. From there we can tell if our number is greater or lesser than α. This can only be infinite if our coin flips match up with α exactly which is probability zero, so we can ignore that case
Great Video, the connection to and explanation of Michael Penn's solution in your picture proof was especially nice to see how different solutions could basically describe more or less the same thing. Just a question, you described alpha in Michael Penn's solution as in binary, wasnt the representation of the U in your solution also basically in binary?
Thanks so much! Yes, both are in binary: in my main solution I never had to refer to the binary expansion of alpha because it was baked into my comparisons of alpha less than or greater than U. You could equally well describe that condition in terms of comparing the binary decomposition of U (the C_ks) to the binary decomposition of the alpha
Yes I agree it's more intuitive! I actually rewatched the Michael Penn video again and it's not actually clear to me if his is the same as mine or not...he does analyze the chances of it going k rounds and shows that's 2^(-k) and that you score alpga_k points when it goes k rounds, but I think very technically speaking his coinflips are the same as ours! It's all just perspective
Love this problem. I studied it years ago. I didn't come up with the solution on my own, but I learned a lot from looking at the answer. It's wonderfully simple and ingenious.
Ya it's a great one to build familiarity with binary decimals! (Or should they be called bin-imals or something?)
So in practice what we will do is write the decimal expansion of α in binary. Then we will construct a new number, term by term of its binary decimal expansion by flipping a coin, say heads is 1 and tails is zero. We keep flipping the coin until the nth toss where the nth digit of our constructed number differs from the nth digit of α. From there we can tell if our number is greater or lesser than α. This can only be infinite if our coin flips match up with α exactly which is probability zero, so we can ignore that case
Yes that's a great summary!
Great Video, the connection to and explanation of Michael Penn's solution in your picture proof was especially nice to see how different solutions could basically describe more or less the same thing.
Just a question, you described alpha in Michael Penn's solution as in binary, wasnt the representation of the U in your solution also basically in binary?
Thanks so much! Yes, both are in binary: in my main solution I never had to refer to the binary expansion of alpha because it was baked into my comparisons of alpha less than or greater than U. You could equally well describe that condition in terms of comparing the binary decomposition of U (the C_ks) to the binary decomposition of the alpha
As soon as you stated the problem, I immediately thought of your solution. It seems a lot less intuitive to stop at heads and translate the meaning
Yes I agree it's more intuitive! I actually rewatched the Michael Penn video again and it's not actually clear to me if his is the same as mine or not...he does analyze the chances of it going k rounds and shows that's 2^(-k) and that you score alpga_k points when it goes k rounds, but I think very technically speaking his coinflips are the same as ours! It's all just perspective