Exercise
Consider the ESP problem as described in Exercise. You are again guessing with information, and you are using the optimal guessing strategy of guessing star if the remaining deck has more stars, circle if more circles, and tossing a coin if the number of stars and circles are equal. Assume that [math]S \geq C[/math], where [math]S[/math] is the number of stars and [math]C[/math] the number of circles.
We can plot the results of a typical game on a graph, where the horizontal axis represents the number of steps and the vertical axis represents the difference between the number of stars and the number of circles that have been turned up. A typical game is shown in Figure. In this particular game, the order in which the cards were turned up is [math](C,S,S,S,S,C,C,S,S,C)[/math]. Thus, in this particular game, there were six stars and four circles in the deck. This means, in particular, that every game played with this deck would have a graph which ends at the point [math](10, 2)[/math]. We define the line [math]L[/math] to be the horizontal line which goes through the ending point on the graph (so its vertical coordinate is just the difference between the number of stars and circles in the deck).
- Show that, when the random walk is below the line [math]L[/math], the player guesses right when the graph goes up (star is turned up) and, when the walk is above the line, the player guesses right when the walk goes down (circle turned up). Show from this property that the subject is sure to have at least [math]S[/math] correct guesses.
- When the walk is at a point [math](x,x)[/math] on the line [math]L[/math] the number of stars
and circles remaining is the same, and so the subject tosses a coin. Show that the
probability that the walk reaches [math](x,x)[/math] is
[[math]] \frac{{S \choose x}{C \choose x}}{{{S + C} \choose {2x}}}\ . [[/math]]Hint: The outcomes of [math]2x[/math] cards is a hypergeometric distribution (see Important Distributions).
- Using the results of (a) and (b) show that the expected number of correct
guesses under intelligent guessing is
[[math]] S + \sum_{x = 1}^C \frac12 \frac{{S \choose x}{C \choose x}}{{{S + C} \choose {2x}}}\ . [[/math]]