Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Need closed form for a Binomial series

  1. Feb 27, 2017 #1
    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.
     
  2. jcsd
  3. Feb 28, 2017 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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}}$$
     
    Last edited: Feb 28, 2017
  4. Feb 28, 2017 #3
    Thanks FactChecker. So do you have any idea how to do summation here. Any closed form ?
     
  5. Feb 28, 2017 #4

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  6. Mar 1, 2017 #5

    StoneTemplePython

    User Avatar
    Gold Member

    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.
     
  7. Mar 1, 2017 #6
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Need closed form for a Binomial series
  1. Binomial distribution (Replies: 3)

  2. Binomial distribution (Replies: 1)

Loading...