# martingales, stochastic processes

Suppose Xn, $n\geqslant0$ is a Markov chain on $\varphi =\left \{ 0,1,2,...,d \right \}$ and $P(x,y)=\frac{\binom{2x}{y}\binom{2d-2x}{d-y}}{\binom{2d}{d}}$. States 0 and d are absorbing states for this chain. Please show that this chain satisfies the equation: $\sum_{y=0}^{d}yP(x,y)=x, x=0,...,d$

I think the equation is the expectation of x, such as Ex(Xi)=x, so I need to take the condition into this form. But i don't know what to do.

• Please read the [self-study] tags wiki. Then tell us what you understand thus far, what you've tried & where you're stuck. We'll provide hints to help you get unstuck. – gung - Reinstate Monica Feb 17 '16 at 0:38
• @Aksakal, it is generally best to ask the OP to add the tag rather than to add the tag for them. That way there is a better chance they will be familiar with our policy. If they don't add the tag within a reasonable period of time, we can close the thread. – gung - Reinstate Monica Feb 17 '16 at 0:40
• @gung, agreed, but in this case I thought the language was too obviously home work-y. – Aksakal Feb 17 '16 at 0:41
• Sure, just my generic comment. – gung - Reinstate Monica Feb 17 '16 at 0:44
• If I may suggest a method with (almost) no computation... Start from a population of $d$ items, amongst which $x$ are marked and $d-x$ are unmarked. Duplicate each item, to reach a population of $2d$ items, amongst which $2x$ are marked and $2d-2x$ are unmarked. Draw uniformly randomly a new population of $d$ items from these and call $y$ the number of marked items in it. Then $x\to y$ is a step of your Markov chain. Each item in the new population is marked with probability $p=(2x)/(2d)$ hence the mean number of marked items in the new population is $d\cdot p=x$, qed. – Did Feb 25 '16 at 10:57

No, you don't need expectations. All you need is a straight up combinatorics.

For instance, look at $d=2$ to see what's up here. The numerator and denominator are: $$\sum_{y=0}^2 y \binom{2 x}{y}\binom{4-2 x}{2-y} = 6 x$$ $$\binom{4}{2} = 6$$

So, you get $$\sum_{y=0}^{2}yP(x,y)=x, x=0,1,2$$

UPDATE:

Here's how the numerator looks for $x=1$: $$0 \binom{2}{0}\binom{2}{2} = 0$$ $$\binom{2}{1}\binom{2}{1} = 4$$ $$2 \binom{2}{2}\binom{2}{0} = 2$$ The numerator is the sum $0+4+2=6$, so the equality to holds. You can check $x=0,2$ yourself.

• Hi, Aksakal. Can I ask homework question with tag self-study? Or would Stack Exchange be pleased with that? – Navy Feb 18 '16 at 22:39
• Yes, do ask, but also show your work. Read the description of self study tag, it explains how to ask for help with home works – Aksakal Feb 18 '16 at 22:42
• I think $\sum_{y=0}^2 y \binom{2 x}{y}\binom{4-2 x}{2-y} = 6 x$ is incorrect. What i get is $\sum_{y=0}^2 y \binom{2 x}{y}\binom{4-2 x}{2-y} = 8x-4x^2$. And I think taking this method is a bit tough, because it is hard to calculate d=n. Is there any other method? – Navy Feb 18 '16 at 23:09
• @Navy Plug $x=1$ directly to the sum to see that your formula is incorrect. – Aksakal Feb 18 '16 at 23:21
• I see, $C_{n}^{0}=1$. But I think it is hard to calculate d=n, as I tried, with no answer. – Navy Feb 19 '16 at 0:13