Expectation and Covariance Matrix of $\tilde{C}^{(n)}$

In Section 5.2 of Chapter 5 we introduced the gambling test for pseudorandom number generators. Here we supplement the expectations and covariances of the counter $\tilde{C}^{(n)}$.

Let X_l, $l \in {\rm I\!N}_0$, $X_l \in \{h,t\}$ denote the state of the chain $(S,{\rm I\!P})$with state space $\{h,t\}$ and transition matrix ${\rm I\!P}=\left( {1/2 \atop 1/2} \; {1/2 \atop 1/2} \right)$ at time land let ${\bf P}_0=(1/2,1/2)$ be the initial distribution. Since $(S,{\rm I\!P})$ is independent with respect to ${\bf P}= (1/2,1/2)$, X_l is an i.i.d. sequence of random variables distributed uniformly on $\{h,t\}^{{\rm I\!N}_0}$. Recall that the sequence $(x_l)_{l \ge 0}$ in Section 5.2 denotes a realization of $(X_l)_{l \ge 0}$ based on the pseudorandom numbers $({\verb*+prn+}_l)_{l \ge 0}$. We put

$$Z_l:=\left\{ \begin{array}{r@{\quad \mbox{if} \quad}l} 1 & \s... ...{h\}}(X_j) \ge 26 \mbox{ and } X_{l+52} = t \end{array}\right.$$

the outcome of the l'th game. Recall, that the first 52 coin tosses are needed to initialize the memory of the gambling strategy. Since $(X_l)_{l \ge 0}$ is a stationary sequence, the same obviously holds for $(Z_l)_{l \ge 0}$.

The gambler being mainly interested in the expected win E[Z_l] per game, we will go further and analyze the asymptotic expectation and covariance of the counters $\tilde{C}^{(n)}:=(\tilde{C}^{(n)}_1,\tilde{C}^{(n)}_0,\tilde{C}^{(n)}_{-1})$, where $\tilde{C}^{(n)}_i=\char93 \{Z_l = i \; : \; 0 \le l \le n-1 \}$, $i \in \{1,0,-1\}$. Note, that the above definition of $\tilde{C}^{(n)}$ is equivalent to that given in Section 5.2, where we had $\tilde{C}^{(n)}= \overline{C}^{(n)} M$ for the matrix (5.2)

$$M=(m_{i j})_{(i,j) \in {\rm I\!N}_{2^{53}} \times {\rm I\!N}_3}, \;\; m_{i j}={\bf 1}_{{\cal B}_j}(i).$$

As in Section 3.1.3, we slightly modify our model in the following. This simplifies the calculations significantly and has no effect on the expectations and an asymptotically negligible effect on the covariances: for an arbitrary but fixed sample size $n \in {\rm I\!N}$, $n \ge 53$, let the sequence $(X^{\ast}_l)_{l \ge 0}$ be defined by $X^{\ast}_l = X_k$ with $k=l \pmod n$ and let Z_l be defined as above but by using $X^{\ast}_l$ instead of X_l. This change affects only the last 52 outcomes $Z_{n-52},\ldots,Z_{n-1}$. Note, that $(Z_l)_{0 \le l \le n-1}$ still is a stationary sequence.

As to the expectation $\tilde{{\bf P}}=\frac{1}{n}E[\tilde{C}^{(n)}]$, $\tilde{{\bf P}}=(\tilde{P}_1,\tilde{P}_0,\tilde{P}_{-1})$, we have according to the linearity of the expectation and the stationarity of $(Z_l)_{0 \le l \le n-1}$,

$$\tilde{P}_i = \frac{1}{n} E[\char93 \{Z_l = i \; : \; 0 \le ... ...{1}{n} \sum_{i=0}^{n-1} E[ {\bf 1}_{\{i\}}(Z_l) ] = P[Z_0 = i].$$

These probabilities calculate to

$$(\tilde{P}_1,\tilde{P}_0,\tilde{P}_{-1})= (\frac{1-\tilde{P}_0}{2},\tilde{P}_0,\frac{1-\tilde{P}_0}{2})$$

with $\tilde{P}_0=\frac{1}{2}(1-{52 \choose 26} / 2^{52})$, where ${52 \choose 26}$ denotes the binomial coefficient, so that we get the following numerical approximation

$$(\tilde{P}_1,\tilde{P}_0,\tilde{P}_{-1}) \approx (0.277529, 0.444942, 0.277529).$$

As to the covariance matrix $\Sigma=(\sigma_{i j})_{(i,j) \in \{1,0,-1\}^2}$ we have

$$\sigma_{i j}=\frac{1}{n}Cov\left[ \tilde{C}^{(n)}_i, \tilde{C... ...^{(n)}_j] - E[\tilde{C}^{(n)}_i] E[\tilde{C}^{(n)}_j] \right).$$

Since $\tilde{C}^{(n)}_i = \sum_{l=0}^{n-1} {\bf 1}_{\{i\}}(Z_l)$ we get by the linearity of the expectation and by the stationarity of $(Z_l)_{0 \le l \le n-1}$,

$$\begin{eqnarray*}E[\tilde{C}^{(n)}_i \tilde{C}^{(n)}_j] & = & \sum_{k=0}^{n-1} ... ... = \\ & = & n \sum_{l=0}^{n-1} P[Z_0= i \mbox{ and } Z_l = j]. \end{eqnarray*}$$

Similarly,

$$\begin{eqnarray*}E[\tilde{C}^{(n)}_i] E[\tilde{C}^{(n)}_j] & = & \sum_{k=0}^{n-1... ... = \\ ( & = & n^2 \tilde{{\bf P}}_i \tilde{{\bf P}}_j \;\;\; ). \end{eqnarray*}$$

Here, Z₀ and Z_l are independent of each other whenever l is not contained in the set ${\cal I}:=\{0,1,\ldots,52\} \cup \{n-53,n-52,\ldots,n-1\}$. In this case, $P[Z_0= i \mbox{ and } Z_l = j]=P[Z_0= i] P[Z_l= j]$ and the corresponding terms cancel in the covariance $Cov\left[ \tilde{C}^{(n)}_i, \tilde{C}^{(n)}_j \right]$. Thus

$$\sigma_{i j} = \left( \sum_{l \in {\cal I}} P[Z_0= i \mbox{ a... ...Z_l = j] - \sum_{l \in {\cal I}} P[Z_0 = i] P[Z_l = j] \right),$$

which depends only on a finite set of the random variables $X^{\ast}_l$ and can be computed by summing up over all possible values of these variables. A Mathematica implementation of the covariance matrix, which exploits symmetries in the problem and employs combinatorical formulas to compute the number of occurrences of certain cases, needs about half an hour of CPU time on a DEC 3000 Alpha workstation to compute the covariance matrix $\Sigma$ to

$$\Sigma \approx \left( \begin{array}{rrr} 3.24953 & -5.46111 &... ... -3.94027 \\ 2.21158 & -3.94027 & 1.72869 \end{array}\right).$$

A weak inverse of $\Sigma$ computed by Mathematica's built-in function PseudoInverse is given by

$$\Sigma^{-} \approx \left( \begin{array}{rrr} 2.908145042372 ... ...66681530 & -0.391431566276 & 3.60609824781 \end{array}\right).$$