Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

Filter by
Sorted by
Tagged with
8 votes
1 answer
535 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 ...
Steven Stadnicki's user avatar
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 ...
bihariforces's user avatar
0 votes
1 answer
30 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 ...
rus9384's user avatar
  • 1,654
0 votes
1 answer
14 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: ...
Vishal's user avatar
  • 1
2 votes
0 answers
82 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 ...
Ashvin Jagadeesan's user avatar
1 vote
1 answer
44 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"-...
Rexcirus's user avatar
  • 171
-1 votes
1 answer
53 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 <...
lesobrod's user avatar
  • 111
3 votes
0 answers
44 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 ...
Alonso Montero's user avatar
0 votes
1 answer
44 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 (...
Dave Jarvis's user avatar
-1 votes
1 answer
59 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 ...
Kashish's user avatar
1 vote
1 answer
47 views

construct language in ${\sf BPP \backslash (RP \cup coRP)}$ assuming $\sf RP \neq ZPP$

Problem This is a HW problem from CMU 15-455 (hw10, p1(a)), spring 17 by Ryan O'Donnell. Assume $L \in {\sf RP \backslash ZPP}$. Define $$ L' = \left\{ (x, y) : \text{either $x \in L$ and $y \notin L$,...
Heda Chen's user avatar
  • 311
1 vote
1 answer
59 views

Average and max. hitting time to a specific vertex [closed]

Consider simple random walks that stop when reaching a given node $x$ in an undirected, unweighted and connected graph on $n$ nodes. Let $H(i,x)$ denote the (expected) hitting time from $i$ to $x$, ...
fawadria's user avatar
  • 113
1 vote
1 answer
43 views

Naïve array sampling algorithm: the possibility of a item being chosen and its time complexity

This naïve sampling algorithm I am talking about is fairly simple: create a set for storing chosen items first, randomly select an item from the array, and examminate if it is in the set. If it isn't, ...
Stephen.W's user avatar
  • 111
1 vote
1 answer
412 views

Why Lavarand (as opposed to other methods of generating random seeds)?

Cloudflare famously uses a wall of lava lamps (https://en.wikipedia.org/wiki/Lavarand) to seed random number generators. But if you're going into the real world to seed your rng, why lava lamps? Why ...
JJW's user avatar
  • 11
1 vote
0 answers
42 views

Probability of a randomised algorithm solving SAT

Let WALKSAT be defined as follows: Let $σ$ be a random truth assignment to the vars For $t = 1, 2, . . . , 3n$: ◦ If $\phi$ is satisfied by $σ$, exit the loop ◦ Else, pick an unsatisfied clause $c$ ...
SVMteamsTool's user avatar
1 vote
0 answers
24 views

How to select a random node when nodes are untrusted in a distributed network? [closed]

Assume in a distributed network, where the nodes are not trusted and are identified by their public keys, we intend to select one of them in a random process. In such a situation, all of the nodes ...
Questioner's user avatar
0 votes
1 answer
24 views

Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?

On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the ...
Daniel Donnelly's user avatar
0 votes
1 answer
47 views

Are turing machines & equivalents with infinite sized random programs still turing machines?

Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to ...
Chao Somnium's user avatar
0 votes
0 answers
2k views

Random team generator with constraints

I would like to create a tool to split a group of persons into multiple teams "randomly". Here is a mockup that shows the UI: https://ibb.co/jDHFkdH Inputs To generate the teams, the tool ...
Edwin ZAP's user avatar
  • 101
0 votes
1 answer
100 views

What's the sum of heights of a random binary search tree

What's the sum of heights of a random binary search tree? By a random binary search tree, I mean the usual definition: you have $n$ keys to be inserted, and all Permutations are equally likely. The ...
user126100's user avatar
4 votes
0 answers
138 views

Uniformly random decimal numbers

Due to finite precision of number representations, we face situations like: In: 0.1+0.1+0.1==0.3 Out: False (on my ...
Matthieu Latapy's user avatar
1 vote
1 answer
31 views

Modifying the probability of sucess of an algorithm

This is motivated from a homework question. Let $A$ be an algorithm with probability of success equal to $q$ for solving a given problem. Let $p \in (0, 1)$. Find an algorithm that has a probability ...
William4920's user avatar
1 vote
0 answers
35 views

What is the most random Markov martingale?

Consider a boxing match between players A and B. If A wins, then $1$ point is gained; otherwise $1$ point is lost. Assume that $A$ is as same good as B. Denote by $X_t$ the expected point of A at time ...
Philo18's user avatar
  • 119
1 vote
0 answers
72 views

Hardness result for online matching

Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (...
user143196's user avatar
1 vote
3 answers
90 views

Is every binary sequence the output of some meaningful-text-input algorithm?

Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/...
jdods's user avatar
  • 111
1 vote
1 answer
31 views

Why does random noise in recurring task periods result in uniform period offsets?

I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten ...
Jonas Kölker's user avatar
1 vote
0 answers
22 views

Distribution independence property testing

I have been reading the proof in the following paper, and I am unable to understand some parts in the proof. This paper shows that a distribution $A$ over $[n]\times[m]$, $n\geq m$, can be $\epsilon$-...
user141088's user avatar
0 votes
2 answers
56 views

A so-called random variable not being well-defined

Consider this algorithm: ...
Emad's user avatar
  • 411
2 votes
1 answer
342 views

Some questions about `RANDOM(a, b)`

This is a question from CLRS: Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of $a$ ...
Emad's user avatar
  • 411
-1 votes
1 answer
49 views

computer science paper: Why t14 and t19 are unreachable and why t19 reachable?

I am reading the paper[1] at: https://arxiv.org/abs/1905.07147 The paper says in Overview section 3: The figure shows a constructed function Bar, which is written in Solidity and contained in a smart ...
user2994783's user avatar
0 votes
0 answers
56 views

Disconnect giant component in random graphs by edge deletion

From a complete random graph (ER graph) after deleting an edge randomly with some probability (p) in each step how many edge deletion occurs to make the graph disconnected or break the giant component?...
Arnab's user avatar
  • 1
4 votes
1 answer
373 views

Randomly selecting element from data structure, probability based on weight

I have a list of elements, each with an id and a weight. A: The weight should be directly proportional to the probability of being randomly selected: An element with weight 10 should be twice as ...
Moritz_st's user avatar
0 votes
0 answers
51 views

How can I randomly sample from the set of NP Complete problems?

I'd like to create some program that can keep spitting out verification algorithms. My verification algorithms take two inputs: problem instance, and solution (both encoded in binary), and output True ...
Phylliida's user avatar
  • 250
1 vote
1 answer
46 views

Definition of RP/poly is not clear!

In Motwani and Raghavan's textbook, p38-39, they states: A sequence $C_1, C_2, C_3, \dots$ of circuits is a circuit family for function $f_n\colon {0,1}^n \rightarrow \{0,1\}$ if $C_n$ has $n$ inputs ...
user777's user avatar
  • 729
1 vote
1 answer
103 views

Could AI be used to detect when a human is picking survey response options randomly?

Context: I am a clinical psych researcher dabbling in machine learning. Humans cannot be truly random. Therefore, could machine learning be used to analyze a string of numbers and determine the ...
Snou's user avatar
  • 11
2 votes
1 answer
152 views

Randomized Version of NP

I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc. Since the above classes are well-known, I will ...
Bader Abu Radi's user avatar
1 vote
1 answer
276 views

Reinforcement learining basics - is it possible to deal with environment with random events

As part of data science course I would like to solve particular problem with reinforcement learning algorithm. I believe I understand general concept, however the problems I had read about up till now ...
White_Raven's user avatar
1 vote
1 answer
58 views

Are there any established methods for generating random graphs/networks that are both planar and meshlike?

There are well-defined methods for generating random graphs / networks that satisfy certain properties, including small-world graphs, scale-free networks, and totally random non-planar graphs. I am ...
Robert Rovetti's user avatar
1 vote
1 answer
72 views

Computational indistinguishability for any distribution using a Chernoff bound

I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. ...
Sid Meier's user avatar
  • 249
2 votes
1 answer
111 views

Shared randomness does not increase capacity of a noisy channel - Why?

Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness? This is ...
user1936752's user avatar
2 votes
1 answer
30 views

Is there a way to measure the maximum random bits of the outputs of a generator?

I want to give examples to explain want I want to know first. Let $G \colon s \mapsto G(s)$ be a PRG. Let $F_{1} \colon s \mapsto G(s) \Vert b$, where $b = \bigoplus_{k = 1}^{|G(s)|} G(s)[k]$. ...
Blanco's user avatar
  • 623
0 votes
1 answer
460 views

How to position images within a canvas while avoiding overlapping

I have a canvas. On this canvas, I want to position 1, 2 or 3 images. The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left ...
Levent Ozbek's user avatar
1 vote
2 answers
455 views

Randomize List with guaranteed Index Change

I usually post on Stackoverflow, but I got stuck with a problem which I think fits better here and I hope someone can help me. The task ist pretty simple: Shuffle/Randomize an array/list conditions: ...
j0h4nn3s's user avatar
  • 111
0 votes
2 answers
1k views

Algorithmic challenge: generate a list of random non overlapping squares [closed]

For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap. So the challenge is simply: given a two dimensional area $a$ (...
Wouter Vandenputte's user avatar
0 votes
0 answers
19 views

Computer Generated If-Statements to create A.I

Just a thought-experiment, could a program be written so that the computer generates it's own if-statements (semi/randomly) and runs them, gathers the results, then tests them in new scenarios, and ...
Aetra's user avatar
  • 1
4 votes
1 answer
494 views

Similarity Of Matrices

Give a randomized algorithm that takes input two $n \times n$ matrices $A$ and $B$ with integer entries and does the following: If $A$ and $B$ are similar, then with high probability the algorithm ...
NeverTooTrivial's user avatar
0 votes
1 answer
49 views

Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly?

Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly? The definition of random for our purpose is anything ...
Sayaman's user avatar
  • 117
3 votes
1 answer
261 views

Under which conditions a given program is deterministic on x86_64 machines?

Given a certain x86_64 "vanilla" binary, without micro-architecture instructions, which can therefore be executed by any x86_64 computer, what are the conditions for the result to be ...
user avatar
3 votes
0 answers
57 views

Assuming $\mathsf{P=BPP}$ would it be possible to derandomize the verifier in Interactive Proof systems?

By the definition, in an Interactive Proof system the verifier is allowed to generate random numbers, which allows the omniscient prover to not fool it in the vast majority of cases for every problem ...
rus9384's user avatar
  • 1,654
0 votes
2 answers
93 views

Benford's law is not working?

So I recently came across Benford's law and immediately tried to code it out but the answer I got was rather confusing. I've been thinking about it for about an hour now and still can't get it, I ...
Avi's user avatar
  • 101

1
2 3 4 5 6