1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.