Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a doubly ended queue of size n. You and I are playing a game where we take turns and pick one element from front or rear with equal probability(0.5). What is the probability that I pick the ith element in queue, given I go first.

For instance v can have 2 element queue with elements: 1,2 There can be only 2 possibilities. I go first So

I pick 1 and you pick 2
Or I pick 2 and you pick 1

So probability of me picking 1st element = 0.5
probability of me picking 2nd element = 0.5.

Plz Help

share|improve this question
1  
I think the probability is sum over all odd k<=n :C(k-1,i-1)/2^k + sum over all k=n-i+1,K<=n :C(k-1,i-1)/2^k.... is there a simplified version for this sum –  Fluvid Oct 2 '12 at 16:27
add comment

1 Answer

up vote 3 down vote accepted

Suppose the queue is sampled sequentially with equal probabilities of choosing either top of the queue, or the bottom of the queue. The queue is initially filled with balls numbered from 1 to $n$, with ball 1 being at the top, and ball $n$ being at the bottom of the queue.

Let $(t_k, b_k)$ denote the balls at the top and the bottom of the queue at $k$-th turn. The vector $s_k = (t_k,b_k)$ defines the state of the queue. The probability of the next state, given the current one is: $$ \mathbb{P}\left( \left.\begin{pmatrix} t_{k+1} \cr b_{k+1} \end{pmatrix} = \begin{pmatrix} t_k+1 \cr b_k \end{pmatrix}\right| \begin{pmatrix}t_k \cr b_k \end{pmatrix}\right) = \frac{1}{2}, \qquad \mathbb{P}\left( \left.\begin{pmatrix} t_{k+1} \cr b_{k+1} \end{pmatrix} = \begin{pmatrix} t_k \cr b_k-1 \end{pmatrix}\right| \begin{pmatrix}t_k \cr b_k \end{pmatrix}\right) = \frac{1}{2} $$ for states where $t_k < b_k$, $t_k \leqslant i$ and $b_k \geqslant i$. Since we are interested in reaching states where either $b_k$ or $t_k$ equals $i$, we use the trick on making states $b_k \geqslant t_k=i$ and $t_k \leqslant b_k = i$ absorbing, that is once the system reaches that state, it remains in there. $$ \mathbb{P}\left( \left.\begin{pmatrix} t_{k+1} \cr b_{k+1} \end{pmatrix} = \begin{pmatrix} t_k \cr b_k \end{pmatrix}\right| t_k >i \text{ or } b_k<i \right) = 1 $$ The only transition left to specify is from the state where there is only one ball $i$ in the queue: $$ \mathbb{P}\left(t_{k+1}=\text{none}, b_{k+1} = \text{none} | t_k=b_k=i \right) = 1 $$ and the state $(t,b) = (\text{none}, \text{none})$ is also absorbing.

Now, let $T_k$ be the random variable, denoting smallest number of turns needed to end up in the absorbing state: $$ T_i = \inf_{k \geqslant 0} \{ t_k < i \text{ or } b_k > i \text{ or } t_k=\text{none} \text{ and } b_k = \text{none} \} $$ The probability of the first player winning the game is $$ \begin{eqnarray} p(n,i) &=& \sum_{m=1}^{\lceil n/2 \rceil}\mathbb{P}\left(T_i = 2m-1 \right) = \sum_{m=1}^{n}\mathbb{P}\left(T_i = m \right) \frac{1-(-1)^m}{2} \\ &=& \frac{1}{2} \left( \mathcal{P}_{T_i}(1) - \mathcal{P}_{T_i}(-1) \right) = \frac{1}{2} - \frac{1}{2} \mathcal{P}_{T_i}(-1) \end{eqnarray} $$ where $\mathcal{P}_T(z)$ denotes the probability generating function of random variable $T_i$.

Now this is a programming exercise. See the book of Norris on how to compute $\mathbb{P}_{T}(-1)$.

Coding this up, I get the following matrix for $p(n,i)$: $$ \begin{array}{ccccccccccccc} i \backslash n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 1 & 1 & \frac{1}{2} & \frac{3}{4} & \frac{5}{8} & \frac{11}{16} & \frac{21}{32} & \frac{43}{64} & \frac{85}{128} & \frac{171}{256} & \frac{341}{512} & \frac{683}{1024} & \frac{1365}{2048} \\ 2 & & \frac{1}{2} & \frac{1}{2} & \frac{3}{8} & \frac{1}{2} & \frac{13}{32} & \frac{15}{32} & \frac{55}{128} & \frac{29}{64} & \frac{225}{512} & \frac{229}{512} & \frac{907}{2048} \\ 3 & & & \frac{3}{4} & \frac{3}{8} & \frac{5}{8} & \frac{7}{16} & \frac{37}{64} & \frac{61}{128} & \frac{35}{64} & \frac{1}{2} & \frac{543}{1024} & \frac{1047}{2048} \\ 4 & & & & \frac{5}{8} & \frac{1}{2} & \frac{7}{16} & \frac{9}{16} & \frac{55}{128} & \frac{35}{64} & \frac{29}{64} & \frac{67}{128} & \frac{969}{2048} \\ 5 & & & & & \frac{11}{16} & \frac{13}{32} & \frac{37}{64} & \frac{55}{128} & \frac{73}{128} & \frac{113}{256} & \frac{283}{512} & \frac{473}{1024} \\ 6 & & & & & & \frac{21}{32} & \frac{15}{32} & \frac{61}{128} & \frac{35}{64} & \frac{113}{256} & \frac{143}{256} & \frac{455}{1024} \\ 7 & & & & & & & \frac{43}{64} & \frac{55}{128} & \frac{35}{64} & \frac{29}{64} & \frac{283}{512} & \frac{455}{1024} \\ 8 & & & & & & & & \frac{85}{128} & \frac{29}{64} & \frac{1}{2} & \frac{67}{128} & \frac{473}{1024} \\ 9 & & & & & & & & & \frac{171}{256} & \frac{225}{512} & \frac{543}{1024} & \frac{969}{2048} \\ 10 & & & & & & & & & & \frac{341}{512} & \frac{229}{512} & \frac{1047}{2048} \\ 11 & & & & & & & & & & & \frac{683}{1024} & \frac{907}{2048} \\ 12 & & & & & & & & & & & & \frac{1365}{2048} \\ \end{array} $$ The expected symmetry $p(n,i) = p(n,n+1-i)$ is apparent.

It is not hard to guess that $$ p(n,1) = p(n,n) = \frac{2}{3} \left( 1- \frac{(-1)^n}{2^n} \right) $$ $$ p(n,2) = p(n,n-1) = \frac{2}{9} \left( 2 - \frac{(-1)^n}{2^n} (3n-7) \right) $$ Also note, that for $3 \leqslant i \leqslant n-2$ satisfy the recurrence equation (obtained by considering possibilities for outcomes during one turn): $$ \begin{eqnarray} p(n,i) &=& \frac{1}{4} p(n-2, i) + \frac{1}{4} p(n-2,i-2) + \left(\frac{1}{4}+\frac{1}{4} \right) p(n-2, i-1) \\ &=& \frac{1}{4} p(n-2, i) + \frac{1}{4} p(n-2,i-2) + \frac{1}{2} p(n-2, i-1) \end{eqnarray} $$

Hope this helps.


The following code in Mathematica computes probabilities $p(n,i)$ using the recursion equation and boundary conditions:

Clear[p];
p[n_, 1] := 2/3 (1 - (-1)^n/2^n);
p[n_, n_] := 2/3 (1 - (-1)^n/2^n);
p[n_, 2] := 2/9 (2 + (-(1/2))^n (7 - 3 n));
p[n_, m_] /; m + 1 == n := 2/9 (2 + (-(1/2))^n (7 - 3 n));
p[5, 3] := 5/8;
p[n_Integer, i_Integer] /; 3 <= i <= n - 3 := 
  p[n, i] = 
   1/4 p[n - 2, i - 2] + 1/4 p[n - 2, i] + 1/2 p[n - 2, i - 1];
p[n_Integer, m_Integer] /; m > n + 1 - m > 0 := p[n, n + 1 - m];

Here is visualization of $p(n,i)$ as function for $1 \leqslant i \leqslant n$ for various $n$: enter image description here

The code above is capable of handling $n=2000$:

In[213]:= N[p[2000, 1000], 50]

Out[213]= 0.49554080475217015132189161819193863269216947761479

In[215]:= N[p[2000, 500] - 1/2, 50]

Out[215]= -6.5598803020892841065655830535449865490716734884628*10^-117
share|improve this answer
    
actually each of these balls have certain weights. I need to find the expected weight I pick up. I know now I can find that out by summing wi*p(n,i). But Is there some workaround for that? –  Fluvid Oct 2 '12 at 20:12
    
I get high precision error for even n>8. Is there an alternate you can suggest. My n is in range 2000 –  Fluvid Oct 3 '12 at 6:14
    
@Fluvid I have updated my post with Mathematica code to compute $p(n,i)$ than can handle $n$ within your range of interest. –  Sasha Oct 3 '12 at 11:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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