# Questions tagged [randomized-algorithms]

Questions about algorithms whose behaviour is determined not only by its input but also by a source of random numbers.

289 questions
Filter by
Sorted by
Tagged with
74 views

### Split a list of elements into sub lists, each with different criteria

I have a list of elements of different values, say 0 to 3. I want to split it into a certain number of sub lists, each accepting only certains elements. The sub lists may not always have the same ...
20 views

### Bayes theorem and randomized algorithms

Are there any randomized algorithms that make use of Bayes theorem? where are they used and why?
75 views

55 views

### What properties does a co-RP problem need to be in P?

Given an arbitrary language $L$ with an algorithm $A$ that places $L$ in $co-RP$ what other properties does the Algorithm $A$ need to have to so that $L$ is in $P$? For example: Considering $L$ is ...
42 views

### How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
12 views

### Randomized response vs Output Perturbation

what are the difference between Randomized response and output perturbation? The only one I can think of is that Randomized Response's output is not always perturbated while in the other case it is.
52 views

8k views

### Can we generate random numbers using irrational numbers like π and e?

Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times ...
49 views

### How to generate random strings from Context-Free Grammar in GNF

I need to generate random strings given a grammar in Greibach Normal Form. The naive approach would be to generate a random integer n and perform ...
29 views

### Difference of simulated annealing and random search for generating crossword puzzles?

I heard that when one wants to write a program to make a crossword puzzle, he can use for example simulated annealing as in the thesis Crossword Construction using Constraint Satisfaction and ...
74 views

### Network throughput with random delay selected from uniform distribution

Background: I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the ...
43 views

### Measuring the Probability of Error for a Potential BPP Algorithm

Problem Given a search algorithm that can be used to query a k-dimensional space, produced from an input array of N data, has a time complexity of $O(klog^2N)$. This algorithm partitions the space ...
39 views

### Using exponential penalty functions in constrained nonlinear optimization

Background: penalty functions Penalty functions convert a constrained optimization problem \begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 ...
154 views

### Efficient n-choose-k random sampling

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)? I have read this question but it asks for generations of all combinations, not ...
57 views

### Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

Let's say I have a simple graph G with an edge set E, vertex set V, and at least 1 cycle. We can determine the number of spanning trees in this graph by finding its graph Laplacian matrix, striking ...
50 views

### Random observations of a total ordering, how much they tell us?

Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know ...
13 views

### Best asymptotic randomized multidimensional index?

What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data? I am interested in both preprocessing time and query time, but let's restrict attention ...
Consider this procedure for building a tree from $v_1, v_2, ..., v_n$: insert $v_1$ insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$ insert $v_3$ and with a uniform ...