Sessions of random length and variance

[jason1990]

Let X_1, X_2, ... be iid with mean 0 and variance 1. Let S_n = X_1 + ... + X_n and Z_n = S_n/sqrt{n}.

It is easy to prove that Var(Z_n) = 1. But what if n is random? In other words, if N is a random index, then what is Var(Z_N)?

Here are some simple examples. In all of them, let X_j be 1 or -1 with equal likelihood.

Example 1. Let N = 1 if X_1 = 1, and N = 2 otherwise. (This is the case where I stop if I am ahead.) Then 50% of the time, N = 1 and in this case Z_N = 1; 25% of the time N = 2 and X_2 = 1. In this case, Z_N = 0. The other 25% of the time N = 2 and X_2 = -1. In this case, Z_N = -sqrt{2}. To summarize,

P(Z_N = 1) = 0.5
P(Z_N = 0) = 0.25
P(Z_N = -sqrt{2}) = 0.25

This gives

E[Z_N] = 0.5 - sqrt{2}(0.25) = 0.146
E[(Z_N)^2] = 0.5 + 2(0.25) = 1
Var(Z_N) = 1 - (0.146)^2 = 0.979

Example 2. Let N = 1 if X_1 = -1, and N = 2 otherwise. (This is the case where I stop if I am behind.) In this case, Var(Z_N) = 0.979, just as before.

Example 3. Let N = 1 if X_2 = -1, and N = 2 otherwise. (This is the magical case where I look into the future and stop if I am about to lose.) Then each of the following events has probability 0.25:

X_1 = 1, X_2 = 1, N = 2, Z_N = sqrt{2}
X_1 = 1, X_2 = -1, N = 1, Z_N = 1
X_1 = -1, X_2 = 1, N = 2, Z_N = 0
X_1 = -1, X_2 = -1, N = 1, Z_N = -1

Hence,

E[Z_N] = sqrt{2}(0.25) = 0.354
E[(Z_N)^2] = 0.5 + 2(0.25) = 1
Var(Z_N) = 1 - (0.354)^2 = 7/8 = 0.875

Questions: Is it always the case that Var(Z_N) is less than or equal to 1? If not, is there a counterexample that uses a random index N which does not look into the future and is bounded by some fixed constant?

[jason1990]

Another Example. Let X_j be 1 or -1 with equal likelihood. Let N = 3 if S_2 = 2, and N = 2 otherwise. (This is the case where I play 2 rounds for sure, but only play a 3rd if I won both the first two.) In this case,

P(N = 3, X_3 = 1) = P(Z_N = 3/sqrt{3}) = 1/8
P(N = 3, X_3 = -1) = P(Z_N = 1/sqrt{3}) = 1/8
P(N = 2, S_2 = 0) = P(Z_N = 0) = 1/2
P(N = 2, S_2 = -2) = P(Z_N = -2/sqrt{2}) = 1/4

Hence,

E[(Z_N)^2] = 3(1/8) + (1/3)(1/8) + 2(1/4) = 11/12.

Therefore, Var(Z_N) <= E[(Z_N)^2] < 1.

A Stronger Conjecture. Is it always the case that E[(Z_N)^2] <= 1?

An Observation. If N is independent of the sequence X_1, X_2, ..., then E[(Z_N)^2] = 1.

A Connection to Poker. Imagine that X_j is the result of the j-th hand of poker by a break-even player; S_n is the result of his session, which is n hands long. If this player tries to estimate his standard deviation using his session results (rather than his per-hand results), then Z_n will be a term that appears in that estimate.

In order for his estimate to be unbiased, it is important that E[(Z_n)^2] be equal to his true per-hand variance, which is 1. This will be true if n is not random, or if n is random but independent of his results X_j. But if his session lengths depend on the results of his play, then this will not be true and his estimate will be biased. The conjecture is that it is always biased in one direction. That is, he will always compute a standard deviation which is lower than his true standard deviation.

Both myself and another poster have observed this phenomenon in practice. The SD computed by PT (which is computed using session results) is consistently lower than the SD one gets when one estimates directly from the per-hand data (using Excel or MATLAB, for example).

[marv]

Assume X_i = +1 or -1. If we can look into the future, just pick N = least s.t. X_{N+1} != X_N.

Then Z_N = sqrt(N) X_1. As N and X_1 are independent, E(Z_N) = 0 and Var(Z_N) = E((Z_N)^2) = E(N) = sum{k>=1} k/2^k = 2.

Marv

[jason1990]

Thanks, marv. That's a nice example. For the record, I will point out that your N not only looks into the future, but it is also not bounded by any fixed constant.

Nonetheless, you have ruled out the most general form of the conjecture. Do you have a counterexample with an N which is either bounded or non-anticipating?

By the way, for anyone who wants a formal definition, N is "non-anticipating" if, for all (deterministic) k, the event {N = k} depends only on X_1, ..., X_k.

[marv]

[ QUOTE ]
Thanks, marv. That's a nice example. For the record, I will point out that your N not only looks into the future, but it is also not bounded by any fixed constant.

Nonetheless, you have ruled out the most general form of the conjecture. Do you have a counterexample with an N which is either bounded or non-anticipating?

By the way, for anyone who wants a formal definition, N is "non-anticipating" if, for all (deterministic) k, the event {N = k} depends only on X_1, ..., X_k.

[/ QUOTE ]

True, my example wasn't exactly earth shattering.

To get a bounded N, just use N2 = min(N,T) for some fixed T. Since Z_N2 -> Z_N monotonically as T->infinity we have Var(Z_N2)->Var(Z_N) so for sufficiently large T we'll have Var(Z_N2) > 1.

The non-anticipative case is obviously much more interesting, and I'm still thinking about that ...

Marv

[jason1990]

Okay, I think this is a valid non-anticipating counterexample. Let X_j be 1 or -1 with equal likelihood. Let N be the first time that |Z_N| > 2. By the law of the iterated logarithm, N is finite with probability 1. By symmetry, E[Z_N] = 0. And, of course, E[(Z_N)^2] > 4.

For a bounded example, take min(N,T) for T sufficiently large. This works because |Z_{min(N,T)}| <= |Z_N|, so we can apply dominated convergence.

So it appears that the random session lengths can create bias in either direction. I wonder if one direction is more common than the other and, if so, what would explain that?

[marv]

[ QUOTE ]
Okay, I think this is a valid non-anticipating counterexample. Let X_j be 1 or -1 with equal likelihood. Let N be the first time that |Z_N| > 2. By the law of the iterated logarithm, N is finite with probability 1. By symmetry, E[Z_N] = 0. And, of course, E[(Z_N)^2] > 4.

For a bounded example, take min(N,T) for T sufficiently large. This works because |Z_{min(N,T)}| <= |Z_N|, so we can apply dominated convergence.

So it appears that the random session lengths can create bias in either direction. I wonder if one direction is more common than the other and, if so, what would explain that?

[/ QUOTE ]

Looks good to me. What are E(N) and Var(N) equal to here?

Marv

[jason1990]

[ QUOTE ]
Looks good to me. What are E(N) and Var(N) equal to here?

[/ QUOTE ]
Good question. I don't know off hand. Maybe it would be better to change N to the first time |Z_N| > 1, then rewrite that as the first time (S_n)^2 - n > 0. This might help because (S_n)^2 - n is a martingale. If it were Brownian motion instead of a random walk, then I might try using Girsanov to compute this, although it's not clear to me that even that would give a closed form expression.

I have been thinking more about the connection to poker here. If m is your true per-hand winrate, s is your true per-hand SD, and Y_j is the result of your j-th hand, then we can write

Y_j = m + sX_j,

where X_j is some random variable with mean 0 and variance 1. The result of an n-hand session is then

mn + sS_n.

Your observed winrate over that n-hand session is

m + s(S_n)/n.

So Z_n is sqrt{n}/s times the difference between your observed winrate and your true winrate. Do you tend to stop your sessions at points where this quantity is either larger or smaller than you would expect it to be in a session of fixed length? If so, then the session-based estimator of SD (i.e. the estimator which Mason describes in "Gambling Theory and Other Topics" and which is used by Poker Tracker) will be biased. Often, session lengths are out of your control. A session might end because the table breaks up, for example. The break-up of the table could easily be correlated to your observed results at that table. I think it is unreasonable to believe that anyone could entirely eliminate the correlation between session lengths and results.

Therefore, the session-based estimator is potentially highly biased. This is aside from the standard issues of the fudge factor (1/n versus 1/(n-1)) or the fact that you need (as Mason says) at least 30 sessions. The bias which comes from random session lengths will not be corrected by any fudge factor nor will it necessarily be corrected in the long run when computed over even infinitely many sessions. Because of this, I think it is pretty clear that the Poker Tracker software should not be using this estimator, especially since they have the available data to do a per-hand analysis.

[jason1990]

[ QUOTE ]
Good question. I don't know off hand. Maybe it would be better to change N to the first time |Z_N| > 1, then rewrite that as the first time (S_n)^2 - n > 0. This might help because (S_n)^2 - n is a martingale. If it were Brownian motion instead of a random walk, then I might try using Girsanov to compute this, although it's not clear to me that even that would give a closed form expression.

[/ QUOTE ]
Going back to the original time N = the first time |Z_N| > 2, I am starting to wonder if E[N] is even finite. Given the absolute values in the definition, my first thought was that it must be finite. But we can rewrite it as the first time that

(S_n)^2 - 4n = ((S_n)^2 - n) - 3n

is positive. This is a martingale plus a negative drift, and we want the first time it exceeds 0. Looking at it this way, I would not be surprised if E[N] were infinite.

Perhaps one can find a lower bound on P(N > n) which is not summable.

[jason1990]

[ QUOTE ]
What are E(N) and Var(N) equal to here?

[/ QUOTE ]
E[N] = infty.

Let N be the first time |Z_n| > c, where c is at least 1. Let T(n) = min(n,N). Since (S_n)^2 - n is a martingale and T(n) is a bounded stopping time, we may apply the optional sampling theorem to get

E[(S_T(n))^2] = E[T(n)].

Hence,

E[T(n)] >= E[I*(S_N)^2],

where I = 1 if N < n and I = 0 otherwise. Let n go to infinity. By monotone convergence, E[N] >= E[S_N^2]. But S_N^2 > (c^2)N. If E[N] is finite, this is a contradiction.