Probabilidad de elegir el artículo k en el turno impar

Question

Hay n artículos en una línea. Los artículos se recogen uno por uno y se eliminan. Por lo tanto, después de cada turno se retira un elemento y se elige el siguiente de entre los restantes.
La restricción es que sólo se puede elegir el primer elemento o el último de los elementos restantes con una probabilidad de 0,5.

El último elemento que quede será elegido por la probabilidad 1.

Entonces, ¿cuál es la probabilidad de que kth el artículo se recoge en impar número de turno significa la probabilidad de recoger kth elemento en la 1ª, 3ª, 5ª vuelta y así sucesivamente.

Para aclarar, si n=2, entonces en el primer turno cualquiera de los elementos puede ser elegido con una probabilidad de 0,5 dejando un elemento que será elegido en el siguiente turno.

si n>2, el segundo elemento no puede ser recogido en el primer turno, puede ser recogido en el segundo turno o más turnos.

Answer 1

Haré un caso especial. Consideremos un artículo en un extremo de la línea. Se elige en la primera vuelta con probabilidad 1/2; en la tercera vuelta con probabilidad 1/8; quinta vuelta, 1/32, y así sucesivamente. Como $n\to\infty$ la probabilidad de que se elija un artículo de este tipo en un turno impar se aproxima a $$1/2+1/8+1/32+\cdots=2/3$$

Answer 2

Dejemos que $P(n,k)$ denotan la probabilidad deseada para impar número de pasos. Entonces tenemos $$ 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*}$$

Por lo tanto, es una recurrencia, similar al triángulo de Pascal.

Por ejemplo, da $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$ ...

Por lo tanto, algo así como (multiplicado el $n$ la fila de $\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}$$

Actualización: Mientras tanto, calculé la función generadora (mejor empezar con $n=k=0$ pero no importa realmente): $$F(x,y):=\sum_{n,k} P(n,k)\cdot x^ny^k$$ Por la ley de recurrencia, obtenemos $$F(x,y)=\sum_{n,k}x^ny^k-\frac12xy\cdot F(x,y)-\frac12x\cdot F(x,y)$$ Y por lo tanto, utilizando $\sum x^ny^k =\frac1{1-x}\cdot\frac1{1-y}$ Llegamos a $$F(x,y)= \frac{1}{(1-x)(1-y)(1+(xy+x)/2)}$$ A continuación, utilice $\frac1{1-z}$ y el timbre binomial para $(1+y)^k$ . A no ser que haya calculado mal, da $$P(u,v) = \sum_{k\le u,\,l\le v}\frac1{(-2)^k}\cdot\begin{pmatrix}k\\l\end{pmatrix}$$

Answer 3

Definir
$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)$
así que para todos $i<n$ que tenemos:
$P(S_i) = P(F_{i-1}) * {{1}\over{2}}$
pero para $i = n$ (último turno), sólo tenemos un artículo y lo elegimos con probabilidad $1$ por lo que tenemos:
$P(S_n) = P(F_{n-1}) * 1$
$P(F_n) = 0$
de manera similar definimos
$P(F_i) = {1\over2} * P(F_{i-1})$
por lo que tenemos
$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$
ahora la probabilidad de elegir k'th elemento en el turno de impar es igual a algunos sobre todos $P(S_i)$ donde $i$ es impar
Finalmente tenemos:

si $n$ es incluso tenemos
$\Sigma_{i=1,3,...,n-1}{P(S_i)} = \Sigma_{i=1,3,...,n-1}{1\over{2^i}}$
si $n$ es impar tenemos
$[\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}}}$

Answer 4

Para un caso determinado, si los números no son demasiado grandes, puedes hacerlo a mano. Por ejemplo, $n=17$ artículos, con $k=6$ queremos la probabilidad de que el 6º objeto sea elegido en un turno de impar. En cada turno se elimina el primer elemento restante ( $F$ ) o el último elemento restante ( $L$ ), con igual probabilidad. Por lo tanto, nos limitamos a enumerar las diferentes formas de llegar al punto 6 después de un número impar de vueltas:

$5F$ y $1L$ en cualquier orden, seguido de un $F$ : $p={6\choose1}/2^7$
$5F$ y $3L$ en cualquier orden, seguido de un $F$ : $p={8\choose3}/2^9$
$5F$ y $5L$ en cualquier orden, seguido de un $F$ : $p={10\choose5}/2^{11}$
$5F$ y $7L$ en cualquier orden, seguido de un $F$ : $p={12\choose7}/2^{13}$
$5F$ y $9L$ en cualquier orden, seguido de un $F$ : $p={14\choose9}/2^{15}$

$1F$ y $11L$ en cualquier orden, seguido de un $L$ : $p={12\choose1}/2^{13}$
$3F$ y $11L$ en cualquier orden, seguido de un $L$ : $p={14\choose3}/2^{15}$

$5F$ y $11L$ en cualquier orden, y entonces sólo queda el punto 6: $p={16\choose5}/2^{16}$

Pero no veo ninguna manera de obtener una fórmula agradable para la suma de estas probabilidades.