# Random walks in multinomial case

Model:

A vector $X=(X_1, X_2, X_3)$ that follows a trinomial distribution with parameters $p=1/3$ and $n$.

(I have a coin with three sides $S1$, $S2$, $S3$). I flip the coin $n$ times. The coin has a probability $p=1/3$ to be flipped to the side $S1$, and similarly with $S2$ and $S3$. $X_1$ counts the number of times the coin is flipped to $S1$ ($X_2$ and $X_3$ are defined similarly).

Questions:

1. Let $0 \leq \alpha \leq n$. I Want to find $T(\alpha)= P (((X_1 - X_2) \geq \alpha) \cap ((X_1 - X_3) \geq \alpha))$, or a lower bound on $T(\alpha)$
2. For what values of $\alpha$, The lower bound on $T(\alpha)$ does not depend on $n$ (is a constant) ?

If $X$ was following a binomial distribution, the problem would have been easy to solve using random walks, but I do not know how to solve it in the multidimensional case.

Any idea? Thank you.

Two-dimensional case

$X= (X_1, X_2)$ follows a binomial distribution with parameters $p=1/2$ and $n$.

(A coin is flipped $n$ times. the coin is up with probability $p=1/2$ and down with probability $p$. $X_1$ counts the number of ups and $X_2$ counts the number of downs)

Let $Y= X_1 - X_2$ (We have $n$ coin flips, when the coin is flipped up, we add (+1) to $Y$, when the the coin is flipped down, we add (-1) to $Y$). We can see this as a random walk, when the coin is up we go to the right and when it is down we go to the left.

$\mathrm{Var}(Y)=n = \sqrt n ^2$. $E(Y)=0$

By the Central Limit Theorem, $P(Y \geq \alpha) \approx 1 - \Phi(\alpha / \sqrt n)$ (normal distribution).

-
Could you elaborate on the sense in which this is a "random walk"? You haven't described a stochastic process; something is missing. –  whuber Aug 17 '11 at 13:48
@whuber: I edited the question. I hope it is ok now. –  user2094 Aug 17 '11 at 14:28
Exactly how does a trinomial distribution lead to a random walk? Now we can form three differences $X_i-X_j$; what do we do with them? You need to be explicit. Even your description of the "two-dimensional" random walk is faulty: there's still no stochastic process in evidence. –  whuber Aug 17 '11 at 14:44
I don't know how to use to random walk in multidimensional case, I just say that random walks help to solve the problem in the two-dimensional case. The stochastic process: I flip a coin $n$ times. the coin is up with probability $p=1/2$ and down with probability $p$. $X_1$ counts the number of ups and $X_2$ counts the number of downs. –  user2094 Aug 17 '11 at 14:49
OK I added a description. (I have a coin with three sides S1, S2, S3). I flip the coin n times. The coin has a probability p=1/3 to be flipped to the side S1, and similarly with S2 and S3. X1 counts the number of times the coin is flipped to S1 (X2 and X3 are defined similarly). –  user2094 Aug 17 '11 at 14:58

The probabilities for this problem can be calculated explicitly for quite large $n$.
To get a very good approximation for even moderately large $n$, we can use the multivariate central limit theorem.


Hence, $\Cov(U_1, U_2) = n p (1-p) + n p^2 = np = n/3$ and by a similar calculation, $\Cov(U_1, U_1) = \Cov(U_2,U_2) = 2 n p = 2 n / 3$.

Observe that $U_1$ and $U_2$ are each the sums of independent and identically distributed random variables. For example, if $\xi_i \in \{1,2,3\}$ is the outcome of the $i$th draw, then $U_1 = \sum_{i=1}^n 1_{(\xi_i = 1)} - 1_{(\xi_i = 2)}$ where $1_{(\cdot)}$ is the indicator function.

Hence, by the multivariate central limit theorem, we conclude that $$\sqrt{\frac{3}{n}} (U_1,U_2) \xrightarrow{d} \mathcal{N}(0, \Sigma)$$ where $$\Sigma = \left(\begin{array}{cc}2 & 1 \\ 1 & 2\end{array}\right).$$

Now, since $$T(\alpha) = \Pr( \{X_1 - X_2 \geq \alpha \} \cap \{X_1 - X_3 \geq \alpha \} ) = \Pr( U_1 \geq \alpha, U_2 \geq \alpha)$$ then, we can approximate $T(\alpha)$ as follows $$T(\alpha) \approx \int_{\alpha\sqrt{3/n}}^\infty \int_{\alpha\sqrt{3/n}}^\infty \frac{1}{2 \sqrt{3} \pi} e^{-\frac{1}{3}(u_1^2 - u_1 u_2 + u_2^2 )} \mathrm{d}u_1 \mathrm{d}u_2 \> .$$

Below is some very brief $R$ code that compares a simulation of the true process against a simulation using the normal approximation assuming $n = 100$ underlying trinomial trials.
First, the picture.

Here is the code.

set.seed(.Random.seed[1])
n <- 100
N <- 10000

X   <- matrix( sample(1:3, n*N, replace=T), nc=n )
xt  <- apply(X,1,table)
dxt <- cbind( xt[1,]-xt[2,], xt[1,]-xt[3,] )
xtt <- table(apply(dxt,1,min))

L   <- matrix( c(sqrt(2), 1/sqrt(2), 0, sqrt(3/2)), 2 )
Y   <- L %*% matrix( rnorm( 2*N ), nr=2 ) * sqrt(n) / sqrt(3)
ytt <- table( floor(apply(Y,2,min)) )

plot( names(xtt), xtt/N, type="h", xlab="a", ylab="Density of T(a)" )
lines( names(ytt), ytt/N, col="red", type="h" )
legend( "topright", legend=c("actual", "normal approx."), lty="solid",
col=c("black", "red"), bg="white", inset=0.02 )


There are also R packages to calculate bivariate normal densities and probabilities. Both mnormt and fMultivar are examples, but I don't know enough to recommend any one over another.

-
Thank you very much for your detailed response. May I ask you another question ? If I generalize my problem the general f-nomial case (f=2 for the binomial and f=3 for the trinomial), so I have $f$ variables $X_1, X_2, .... X_f$. I want to calculate the probability $P(\alpha)$ that some $X_i$ is greater than all the other $X_j, j\neq i$ by at least $\alpha$. Suppose I fix $\alpha=\sqrt(N)$, do you think that I can find an approximation or a lower bound to $P(\alpha)$ that does NOT depend on $f$, even if it is very low. Thank you. –  user2094 Sep 5 '11 at 7:19
You want a lower bound as opposed to an upper bound? I'm not sure a nontrivial such bound will exist, but I will think about it a little. –  cardinal Sep 5 '11 at 18:37
By lower bound I mean a value $V$ that is lower than the probability I want to compute, to be able that the probability is at least equal to $V$. –  user2094 Sep 7 '11 at 16:22
I deleted some previous comments that were no longer relevant. I will try to update this answer with a more general one in the next few days if you are still interested. –  cardinal Sep 21 '11 at 17:05
Yes, thank you, I would be very grateful. –  user2094 Sep 24 '11 at 10:19