Skip to main content

Questions tagged [algorithmic-randomness]

Use this tag for questions related to algorithmic randomness, which is the study of random individual elements in sample spaces.

Filter by
Sorted by
Tagged with
0 votes
0 answers
23 views

Bounding d-regular graph traversal length for every starting node and every traversal

Question: (Past exam question i'm using to revise) Let $G = (V,E)$. A connected d-regular graph. Let $v_1 \in V$. Assume that at each node, the ends of the edges incident with the node are labelled $1,...
Willow's user avatar
  • 1
0 votes
1 answer
63 views

Impossible Rubik's cube position (2 corners swapped!) [closed]

Left side, white up, Red, green, white corner swapped with Red, blue, white corner Right side, white up, Red, blue, white corner swapped with Red, green, white corner Right, Down, Back view of cube. ...
A.V. Anderson's user avatar
3 votes
2 answers
155 views

Asymptotic convergence of a count-distinct estimator

Consider the following variant of the count-distinct problem. Problem Setting. Let $B = \{ b_1, \dots, b_n \}$ be a finite set of $n$ balls, let $C$ be a set of colours, let $F : B \to C$ be a ...
Boris's user avatar
  • 33
1 vote
0 answers
38 views

Using ML predictions for Online Scheduling Algorithms [closed]

I've read this paper on improving worst case performances of online scheduling algorithms. Was wondering if anyone had any insight on the follow-up question, if you could use the error distribution ...
Test Subject's user avatar
0 votes
0 answers
16 views

Uniform measure of algorithmically random strings

Def. $1$-randomness [Def. 6.1.1 in Downey & Hirschfeldt] An (infinite) string $w$ is $1$-random if there exists some $c \in \mathbb{N}$ s.t. for all $n \in \mathbb{N}$ it holds that $\operatorname{...
Nicholas Brandt's user avatar
1 vote
0 answers
43 views

Probability for a randomly generated string to have the same suffix as the prefix

I am working with randomly generated strings and the minimum fractional period of those string. The minimum fractional period of a string $s$ can be found by checking the eqaulity between the suffix ...
Leonardo Danelutti's user avatar
0 votes
1 answer
42 views

Testing of randomness of binary bit sequences

I am trying to test randomness of binary bit sequence using NIST test suite. The tests applied for testing requires longer length of bit sequence. I have 256 bits sequence. Is it a good approach to ...
Mohit Kumar's user avatar
3 votes
0 answers
40 views

Do all Turing-complete systems converge on a single universal function w.r.t. description redundancy?

Let $L$ be any Turing-complete language. Let $d_L(n)$ be the number of distinct algorithms expressible in $L$ using at most $n$ bits. I'm not sure how to properly define "distinct algorithm",...
Trevor's user avatar
  • 6,004
3 votes
1 answer
289 views

Kolmogorov Complexity and Compression Schemes

My question concerns strings with low Kolmogorov Complexities and if there is a single compression scheme that can be used to compress them I have been introduced to Kolmogorov Complexity through ...
Anwar's user avatar
  • 256
3 votes
1 answer
81 views

Randomly splitting a group into two equal teams using only a fair coin

A few days ago a group of 8 of us had to split into two teams of 4 for the purposes of competing in a trivia night. Notwithstanding that it was far from optimal as a trivia-winning strategy, we ...
Damian Pavlyshyn's user avatar
0 votes
1 answer
90 views

Do random number generators use prime numbers because the gaps between them are random?

Many random number generators like Linear Congruential Generator and the Marsenne Twister generator use prime numbers. Is it to capitalize on the fact that the gaps between the primes are thought of ...
Metrician's user avatar
  • 195
3 votes
2 answers
87 views

Dividing distinguishable cards into distinguishable hands where some hands cannot contain some cards

I am making a computer program to play cards, for this algorithm to work I need to deal cards out randomly. However, I know that some people cannot have some cards due to the rules of the card game. ...
jorisperrenet's user avatar
0 votes
1 answer
64 views

Balls and bins lower bound with random algorithm

Assume we have $n$ bins and $B \sim Binom(nk,p)$ balls to distribute in an equitable. Furthermore, assume that each ball arrives one at a time and must be placed in a bin before the next arrives. ...
Doc Stories's user avatar
-2 votes
1 answer
71 views

How to combine two Monte Carlo algorithms into a Las Vegas one?

Consider a decision problem $D$ with corresponding Monte Carlo algorithms $X$ and $Y$ satisfying the following properties: If $D(s)$ is true, then $X$ returns true with probability $p$ and false ...
Jarler 's user avatar
0 votes
1 answer
147 views

How to distribute $N$ items into $M$ groups the "most" random way?

There are $N$ "items" $s_1, s_2, ..., s_N$ and $M$ "buckets" with capacities $c_1, c_2, ..., c_M$ such that $\sum_{j=1}^{M}c_j = N$. In a document I'm reading (some industry ...
user7647857's user avatar
-1 votes
1 answer
90 views

Does a number n raised to itself (n^n) will have digits depending on the original number n? [closed]

Consider, 7^7 = 823543, the digit 3 in 823543 is repeated two times, is it possible that a number raised to itself can have a higher repetitions of any other digit or is it random. Now consider, 93^93 ...
shubham birmi's user avatar
1 vote
1 answer
73 views

Randomized triangle-freeness testing algorithm.

I'm asked to use the following lemma to prove the statement below. Theorem 1.1.1 (Triangle Removal Lemma). For every $\gamma>0$ there exists $\delta=\delta(\gamma)>0$ such that for every graph $...
ensbana's user avatar
  • 2,307
2 votes
3 answers
114 views

Fixed-rate sampling without replacement

Suppose that we have a population of $N$ elements $E=\{e_1,e_2,...,e_N\}$, and a corresponding set of desired sampling probabilities $P=\{p_1,p_2,...,p_N\}$. Each element $e_i\in E$ should be sampled ...
Ron Banner's user avatar
0 votes
1 answer
132 views

Could my simple iterative algorithm for generating random numbers be favouring digits of value 0?

I have been creating a random number generator, using Python. My script starts by creating a one-dimensional $1 \times N$ matrix of integers ranging from 0 and 9. We can denote this matrix as $A$. I ...
Alexander Kalian's user avatar
1 vote
1 answer
69 views

An algorithm for enumerating subsequences of all infinite binary sequences?

We consider that an infinite binary sequence $s$ is not random in the sense of Martin-Löf. For all the $s$ sequences which respect this constraint, is it possible to build an algorithm which can ...
Antonin's user avatar
  • 33
0 votes
1 answer
46 views

Question on random bits

Sample a uniformly random bit. Let $X$ be the corresponding random variable. Here is a randomized procedure to create two more output bits, denoted by random variables $Y_1$ and $Y_2$. To generate ...
RandomMatrices's user avatar
1 vote
1 answer
114 views

Algorithm for sampling items fails the tests

I was looking into a coding exercise which asks the following: Given an array of positive integers $w$ where each $w_i$ describes the weight of the $i^{th}$ element, implement an algorithm that ...
Jim's user avatar
  • 1,609
-1 votes
1 answer
46 views

Biased graph generating processes

Given a random process (algorithm) that is supposed to generate with equal probability graphs from a given class $\Gamma$. Assume the process is not obviously biased, i.e. generating graphs unevenly (...
Hans-Peter Stricker's user avatar
4 votes
1 answer
423 views

How to find the Expected height of a randomly built binary tree

I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or ...
hello_moto's user avatar
1 vote
0 answers
31 views

What's the expected size of sampling for estimating percentile in a dataset?

Problem definition: D: a size n set of real numbers M: a size m set of real numbers sampled from D without replacement, each number in D has equal probability to appear in M. $m \leq n$ I want to ...
math-bob's user avatar
2 votes
1 answer
1k views

Are there any real-world applications for the logistic map (as defined in chaos theory)?

Is the logistic map only useful for theoretically exploring nonlinear dynamical systems, or can it be applied to real-world scenarios in any practical way?
Jamerson2's user avatar
2 votes
0 answers
50 views

Almost sure statements which don't hold for all Martin Löf random sequences

I have been looking into Martin-Löf random (MLR) sequences. The intuition is that when a statement $P$ is true for almost all sequences, it holds for ALL MLR sequences. For example, the strong law of ...
Anton V.'s user avatar
  • 603
1 vote
0 answers
50 views

Uniform sampling $k$ non-crossing $s$-$t$-paths in plane graph.

Let $G=(V, E)$ be a graph embedded in the plane and let $s, t\in V$ both lie on a common face. Shortest non-crossing $s$-$t$-paths $P$ and $P'$ are shortest paths (wrt. edge count) from $s$ to $t$ ...
S. M. Roch's user avatar
4 votes
1 answer
662 views

Is compressibility a good test for randomness of a pseudorandom sequence?

I am interested in tests and definitions of randomness of a sequence generated by a pseudo-random number generator. A similar question was asked a few years ago, and the response was to use a ...
Lars Ericson's user avatar
1 vote
1 answer
74 views

Is it possible to get the true generating function of a PRNG?

Since every sequence of pseudo-random numbers must be generated by deterministic means, it has to follow some underlying mathematical expression (function-like I guess). Suposse you intend to get this ...
darubik's user avatar
  • 11
1 vote
1 answer
181 views

Why does tSNE includes "Stochastic" on its name?

I know that in Machine Learning one classification of algorithms that researchers use is if they are deterministic or stochastic. I've been studying tSNE, but I don't get if "Stochastic" is ...
user13827069's user avatar
1 vote
0 answers
19 views

difference between sampling from different number system

Is there any difference in algorithm between sampling from different number system, e.g.sample from a standard Gaussian distribution $X \sim N(0,1)$ with samples defined on rational numbers $Q$ or ...
peng yu's user avatar
  • 1,271
0 votes
0 answers
312 views

Understanding the Hiring assistant problem

I am reading Introduction to Algorithms by CLRS and saw the probabilistic analysis of the Hiring assistant problem Problem : $n$ people appear randomly for a job interview for an assistant . We hire ...
Vinay Varahabhotla's user avatar
0 votes
0 answers
519 views

Proving Knuths Algorithm for generating a Poisson Distribution

I must prove that the following algorithm returns Poisson distributed numbers $k$. ...
Tetraquark's user avatar
0 votes
1 answer
73 views

A novice theory about lack of "randomness"

I have a theory, (have no idea even if this has been discussed before). In any set of numbers, you might find a pattern (given enough time), thus making it not random. Example: I was once given a set ...
Kalvin siuth's user avatar
1 vote
2 answers
63 views

$\Sigma_{\tau \in S} 2^{-|\tau|} = 2^{-|\sigma|}$, for any prefix-free $S \subseteq 2^{<\omega}$ s.t. $[S] = [\sigma]$.

The Kolmogorov Inequality gives me $\Sigma_{\tau \in S} 2^{-|\tau|} \leq 2^{-|\sigma|}$, for any prefix-free $S$ extending $\sigma$. But equality seems to hold when $[S] = [\sigma]$. Notation: $[\...
Dariusz's user avatar
  • 51
1 vote
0 answers
196 views

Performance - recurrence for the expected number of recursive calls

Here's what the following code is doing: The randomized algorithm selects the k-th smallest element in an unsorted array A[1...n], 1 < k < n. For simplicity of analysis it is assumed that all ...
bmath123's user avatar
1 vote
2 answers
170 views

Formal statement of property of randomness of a sequence

Suppose we have a probability space $(\Omega,{\mathscr F},P)$ consisting of An arbitrary nonempty set $\Omega$ A collection ${\mathscr F}$ of subsets of $\Omega$ which is also a $\sigma$-algebra on ...
Lars Ericson's user avatar
0 votes
0 answers
141 views

Martin-Löf randomness tests relative to conditional probability?

Background: Martin-Löf's way of defining randomness of finite strings (over a finite alphabet such as $\{0,1\}$) and infinite sequences uses a generalized notion of a statistical test. Often, when ...
Mars's user avatar
  • 1,338
0 votes
1 answer
163 views

Randomness Formal definition

What is the most accurate definition of randomness? I saw some posts concerning random variables, but I would say I don't intuitively think they present some kind of randomness, given that they have ...
Peter's user avatar
  • 121
2 votes
0 answers
82 views

mathematical proof of fast convergence of an nature-inspired algorithm

I am using the Moth-flame optimization algorithm to solve a problem. The algorithm uses logarithmic spiral to update the position of the moths. I have been asked to provide a mathematical proof to ...
Ananya Malik's user avatar
2 votes
1 answer
113 views

Unexpected values returned by C++ noise generation functions

I'm porting the C++ libnoise library into another language. While doing so, I came across a function which appears to return inappropriate values, at least according to the original documentation from ...
user2875252's user avatar
0 votes
0 answers
41 views

Why quasi-random sequences are generated in the interval [0,1]? Is it a normalized sequence generation?

The quasi-random sequences are generated using low discrepancy sequences and Koksma-Hlawka inequality explains the quasi sequence clearly. However, it is observed that these sequences are generated in ...
Saurabh Kumar Pandey's user avatar
0 votes
0 answers
283 views

boxing algorithm problem

This is a bit of a computational algorithm problem, I am not entirely sure if here would be the right place to ask this, but here is the problem. I got some “containers” that each can hold 15, and I ...
kdlsw's user avatar
  • 1
0 votes
1 answer
54 views

Expectation in spectral sparsification algorithms

I am new to random matrices. I am studying the (Sampling) sparsification algorithms done by Daniel Spielman, Teng, Srivastava. They used the concept of graph sampling to obtain a good spectral ...
emelie's user avatar
  • 439
0 votes
0 answers
18 views

Optimal Speed up of Las-Vegas Algorithm

As per my course requirement, I was reading a paper titled "Optimal Speed-up of Las Vegas Algorithm" by M. Luby et. al . I couldn't get around this Lemma $$T(S) = \sum\limits_{t \leq t_{1}} t \cdot ...
Aman Sharma's user avatar
2 votes
2 answers
250 views

How many bits of randomness needed to sample from $\operatorname{Bernoulli}(1/3)$

The title says it all. How can you take a sequence of random coin flops $x_1,x_2,\ldots,x_n\sim\operatorname{Bernoulli}(1/2)$ and generate a sample from a coin $X \sim \operatorname{Bernoulli}(1/3)$ ...
cdipaolo's user avatar
  • 1,156
0 votes
1 answer
133 views

Motivation for Algorithmic Randomness Definition

Wikipedia gives this definition for algorithmic randomness in terms of Kolmogorov complexity: "Given a natural number c and a sequence w, we say that w is c-incompressible if $K(w) \geq |w|-c$. An ...
Halley's user avatar
  • 3
1 vote
2 answers
120 views

Shuffling an ordered list with a given degree of randomness

I feel like the following problem should have a well-known answer, but unfortunately I don't know the keywords to look up. I would like a procedure that takes as an input an ordered list of items, ...
MGA's user avatar
  • 9,666
2 votes
0 answers
73 views

How to generate a uniform simple path from a rectangular grid graph?

I have an $m \times n$ grid graph. I want to generate a simple path from $(1,1)$ to $(m, n)$ uniformly from the set of all such paths. (Note I am not constrainted to move only right/down; the path ...
Curtis F's user avatar
  • 191