Strategies for predicting 100 binary choices given the previous 100 Edit: this project ultimately resulted in the paper "The unpredictable Buridan's ass: Failure to predict decisions in a trivial decision-making task".
Background
As an experimental psychologist, I've long had an interest in binary decision-making tasks. Typically, in such a task, I manipulate a few properties of some hypothetical or real decision, such as the probability of winning a gamble, and ask human subjects which of the two options they'd prefer. Now, however, I'm studying a task in which there is no meaningful difference between the two choices; subjects just make an arbitrary binary choice. The point is to see how well decisions can be predicted in the simplest possible case, as a kind of ceiling (or perhaps floor) for my accuracy in predicting more meaningful decisions.
The problem
I'm asking each subject to make 200 binary choices. The question is, using the first 100 as training data, how can I predict the latter 100, using simple accuracy (the proportion of predicted choices equal to the observed choice) as my loss function? I'm not expecting you guys to give me a complete answer so much as ideas of what kinds of methods I should read about. For example, I'm vaguely aware that stochastic processes and time series exist and that this problem can be modeled as one, but I'm not sure which of the many related methods would be most applicable.
You can see many more details about this study, including my attempts so far, on my website, but here are the most relevant bits:

*

*I have only 3 subjects, but collecting more is easy since I'm on Mechanical Turk.

*Subject tend to choose one of the options about 50% of the time. So, there's lots of room for improvement over a trivial model.

*I have not only the binary choices but also the response times. While I'm not interested in predicting response times for their own sake, and I don't want to let a predictive model see the response time for a decision it's trying to predict, they might still be useful.

*I've framed my investigation as a separate predictive problem for each subject, but I'm open to using all 200 trials from some subjects in order to train a higher-level model used to predict the latter 100 trials in other subjects. (In such a case, I'd probably use cross-validation to let each subject get a chance to be in the test set.)

 A: I recommend you approach this by making some conjectures about the nature of the subject choices, and then model these using appropriate models, and test the conjectures by hypothesis tests/model performance.  From the training data you have displayed in the link, it is pretty clear that the choices are not exchangeable, so this is not a simple Bernoulli sequence.  Instead, it seems that your subject tends to choose a long string of consecutive values of the same type and then switch occasionally.  It is reasonable to conjecture that subjects would tend to forget their previous choices once they become far away, and so it might be the case that their choice depends only on the previous choice, and how long they have been pressing it.  This would lead me to start by trying the following conjecture and model.

Conjecture 1: Subject choice depends only on the previous choice and the number of consecutive values of that choice in the present string.  We assume that subject behaviour is symmetric with respect to the choices.
Modelling: If this conjecture is true, then we can model the binary sequence $X_1, X_2, X_3, ...$ as follows.  For any time index $t$, define:
$$S_t \equiv \max \{ n \in \mathbb{N} | X_t = X_{t-1} = \cdots = X_{t-n+1} \}.$$
The value $S_t$ tells us the number of consecutive values of the present selection at time $t$.  Under our conjecture we have the model form:
$$\mathbb{P}(X_{t+1} = X_{t}| \mathbf{X}_t = \mathbf{x}_t) = f(s_t) \quad \quad \quad \quad \mathbb{P}(X_0 = 1) = \phi.$$
That is, we formulate our model so that the probability of sticking to the same choice at time $t+1$ is fully determined by $s_t$, which is the number of consecutive values that have been chosen.  By specifying a broad parametric form for the function $f$ (e.g., one that is monotonically decreasing using some simple parametric form) we can then model the data and estimate this function, which then gives a basis for making predictions of future values.  We note that this gives a model form that can be analysed as a Markov chain with state-space $(X_t, S_t)$.  



Conjecture 2: Subject choice depends only on the previous choice and the number of consecutive values of that choice in the present string.  We do not assume that subject behaviour is symmetric with respect to the choices.
Modelling: This conjecture is a variation of conjecture 1 where we generalise to allow the probability of sticking/switching to be non-symmetric in the choices.  Under this generalisation we have the model form:
$$\mathbb{P}(X_{t+1} = X_{t} = i| \mathbf{X}_t = \mathbf{x}_t) = f_i(s_t) \quad \quad \quad \quad \mathbb{P}(X_0 = 1) = \phi.$$
That is, we again formulate our model so that the probability of sticking to the same choice at time $t+1$ is fully determined by $s_t$, but now we have two functions $f_0$ and $f_1$ for the two different choices.  We can again specify a parametric form for these functions, model the data and estimate the functions, which then gives a basis for making predictions of future values.  This generalised model form can also be analysed as a Markov chain with state-space $(X_t, S_t)$ (with a slightly generalised transition matrix).


Testing the conjectures: The above model forms would allow you to model your data under some basic conjectures about subject behaviour.  Testing these conjectures could be done in a number of ways, either by nesting these models inside a broader model and doing explicit cross-validation, or by doing some kind of hypothesis test for the conjecture by formulating a test statistic that becomes large when the conjecture is false.  
I will leave it to others to specify other models that could be applied to this type of data.  There are a myriad of possibilities, but the above strike me as reasonable models to start with.  Personally, I would start by fitting a model of a form similar to the ones above, with function(s) $f$ that have some simple parametric form (and maybe test some montonically decreasing functions against broader options).  With $n=100$ data points you should have a reasonable amount of data to estimate a parametric form for such a function.  Have a look at the RMSE of predictions from such a model and see if they are any good.
