# Difficult Combinatorics Problem, Help PLZ

• Apr 10th 2008, 03:39 PM
ChiragDesai01
Difficult Combinatorics Problem, Help PLZ
i have this assignment due tmrw where i have to answer this question, plzzzzzzzz help i really dont understand it, im being marked for the process of thinking so steps will be very helpful

in a sequence of p zeroes and q ones, the ith term ti, is called a change point if ti does not equal ti-1, for i= 2,3,4....p+q. For example, the sequence of 0,1,1,0,1,0,1,0 has p=q=4, and five change points t2, t4, t6, t7, t8. For all possible sequences of p zeroes and q ones with 1 less then or equal to p which is less then or equal to q, determine the average number of change points.

i know its a difficult problem but plz jus try to help i really dont understand it!

(Yes)
• Apr 11th 2008, 05:24 AM
awkward
Quote:

Originally Posted by ChiragDesai01
i have this assignment due tmrw where i have to answer this question, plzzzzzzzz help i really dont understand it, im being marked for the process of thinking so steps will be very helpful

in a sequence of p zeroes and q ones, the ith term ti, is called a change point if ti does not equal ti-1, for i= 2,3,4....p+q. For example, the sequence of 0,1,1,0,1,0,1,0 has p=q=4, and five change points t2, t4, t6, t7, t8. For all possible sequences of p zeroes and q ones with 1 less then or equal to p which is less then or equal to q, determine the average number of change points.

i know its a difficult problem but plz jus try to help i really dont understand it!

(Yes)

Define $X_i = \begin{cases}
1 \text{ if } t_i \neq t_{i-1}\\
0 \text{ otherwise}
\end{cases}$

For any i from 1 to p+q-1,
$Pr(t_{i-1} = 0) = p / (p+q)$ and $Pr(t_i=1 | t_{i-1} = 0) = q / (p+q-1)$
$Pr(t_{i-1} = 1) = q / (p+q)$ and $Pr(t_i=0| t_{i-1} = 1) = p / (p+q-1)$
so
$Pr(X_i = 1) = \frac{p}{p+q} \frac{q}{p+q-1} + \frac{q}{p+q} \frac{p}{p+q-1} = \frac{2pq}{(p+q)(p+q-1)}$
This is also $E(X_i)$.

The number we want, the average number of change points, is
$E(X_1 + X_2 + \cdots + X_{p+q-1})$. There is an extremely useful theorem saying that if X and Y are random variables then E(X+Y) = E(X) + E(Y). It's important to note that it is not necessary that X and Y be independent in order to apply this theorem. This good for us because the $X_i's$ are not independent. So let's apply it as follows:

$E(X_1 + X_2 + \cdots + X_{p+q-1})$
$= E(X_1) + E(X_2) + \cdots + E(X_{p+q-1})$
$= (p+q-1) E(X_i)$
$= (p+q-1) \frac{2pq}{(p+q)(p+q-1)}$
$= \frac{2pq}{p+q}$

Hope this helps-- I'm in a rush, but then so are you.

jw
• Apr 11th 2008, 05:26 AM
ChiragDesai01
broooooo thanks alot! this dus help im jus guna copy this into my notebook cuz im getting marked on process and thinking thanks boss