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.

  • 1
    $\begingroup$ 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. $\endgroup$ – gung - Reinstate Monica Feb 17 '16 at 0:38
  • $\begingroup$ @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. $\endgroup$ – gung - Reinstate Monica Feb 17 '16 at 0:40
  • 1
    $\begingroup$ @gung, agreed, but in this case I thought the language was too obviously home work-y. $\endgroup$ – Aksakal Feb 17 '16 at 0:41
  • $\begingroup$ Sure, just my generic comment. $\endgroup$ – gung - Reinstate Monica Feb 17 '16 at 0:44
  • $\begingroup$ 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. $\endgroup$ – 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$$


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.

  • $\begingroup$ Hi, Aksakal. Can I ask homework question with tag self-study? Or would Stack Exchange be pleased with that? $\endgroup$ – Navy Feb 18 '16 at 22:39
  • $\begingroup$ 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 $\endgroup$ – Aksakal Feb 18 '16 at 22:42
  • $\begingroup$ 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? $\endgroup$ – Navy Feb 18 '16 at 23:09
  • $\begingroup$ @Navy Plug $x=1$ directly to the sum to see that your formula is incorrect. $\endgroup$ – Aksakal Feb 18 '16 at 23:21
  • $\begingroup$ I see, $C_{n}^{0}=1$. But I think it is hard to calculate d=n, as I tried, with no answer. $\endgroup$ – Navy Feb 19 '16 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.