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
    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$

  • 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}$

  • 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}}}$