# Tag Info

12

To expand out my comment into an answer: the multiplicative form of Chernoff's bound says that if the expectation $X=\sum_{i=0}^n X_i$ for the sum of independent random binary variables is $\mu$, then the probability of straying 'too far' from that expectation goes as: $Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$. ...

11

No, it's not possible. Suppose the bias of the coin is $1/3$, and suppose you could guarantee termination. Then there would be some $n$ such that this always terminates after $n$ coin flips. Let $S$ denote the set of flip-sequences that causes your algorithm to output 0 (so that $\overline{S}$ is the set of flip-sequences that causes your algorithm to ...

10

If I understand the question correctly, the answer is simple: if Hash(object) returns 27 when you call it this afternoon, we want Hash(object) to return 27 if we call it next week, on a different computer. If you use a random number generator in such a way that this is guaranteed, then go for it. Consider that a key use case for hash functions is ...

9

The Knuth-Morris-Pratt algorithm does this in linear time without any error.

8

By definition, $\mathsf{RL}$ is a subset of $\mathsf{NL}$, and so $\mathsf{coRL}$ is a subset of $\mathsf{coNL}$. Since $\mathsf{NL} = \mathsf{coNL}$, $\mathsf{coRL}$ is also subset of $\mathsf{NL}$. Moreover, $\mathsf{NL} \subseteq \mathsf{P}$. Please also note that although it is widely believed to be true, whether $\mathsf{RL} \... 8 When edges connect more than two nodes, you don't have a graph, you have a hypergraph. More precisely, since transitions are oriented (you're starting from a digraph) and there are probability on each transition, you have a weighted hyperdigraph. I'm not sure having this term will help you that much: as data structures go, this isn't that much of a classic. ... 8 There is no decision problem that is (unconditionally) known to be in$coNP \setminus NP$. If we had a decision problem that we could prove is in$coNP$and could prove is not in$NP$, then we would have proven that$NP \ne coNP$, from which it follows that$P \ne NP$. In other words, if we knew of such a problem, a proof that is in$coNP \setminus NP$... 7 I couldn't find the source, but the idea is simple: Use additional bloom filter to represent the set of the deletions. As this is a very simple solution, it might be considered as a folklore. Anyway, I found a short reference to this solution in the following paper (Theory and Practice of Bloom Filters for Distributed Systems): http://www.dca.fee.unicamp.... 7 I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical dynamic perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative. Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected ... 7 This is the arithmetic for Juho's answer. (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability). Suppose it takes time$t$seconds to perform one computation, and thus time$kt$to get the algorithm error probability down to$2^{-k}$. Suppose that the hardware probability of failure per ... 7 The statement of the PCP theorem is essentially equivalent to the following statement: For every problem in NP there is a reduction$f$to$O(1)$-FUNCTION-SAT such that if$x$is a YES instance then$f(x)$is satisfiable, whereas if$x$is a NO instance then at most half of the clauses of$f(x)$can be satisfied. Here an instance of$k$-FUNCTION-SAT ... 7 Suppose that$k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the$k$numbers you get, you pick the smallest one. If$k$is small enough compared to$n$, then it is very likely that the smallest of the$k$numbers is the one that your friend sent you. More concretely, suppose that$k$is constant. With ... 6 Given that you want to insert$n$words into the Bloom filter, and you want a false positive probability of$p$, the wikipedia page on Bloom filters gives the following formulas for choosing$m$, the number of bits in your table and$k$, the number of hash functions that you are going to use. They give$ m = - \frac{n \ln p}{(\ln 2)^2} $and $$k = \frac{m}{... 6 I don't think there is a polynomial probability for losing 'balance'. After you insert an element in a skip list, you build a tower of copies above it by flipping a coin until it comes up heads. So you have layers with fewer and fewer elements as you reach the top. Since a tower has height k with probability 2^{-k}, there is an element at height k ... 6 We say that a probabilistic Turing machine M runs in time T(n) if for any input x M halts in less than T(|x|) steps independently of the random choices it makes during the computation (worst case over all possible computation paths). For example, the most general definition of Probabilistic Polynomial-time, namely PP, is: A language L is in PP if and ... 6 It is easy to think of many different problems: Converting sound to scores. Converting scores to sound. Automatic music composition. Music analysis, for example key recognition. Music classification, such as style recognition and artist recognition. All of these things are actually being done. 6 Using the formula from wikipedia for Bloom filter false positives, your proposal would have a false positive probability of about 0.00726%. This assumes, among other things, that good hash functions are used. The formula is: (1 - (1 - [1/m])^{kn})^k where m is the number of bits in the filter, k is the number of hash functions and n is the number ... 6 To expand Patrick87's comment and help you better understand the probabilistic counting algorithm : Linear Counting is used to get an approximate value of the number of distinct elements in a big set S using a small amount of space. Suppose that you have a set of 1000 of names and you want to know how many distinct names are present in it. In the worst ... 6 The principle of deferred decisions is the concept that we have two ways to make a random choice both of which are equivalent. One way is that you can toss a coin yourself at the exact step when you need a random input in some algorithm. In the other way you can imagine that there is an oracle who has already tossed a coin infinitely many times and has ... 6 Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability \Omega(n^{-2}), i.e. with probability \ge \frac{c}{n^2} for some c>0. This is, of course, very bad. For large n our success probability converges to zero. However, if we run it independently k times, ... 5 No, needing training has nothing to do with unsupervised/supervised. Supervised learners need labels, unsupervised learners do not (they do things like clustering, density estimation, dimensionality reduction). In fact you can use all of them for supervised and unsupervised learning, except maybe CRFs, since an unsupervised CRF would more likely be referred ... 5 It depends what you mean by "probabilistic". There are at least two interpretations. First, the algorithm has some probability of success for every input. Second, the algorithm succeeds on a certain fraction of inputs. For the first interpretation, it is easy to rule out such an algorithm: probabilistic computation can be simulated (inefficiently but ... 5 Based on your above comments with @Gilles, what you describe is just a higher order markov model. For example an nth order markov model, is a model which assumes$$ P(x_t | x_{t-1}, x_{t-2}, \ldots x_1) = P(x_t | x_{t-1}, x_{t-2}, \ldots x_{t-n}).$$If$n$is not fixed you have a variable order markv model. 5 It would seem that the question has been answered at CSTheory.SE. Summary: it is, indeed possible. For example, the Max 2-CSP problem is NP hard with an$O(n)$expected time algorithm. This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem$NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long ... 5 As you say, this is application or situation dependant in general. However, a guideline I have encountered is "making the error probability smaller than the probability of a hardware failure". If I remember correctly, this is at least mentioned in the Mitzenmacher-Upfal book. Say you wanted to replace a deterministic algorithm with a probabilistic algorithm,... 5 Monte Carlo methods are inherently not one-sided, though it's dubious whether they're usually two-sided. The general idea is that in order to estimate the expectation of a random variable$X$, we take the average of many samples of$X$. For example, suppose that you're a petroleum company, and you're trying to decide where to look for oil. For every square ... 5 The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though. Markov's inequality is$P[ X \geq a] \leq E[X]/a$if$X \geq 0$. If we substitude$a = 2E[X]$then we will have$P[ X \geq 2 E[X]] \leq 1/2$. So, basically we run the algorithm ... 5 For simplicity , assume the grid is a square$N \times N$grid and$N$is a prime. Its easy to see that from each row we can pick$\leq 2$points only , so the maximum number of points we can chose is$2N$. Now consider the set of points$\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \}$. For any set of 3 points to be collinear (Lets call them$(x_1,y_1),(x_2,...

4

If the relation $R$ lies in the complexity class P (or even BPP), then boosting works by running your algorithm many times, and testing whether its output satisfies $R$. When $x \in S$, this fails with probability $\mu^N$, where $N$ is the number of times you run $A$. When $x \notin S$, this never fails. This way you can boost $\mu$ from $1-1/\mathrm{poly}(n)... 4 If$AB=C$, then$A(Bx)=Cx$for all vectors$x\$. Generate vectors randomly and check. This known as Freivalds' algorithm. Wikipedia has details.

Only top voted, non community-wiki answers of a minimum length are eligible