# Probability of picking kth item at odd turn

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.

-
Can there be recurrence for this? –  user1515905 Oct 6 '12 at 9:17
I guess the probability is $1/2$. –  Berci Oct 6 '12 at 9:28
@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. –  Gerry Myerson Oct 6 '12 at 9:59
@GerryMyerson Last item can also be picked at first turn but not the inner items. –  user1515905 Oct 6 '12 at 10:03
@user, yes --- what's your point? –  Gerry Myerson Oct 6 '12 at 10:04

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

-
Whoa! This is actually the same problem as math.stackexchange.com/questions/206551/… –  Gerry Myerson Oct 6 '12 at 12:21
Thanks for such a descriptive solution. –  user1515905 Oct 6 '12 at 22:19

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

-
That's fit for first item among infinite items. But for kth item among n items, the answer will depend on k and n. –  user1515905 Oct 6 '12 at 10:08
No kidding. But the journey of a thousand miles begins with a single step. –  Gerry Myerson Oct 6 '12 at 10:24

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

-

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.

-