Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we play the following game. You choose a real number $x$ (which you keep secret) and I choose a natural number $N$. On the first turn, you show me the first $N$ digits in the binary expansion of $x$, and based on that I make a guess of $p \in [0,1]$, the proportion of $1$s that will appear in the next $N$ digits. On the next turn, you reveal the next $N$ digits, and I receive $\dfrac{1}{2}-2|p-P|$ added to my score, where $P$ is the actual proportion of $1$s in the sequence you showed me. I can then amend my guess $p$ and we continue playing the game forever.

Note that I never know $x$ in its entirety, therefore I must make a guess of $p$ based on whatever digits have thus far been revealed. An example strategy would be to always guess $p$ to be whatever the true proportion was for the last $N$ digits revealed.

Is there a strategy I can adopt for guessing such that for any number $x$ that you choose, I can maintain a positive score in the long run?

I can't tell if this is an elementary question or not, but I have no idea how to approach it. It is clear that choosing a rational number for $x$ would make it very easy for the guesser to do very well. But I don't know how the game would play for irrational numbers.

I feel like the question may have something to do with normal numbers or perhaps computable/noncomputable numbers. But again, I know little about these things beyond their definition, so I don't know where to start.

Also, the specifics of the game I described are not really the important part, it is just my attempt to a formalize the hazy question I have had in mind for a while, "is it possible to have a sequence where you can never win on average by betting on its evolution?"

Edit: Based on the discussion in the comments (thanks for the input) I have changed the order of quantifiers in the third paragraph where I state the question. There was also discussion regarding what I meant by strategy. Just to be clear, I consider a strategy to be a mapping from strings of digits (the revealed digits of $x$) to guesses $p$. One commenter has pointed out that "any deterministic strategy will fail against some $x$". Somehow this isn't completely obvious to me (perhaps it should be), but I would be interested in a demonstration of this fact. Also, if admitting mixed strategies changes the answer, I'd be curious about that too.

share|improve this question
1  
No, there's no such number. For any number $x$, the optimal strategy is to always guess the actual proportion $P$ of the digits about to be revealed. That's probably not what you had in mind; if so, you may need to work on this aspect of your question a bit. Perhaps by "strategy" you don't mean a strategy in the game-theoretic sense? If so, you should define what a "strategy" is. –  joriki Apr 20 '12 at 16:15
1  
I was aware that $x$ is kept secret. The problem is that in game theory a "strategy" is a very wide concept that also includes the strategy of guessing according to the digits of any real number, including $x$, regardless of whether you've been told $x$ or not. If you want to use a different concept of a "strategy", I think you'll need to define it. The example strategy you give doesn't make it clear to me what would count as a strategy and what wouldn't. –  joriki Apr 20 '12 at 16:33
2  
@JOwen: No, unfortunately that doesn't help at all, since the optimal strategy would still be the one that maps the initial strings of $x$ to the correct guesses $P$. In fact, your definition is precisely the definition of a pure strategy for this game, in the game-theoretic sense, the only further generalization being that one could randomize among such pure strategies to form a so-called mixed strategy, but that's not necessary in this case since a pure strategy is already optimal. –  joriki Apr 20 '12 at 16:59
1  
@JOwen: Perhaps we're talking about different questions. I was talking about the question as formulated in your post: "Is there a number $x$ that you could choose so that no matter my choice of $N$ or clever strategy for guessing $p$, I could not maintain a positive score in the long run?" The answer, using your definition of "strategy" above, is no. There is no such number $x$ because for every $x\in\mathbb R$ there is a strategy (a map from strings to guesses) that guesses perfectly. It's a different strategy for different $x$, but that doesn't matter. –  joriki Apr 20 '12 at 17:11
1  
@JOwen: seem obvious that the guessing player score >= 0 point each round, so it's not possible for him to have a negative expected score. This can be show by this simple strategy: choose a random N, and pick always 0.5, because 0.5 - 2|x-0.5|>=0 for 0<=x<=1. –  carlop Apr 20 '12 at 17:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.