Need closed form for a Binomial series

[issacnewton]

Hello
I was solving a problem in probability. Here is the statement.
Seven terminals in an on-line system are attached to a communications line to the central computer. Exactly four of these terminals are ready to transmit a message. Assume that each terminal is equally likely to be in the ready state.Let $X$ be the random variable whose value is the number of terminals polled until the first ready terminal is located.
(a) What values may $X$ assume ?
(b) What is the probability that $X$ will assume each of these values? Assume that terminals are polled in a fixed sequence without repetition.
(c) Suppose the communication line has $m$ terminals attached of which $n$ are ready to transmit. Show that $X$ can assume only the values $i=1,2,\cdots,m-n+1$ with $P[X =i] = \binom{m-i}[n-i}/\binom{m}{n}$. The problem is from the book Probability, Statistics, and Queueing Theory: With Computer Science Applications by Arnold Allen. The problem can be seen in this google book review. Now I have been able to solve this problem. Though its not asked here, wanted to find the $E(X)$ for case (c). So we would have $$\sum_{i=1}^{m-n+1}i \frac{\binom{m-i}[n-i}} {\binom{m}{n}}$$
I have not been able to get this into some nice closed form. Can anybody provide guidance ? Also there seems to be some problem with the latex command \binom{}{}. Its not working for me.

 

[FactChecker]

Also there seems to be some problem with the latex command \binom{}{}. Its not working for me.

You have a '[' before the n-i that should be a '{'.

$$P[X =i] = \binom{m-i}{n-i}/\binom{m}{n}$$
$$\sum_{i=1}^{m-n+1}i \frac{\binom{m-i}{n-i}} {\binom{m}{n}}$$

 

[issacnewton]

Thanks FactChecker. So do you have any idea how to do summation here. Any closed form ?

 

[FactChecker]

Thanks FactChecker. So do you have any idea how to do summation here. Any closed form ?

Nope. I don't see any way to simplify it (other than possibly factoring out the denominator). If I had Maple or something that could do symbolic math, I might experiment a little, but I don't have Maple.

 

[StoneTemplePython]

Thanks FactChecker. So do you have any idea how to do summation here. Any closed form ?

The problem can instead by interpreted as an absorbing state Markov Chain. Consider using the expression:

$E[X] \approx \frac{m}{n} = \frac{1}{\frac{n}{m}}$

Technically this is an upper bound. If you have a lot of terminals, and a 'semi balanced' mix of working and non-working ones, then this becomes an extremely tight bound that approximates the answer.

If you are concerned with a small number of terminals, you could tighten the bound using a finite geometric series setup where $p = 1 - \frac{n}{m}$, and $E[X] \approx \frac{1-p^{m-n+1}}{1-p}$ but I find the earlier expression rather nicer, and note that in the limit they are the same.

- - - -
Note the summation and probabilities written by isaacNewton and FactChecker have a typo in it that makes the probabilities not sum to one. It should read:

$\sum_{i=1}^{m-n+1}i \frac{\binom{m-i}{n-1}} {\binom{m}{n}}$

Where we have n - 1 not n - i in the binomial coefficient in the numerator.

 

[issacnewton]

StoneTemplePython, thanks for pointing out the mistake of $n-i$. Your explanation about the bounds makes sense. I will have to modify my solution now, as I was helping a student.