2
$\begingroup$

There are n items in a line. Items are to be picked one by one and removed. So after each turn one item is removed and the next item is picked from remaining items.
Constraint is that only first item or last item from the remaining items can be picked with probability 0.5.

The last item remaining will be picked by probability 1.

So what is the probability that kth item is picked at odd number of turn means probability of picking kth item in 1st, 3rd ,5th turn and so on.

For clarification, if n=2, then in first turn either item can be picked with probability 0.5 leaving one item which will be picked in next turn.

if n>2, second item can't be picked in first turn, it can be picked in second turn or more turns.

  • 0
    Can there be recurrence for this?2012-10-06
  • 0
    I guess the probability is $1/2$.2012-10-06
  • 0
    @Berci, for an item at the end of the line, the probability of being picked on an odd turn is strictly greater than the probability of being picked on the first turn, which is already 1/2.2012-10-06
  • 0
    @GerryMyerson Last item can also be picked at first turn but not the inner items.2012-10-06
  • 0
    @user, yes --- what's your point?2012-10-06
  • 0
    @GerryMyerson First and last items can be solved easily. But how to do for inner items?2012-10-06
  • 0
    If you knew how to do it for the first and last items, why did you not include that information in the body of your question? We should not have to guess what you know and what you don't know. What other secrets are you hiding from us?2012-10-06

4 Answers 4

0

For a given case, if the numbers are not too big, you can do this by hand. Take, for example, $n=17$ items, with $k=6$; we want the probability that the 6th item is picked on an odd turn. Each turn removes either the first remaining item ($F$) or the last remaining item ($L$), with equal probability. So we just enumerate the different ways of arriving at item 6 after an odd number of turns:

$5F$ and $1L$ in any order, followed by an $F$: $p={6\choose1}/2^7$
$5F$ and $3L$ in any order, followed by an $F$: $p={8\choose3}/2^9$
$5F$ and $5L$ in any order, followed by an $F$: $p={10\choose5}/2^{11}$
$5F$ and $7L$ in any order, followed by an $F$: $p={12\choose7}/2^{13}$
$5F$ and $9L$ in any order, followed by an $F$: $p={14\choose9}/2^{15}$

$1F$ and $11L$ in any order, followed by an $L$: $p={12\choose1}/2^{13}$
$3F$ and $11L$ in any order, followed by an $L$: $p={14\choose3}/2^{15}$

$5F$ and $11L$ in any order, and then only item 6 remains: $p={16\choose5}/2^{16}$

But I can't see any way to get a nice formula for the sum of these probabilities.

1

I'll do a special case. Consider an item at an end of the line. It's picked at the first turn with probability 1/2; at the third turn with probability 1/8; fifth turn, 1/32, and so on. As $n\to\infty$, the probability such an item is chosen at an odd turn approaches $$1/2+1/8+1/32+\cdots=2/3$$

  • 1
    That's fit for first item among infinite items. But for kth item among n items, the answer will depend on k and n.2012-10-06
  • 0
    No kidding. But the journey of a thousand miles begins with a single step.2012-10-06
1

Let $P(n,k)$ denote the desired probability for odd number of steps. Then we have $$ P(n,k,even) = 1-P(n,k)$$ $$ P(n,k) = P(n,n+1-k) $$ $$ P(n,k) =0\ \text{ if }\ k\le 0\ \text{ or }\ k>n$$ $$ P(1,1) = 1$$

$$ \begin{align*} P(n,k ) &=\frac12\cdot (1- P(n-1,k))+\frac12\cdot (1-P(n-1,k-1)) \\ &=1-\frac12\cdot\left(P(n-1,k)+P(n-1,k-1)\right) \end{align*}$$

So, it is a recurrence, similar to Pascal's triangle.

For example, it gives $P(2,1) = 1/2$, $P(3,1)=1-1/2\cdot(P(2,1)+P(2,0))=3/4$ $P(3,2)=1-1/2\cdot(P(2,2)+P(2,1)) = 1/2$, $P(4,1)=1-1/2\cdot3/4 = 5/8$, $P(4,2)=1-1/2\cdot(1/2+3/4)=3/8$...

So, something like (multiplied the $n$th row by $\displaystyle\frac1{2^{n-1}}$): $$\begin{bmatrix} 1 \\ 1&1\\ 3&2&3\\ 5&3&3&5 \\ 11&8&10&8&11\\ \vdots&&&&& \ddots \end{bmatrix}$$

Update: Meanwhile I calculated the generator function (better starting with $n=k=0$, but doesn't really matter): $$F(x,y):=\sum_{n,k} P(n,k)\cdot x^ny^k$$ By the recurrence law, we get $$F(x,y)=\sum_{n,k}x^ny^k-\frac12xy\cdot F(x,y)-\frac12x\cdot F(x,y)$$ And hence, using $\sum x^ny^k =\frac1{1-x}\cdot\frac1{1-y}$, we arrive to $$F(x,y)= \frac{1}{(1-x)(1-y)(1+(xy+x)/2)}$$ Then use $\frac1{1-z}$ and the binomial thm for $(1+y)^k$. Unless I miscalculated, it yields $$P(u,v) = \sum_{k\le u,\,l\le v}\frac1{(-2)^k}\cdot\begin{pmatrix}k\\l\end{pmatrix}$$

  • 1
    Whoa! This is actually the same problem as http://math.stackexchange.com/questions/206551/general-term-of-a-double-dimensional-sequence2012-10-06
  • 0
    Thanks for such a descriptive solution.2012-10-06
1

Define
$P(S_i)=Probability\ of\ success\ in\ i'th\ turn\ (We\ pick\ K'th\ element\ in\ this\ turn)$
$P(F_i)=Probability\ of\ fail\ in\ i'th\ turn\ (We\ don't\ pick\ K'th\ element\ in\ this\ turn)$
so for all $i we have:
$P(S_i) = P(F_{i-1}) * {{1}\over{2}}$
but for $i = n$ (last turn), we have only one item and we pick it with probabilty $1$ so we have:
$P(S_n) = P(F_{n-1}) * 1$
$P(F_n) = 0$
in similar manner we define
$P(F_i) = {1\over2} * P(F_{i-1})$
so we have
$P(S_1) = {1\over2} \\P(F_1) = {1\over2} \\P(S_2) = {1\over2}*P(F_1) = {1\over4}\\ P(F_2) = {1\over2}*P(F_1) = {1\over4}\\...\\ P(S_i) = {1\over{2^i}}\\P(F_i)={1\over{2^i}}\\... \\ P(S_{n-1})={1\over{2^{n-1}}}\\P(F_{n-1})={1\over{2^{n-1}}}\\ P(S_n) = {1\over{2^{n-1}}}\\P(F_n)=0$
now probability of picking k'th element in the odd turn is equal to some over all $P(S_i)$ where $i$ is odd
Finally we have:

if $n$ is even we have
$\Sigma_{i=1,3,...,n-1}{P(S_i)} = \Sigma_{i=1,3,...,n-1}{1\over{2^i}}$
if $n$ is odd we have
$[\Sigma_{i=1,3,...,n-2}{P(S_i)}] + P(S_n) = [\Sigma_{i=1,3,...,n-2}{1\over{2^i}}] + {1\over{2^{n-1}}}$