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.