Número previsto de artículos examinados

Question

Actualmente, fallando en la probabilidad básica

Dada una secuencia de elementos, la búsqueda lineal consiste en mirar cada uno de ellos por separado y ver si es el que buscamos. (Es decir, en el peor de los casos, es el último elemento de la secuencia o no está en la secuencia y tendremos que mirar todos los elementos para encontrarlo/determinar que no está).

¿Cuántos elementos de la secuencia de entrada hay que comprobar por término medio, suponiendo que el elemento que se busca tiene la misma probabilidad de ser cualquier elemento de la matriz?

Bien, sabemos dos cosas:

• el elemento que buscamos está en el array
• P[el elemento i-ésimo es el que buscamos] = $\frac{1}{n}$ para todos $i\in\{1,..,n\}$

Y creo que se supone que tengo que conseguir $\frac{n+1}{2}$ o $\frac{n}{2}$ o algo por el estilo.

Dejemos que $X$ sea el número de elementos que el algoritmo de búsqueda lineal está examinando.

$$\begin{align} P[X=1] &= \frac{1}{n} \\ P[X=2] &= \left(1-\frac{1}{n}\right)\frac{1}{n} \\ P[X=3] &= \left(1-\frac{1}{n}\right)^2\frac{1}{n} \\ & \ \ \vdots \\ \end{align}$$

Así que

$$\begin{align} \mathbb{E}(X) &= \sum_{i=1}^n i\left(1-\frac{1}{n}\right)^{i-1}\frac{1}{n} \\ &= \frac{1}{n}\sum_{i=1}^n i\left(1-\frac{1}{n}\right)^{i-1} \\ \end{align}$$

Eso no es algo que quiera resolver yo mismo, así que se lo di a Wolfram Alpha y obtuve

$$\left(1-2\left(\frac{n-1}{n}\right)^n\right)n$$

Esto no parece particularmente cercano.

¿En qué me he equivocado?

Answer 1

Sus cálculos para $P(X=2), P(X=3)$ etc. son incorrectos.

Por ejemplo, deberías tener, $P(X=2)=P(X=2\mid X\ne 1)\cdot P(X\ne 1)=\frac{1}{n-1}\cdot\frac{n-1}{n}=\frac1n$ .

De hecho, como han señalado otros $P(X=k)=\frac1n$ para $k=1, 2,\cdots, n$ .

Answer 2

Suponiendo que haya exactamente un elemento de interés: $$P[X=i]=\frac1n\text{ for }1\le i\le n$$ $$E[X]=\sum_{i=1}^n\frac in=\frac1n\sum_{i=1}^ni=\frac{n(n+1)}{2n}=\frac{n+1}2$$ Si $P[X=i]=\left(1-\frac1n\right)^{i-1}\frac1n$ en cambio, existe una distribución geométrica, que puede realizarse como (digamos) hay $n$ rollos de un $n$ -un dado de lado y buscamos el primer 1 lanzado. Aquí hay un extra $\left(1-\frac1n\right)^n$ probabilidad de hacer $n$ comparaciones y no encontrar el elemento deseado, lo que lleva a la expectativa en este caso como $$\left(1-2\left(\frac{n-1}n\right)^n+\left(1-\frac1n\right)^n\right)n$$ $$=\left(1-\left(1-\frac1n\right)^n\right)n$$ que es diferente de $\frac{n+1}2$ porque el elemento deseado puede aparecer más de una vez en la matriz.

Answer 3

Se trata de una cuestión de condicionalidad.

En su cálculo, usted tomó $1/n$ para ser la probabilidad de que el elemento esté en el $i$ La posición con la condición de que no estuviera en ninguna de las posiciones anteriores $n$ . Si este fuera el caso, entonces su cálculo de las probabilidades para $i\geq2$ sería correcta. Pero, por desgracia, las probabilidades no suman uno.

En cambio, la probabilidad de encontrar el elemento en el $i$ La posición es precisamente $1/n$ por cada $i\in\{1,\dots,n\}$ . Las probabilidades están dadas y no es necesario encontrarlas. Las probabilidades son incondicionales; los eventos para $i<j$ no tienen ninguna relación con $P[X=j]$ . Si quieres, puedes utilizar esta información para encontrar las probabilidades condicionales. No son necesarias en este problema, pero verás que no son $1/n$ .

Hay dos cosas alarmantes en tus cálculos, que insinúan un problema:

1. Usted asumió $P[X=2]=\frac1n$ y el calculado que $P[X=2]=(1-\frac1n)\frac1n$ .
2. Las probabilidades no suman uno aunque deberían.

Answer 4

Si desea incluir la posibilidad de que el objeto deseado no esté en el array:

Denota por $\psi$ la probabilidad de que el objeto deseado no esté en la matriz. Sea $p_i$ denotan la probabilidad de que esté en la ranura $i$ . Entonces, como todos los $p_i$ son iguales, debemos tener $$\sum_{i=1}^np_i=1-\psi\implies p_i=\frac {1-\psi}n$$

Por cada $i<n$ la probabilidad de que se mire exactamente $i$ objetos en su búsqueda es $p_i$ . Para $i=n$ la probabilidad es $p_i+\psi$ . Por lo tanto, en este caso el valor esperado es $$\sum_{i=1}^n i\times \frac {1-\psi}n+n\times \psi=\frac {(n+1)(1-\psi)}2+n\psi=\frac {n+1+n\psi-\psi}2$$

Comprobación de la cordura: Tenga en cuenta que si $\psi=0$ esto se reduce a la fórmula que conocemos. Además, hay que tener en cuenta que si $\psi =1 $ esto se reduce a $n$ como debe ser.

Answer 5

Supongamos que la clave está presente en la lista. Las expectativas del "coste" de encontrar la clave equiprobablemente en cada posición $k$ son $\dfrac kn$ cuya suma es

$$\frac{n(n+1)}2\frac1n=\frac{n+1}2.$$

La corrección por la posibilidad de que la clave esté ausente con probabilidad $q=1-p$ produce

$$p\frac{n+1}2+qn.$$