New answers tagged probability-theory
2
it seems that you're asking why bother with reservoir sampling when you're capable of tricking the test that you wrote?
Round robin doesn't return random numbers. It returns numbers deterministically. Well much more deterministic seeming than reservoir/other methods.
Your tests should be better. If you need the result to seem random and not deterministic, ...
0
I learned the following argument from Dieter van Melkebeek (but any mistakes are my own). I'm not sure that this is what Arvind and Mukhopadhyay had in mind, because the assumptions are not the same, as I point out after the argument. I am still interested in learning alternative proofs.
The idea will be to start with the collection of all subsets, and ...
1
For each $\Sigma \subseteq [k+1]$, you can compute the probability $q(\Sigma)$ that the first $|\Sigma|$ elements to appear are $\Sigma$ using the following recurrence: $q(\emptyset) = 1$ and when $\Sigma \neq \emptyset$,
$$
q(\Sigma) = \sum_{\sigma \in \Sigma} q(\Sigma-\sigma) \frac{p_\sigma}{p_\sigma + \sum_{\tau \notin \Sigma} p_\tau}.
$$
You are ...
1
Write $T_x$ for the random variable representing the running time of $A$ on input $x$. By Markov's inequality,
$$\Pr(T_x \geq 2 \operatorname{E}(T_x)) \leq \frac{1}{2}.$$
See if you can figure out a solution now.
Solution:
2
We can imagine simulating the random walk on an infinite line, keeping track of the "extension", which is the distance between the rightmost point visited and the leftmost point visited. Let $\ell(a,b)$ denote the probability that the extension became $b-a$ due to a move to $a$, and let $r(a,b)$ denote the probability that the extension became $b-a$ due to a ...
0
This looks like it might be implementing Laplace smoothing (though I can't explain the extra +2 in the first two calculations).
There are many smoothing methods, e.g., Lidstone, Good-Turing, Kneser-Tey, Witten-Bell. You can also use interpolation and backoff to handle rare or low-probability events when computing conditional probabilities like this.
1
The proof is by induction. The base case $t = k$ is clear. Suppose that the claim is true at some time $t$. We will prove it for time $t+1$.
Let the first $t+1$ elements be $x_1,\ldots,x_{t+1}$. By the induction hypothesis, at time $t$ each of the $\binom{t}{k}$ possible $k$-subsets of $x_1,\ldots,x_t$ is found in the array with equal probability. The ...
1
You can compute the average using linearity of expectation.
Let the random variable $X$ denote the number of elements that are retained. Let $X_i$ be an indicator r.v. that is 1 if the $i$th element is retained, or 0 otherwise. Then $X = X_1+\dots + X_n$, so
$$\mathbb{E}[X] = \mathbb{E}[X_1] + \dots + \mathbb{E}[X_n] = \Pr[X_1=1] + \dots + \Pr[X_n=1].$$
...
Top 50 recent answers are included
