Questions tagged [algorithmic-randomness]
Use this tag for questions related to algorithmic randomness, which is the study of random individual elements in sample spaces.
88
questions
1
vote
0
answers
38
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 ...
0
votes
1
answer
25
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 ...
0
votes
0
answers
48
views
Finding a bound for an estimate of $\pi$ using a Monte-Carlo algorithm
I want to estimate $\pi$ using the following method
let $Z$ be $0$ to start with
repeated $N$ times:
draw $u_1, u_2 \in [0, 1]$ and calculate whether or not $(u_1)^2 + (u_2)^2 < 1$, if so add $1$ ...
- 181
3
votes
0
answers
39
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",...
- 5,698
0
votes
0
answers
26
views
Upper Bound to PoS of a congestion game with max λ players using a resource
Good morning everyone, I've been reasoning on this problem for severeal days, but I couldn't end up with a solution.
Consider a congestion game for which we have the following guarantee:
The cost ...
- 1
2
votes
1
answer
96
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 ...
- 246
0
votes
0
answers
11
views
A question about integrality gap, approximation ratio
I am reading the paper on RPR2 rounding on approximation ratio of MaxCut problem. See this link. There is one sentence which is important to me but I don't understand its logic. I quote it here:
If ...
- 509
3
votes
1
answer
61
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 ...
- 3,331
0
votes
1
answer
45
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 ...
- 185
3
votes
2
answers
81
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.
...
- 1,425
0
votes
1
answer
54
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. ...
- 129
-2
votes
1
answer
56
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 ...
- 21
0
votes
1
answer
102
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 ...
- 161
-1
votes
1
answer
87
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 ...
1
vote
1
answer
60
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 $...
- 2,125
2
votes
3
answers
105
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 ...
- 21
0
votes
1
answer
79
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 ...
- 427
1
vote
1
answer
64
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 ...
- 33
0
votes
1
answer
38
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 ...
- 535
1
vote
1
answer
100
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 ...
- 1,581
-1
votes
1
answer
44
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 (...
- 17.9k
4
votes
1
answer
327
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 ...
- 97
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 ...
- 31
2
votes
1
answer
852
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?
- 37
2
votes
0
answers
45
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 ...
- 603
1
vote
0
answers
42
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$ ...
- 941
4
votes
1
answer
537
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 ...
- 120
1
vote
1
answer
64
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 ...
- 11
1
vote
1
answer
143
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 ...
- 11
1
vote
0
answers
18
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 ...
- 1,253
0
votes
0
answers
170
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 ...
0
votes
0
answers
357
views
Proving Knuths Algorithm for generating a Poisson Distribution
I must prove that the following algorithm returns Poisson distributed numbers $k$.
...
0
votes
1
answer
69
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 ...
1
vote
2
answers
58
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: $[\...
- 31
1
vote
0
answers
171
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 ...
- 43
1
vote
2
answers
146
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 ...
- 120
0
votes
0
answers
105
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 ...
- 1,328
0
votes
1
answer
130
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 ...
- 121
1
vote
0
answers
64
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 ...
- 11
2
votes
1
answer
109
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 ...
- 23
0
votes
0
answers
33
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 ...
0
votes
0
answers
262
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 ...
- 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 ...
- 377
0
votes
0
answers
16
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 ...
2
votes
2
answers
172
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)$ ...
- 1,116
0
votes
1
answer
120
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 ...
- 3
1
vote
2
answers
102
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, ...
- 9,516
2
votes
0
answers
70
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 ...
- 191
0
votes
1
answer
78
views
If I roll 5 casino dice at the same time, does the order in which I read the results matter?
If I want to get a perfectly random sequence of numbers in range 1 to 6, possibly very long, and roll 5 casino dice at the same time, does the order in which I read the numbers from individual dice ...
1
vote
1
answer
28
views
Does "for almost each object" make sense in this example?
In the 2nd paragraph at Kolmogorov complexity, these is the following sentence.
"In particular, for almost each object it is not possible to compute even a lower bound for its Kolmogorov complexity .....
- 113