Monte Carlo algorithm: Element in array

Question

Design a Monte Carlo algorithm that checks in constant time if a given element $x$ is in a $n$-dimensional vector $V$. Calculate the probability for a correct answer. Then suppose $n=10$, how many times the algorithm must be executed so the probability for a correct answer is greater than $0.9$?

Thats what I tried. Lets pick an arbitrary index $i$ which make sense in $V$, then check if $x=V[i]$ and return true or false as the equality holds or not.

My doubt comes at the time of calculating the probability of a correct answer as the statement gives no more details. Is it even numerically doable without additional asumptions?

I guess the probability of $x\in V$ once $x\not=V[i]$ is $$p=p_1+p_2+\dots+p_{n-1}$$ (following law of total probability) being $p_j$ the probability of $V$ having $j$ times the element $x$. But this probabilities are unknown. Or $$p=1-p'$$ being $p'$ the probability of $V$ not having $x$ as an element (also unknown).

Am I forced to suppose $V$ is a vector of elements of a certain finite set $X$ of $m$ elements or something similar?

Answer 1

It doesn't matter what other elements are. We can assume that $k$ elements in $V$ are equal to $x$. Then the probability for a correct answer would be $k/n$ and $1-k/n$ for an incorrect answer. Then after $m$ tries, the probability of failure would be $(1-\frac{k}{n})^m$. And the probability of success in $m$ tries is the probability of not to be failed in every try, which is $1-(1-\frac{k}{n})^m$.

Answer 2

Your vector has n entries. If x is in the vector, then finding it when you pick a random index has probability at least 1/n (higher if there are multiple copies of x).