Questions tagged [randomness]
Randomness is a way to mathematically model uncertainty. We often assume to have access to some well-defined source of random numbers, or that input values or events follow some probability distribution.
260 questions
1 vote
1 answer
104 views
Query regarding random seeds
I am very new to statistics and bioinformatics. For my project, I have been creating a certain number of sets of n patients and splitting them into subsets, say HA and HB, each containing equal number ...
0 votes
0 answers
36 views
Communication complexity in Linear PCP
I wonder how should I state the communication complexity when having a linear PCP combined with another protocol? May I ask that if I have a protocol that utilizes a linear PCP that has proof length n,...
- 101
2 votes
1 answer
173 views
Generating a random bitstring with at most $k$ bits set
Inspired by this SO post, I'd like to generate random bitstrings of a length $n$, having at most $k$ bits set for some $k$. Bitstrings should be selected uniformly at random amongst all possible ...
- 226
1 vote
0 answers
55 views
Construction of a polynomial time algorithm
We are currently learning derandomization, which aims to transfer a probabilistic proof into a deterministic algorithm. My problem is as follows. Given $n$, constructs in time polynomial in $n$, a ...
- 111
2 votes
0 answers
50 views
Picking from a categorical distribution such that the selection is stable
Let's say I have a random variable $V$ which takes values from the finite set $V = \{v_1, v_2,...,v_N \}$. I want to pick one value randomly based on given probabilities $p_i = \Pr(V=v_i)$. Let's call ...
- 121
9 votes
1 answer
662 views
Is there a linear-time algorithm for randomly sampling weighted combinations?
For concreteness, here's the specific problem description: suppose we have a set $S$ of $n$ items $a_1, a_2, \ldots, a_n$ with weights $w_1, w_2, \ldots, w_n$ respectively. The goal is to select a ...
- 2,539
12 votes
5 answers
3k views
pick K random integers without repetition
Suppose we've to pick $K (\le N)$ random integers in the range $[0, N - 1]$ for very large $N$ such that there is no repetition, while also deterministically minimizing the number of calls made to the ...
- 333
0 votes
1 answer
64 views
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
- 2,151
0 votes
1 answer
60 views
Why are seeds connected in Linear Congruential Generators?
I looked through Java's Random class and saw that the initial seed is created using: ...
- 1
2 votes
0 answers
134 views
What are some of the philosophical implications if BPP = P?
As it stands, the general consensus seems to be that BPP = P. If this conjecture were indeed true, what would be some of the philosophical implications beyond theoretical computer science? I know that ...
1 vote
1 answer
83 views
Are there applications in which random number generation quality is the bottleneck?
Random number generators commonly found in default libraries are actually pseudo-random number generators. Nevertheless, more sophisticated options exist to gather entropy from "truly"-...
- 181
-1 votes
1 answer
101 views
Correct way to encode strings
I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples. E.g. for a long string "abbccba.." with an alphabet <...
- 111
3 votes
0 answers
83 views
Given a complexity class C for problems which can be solved using exponential time and an exponential number of random bits. C ⊆ NEXP?
There must be a complexity class C that includes exactly the problems that can be solved in exponential time and having access to a truly random coin (which in turns implies that you will be able to ...
- 145
0 votes
1 answer
100 views
Uniformly random connected minimally cyclic graph algorithm
Background I'm looking to replicate (as closely as possible) the graphs depicted in this question (in MetaPost). Overview The green edges and large green nodes in the following image depict a graph (...
- 271
-1 votes
1 answer
85 views
Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?
While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say ...
- 1