1
$\begingroup$

I am trying to solve a combinatoric problem. The problem is the following: There are A,B,C three types of people. There are totally N people arriving sequentially and make a choice between two boxes X and Y and they just stand in front of the box they have chosen.

The selection rule is the following: Type A people always select box X; Type B people always select the box that has the longest queue, e.g., when facing state $(n,m)$ such that $n>m$, where the 1st entry is the queue length at box X and the 2nd entry is the queue length at box Y. The B type people always chooses box X, which has $n$ people there. If the B type people is the first arrival or he sees two boxes have same queue length, then he chooses each box with 1/2 probability; Type C people always select the box that has positive queue length with equal probability, e.g., when seeing state $(n,0)$, type C people always chooses box X, the one with $n$ people; when seeing state $(n,m)$, with $n>0,m>0$, then type C people chooses each box with equal probability. If the type C people is the first arrival, then he chooses each box with equal probability.

Each arrival with probability $q_A$ of being A type, $q_B$ of being B type, $q_C$ of being C type, and $q_A+q_B+q_C=1$. Each arrival is independent of each other.

The question is to compute the probability $P\{(m,n)|(X,Y)\}$ where $0<m<n$.

This problem can be solved recursively, but I am struggling to obtain some analytical expression.

One thing is sure that the first arrival cannot be type A, since type A people will choose box X only, and then all the later people regardless of their type will all choose box X according to their selection rule.

$\endgroup$
2
  • $\begingroup$ What probability do you want to compute? The probability that $Y$'s queue is ever longer than $X$'s, the probability that $Y$'s queue is longer than $X$'s at some given time, or something else? And can you say something about why you are interested in this problem? $\endgroup$
    – Ben Barber
    May 25, 2016 at 10:07
  • $\begingroup$ Since FTXX is able to compute this quantity recursively, I'm guessing the question is asking for the probability of visiting the state $(m,n)$ as a function of $m$ and $n$ (as well as $q_A$, $q_B$, $q_C$); presumably $N = m+n$ and the queues are initially empty. It seems easier to think about the difference $m-n$ which is doing a version of a simple random walk, but I don't know of a nice exact expression for the distribution of a random walk whose transition probabilities depend on sign. There should be nice exact expressions for asymptotics such as $lim_{N \to \infty} P(m < n)$. $\endgroup$ May 25, 2016 at 21:01

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.