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
2
votes
1answer
68 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 ...
1
vote
1answer
46 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 ...
1
vote
1answer
22 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 ...
1
vote
0answers
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 ...
0
votes
0answers
24 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
0answers
27 views

Proving Knuths Algorithm for generating a Poisson Distribution

I must prove that the following algorithm returns Poisson distributed numbers $k$. ...
0
votes
1answer
46 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
2answers
47 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: $[\...
1
vote
0answers
66 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 ...
1
vote
2answers
84 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 ...
0
votes
0answers
15 views

Why divide by (size of alphabet) - 1 in Martin-Löf randomness tests?

In Information and Randomness: An Algorithmic Perspective, 2nd ed., Calude defines "Martin-Löf test" for uniform distributions over a finite alphabet of size $Q$, and includes this requirement for a ...
0
votes
0answers
27 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 ...
0
votes
1answer
54 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 ...
1
vote
0answers
43 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 ...
2
votes
1answer
76 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 ...
0
votes
0answers
26 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
0answers
124 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 ...
0
votes
1answer
37 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 ...
0
votes
0answers
13 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
1answer
45 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)$ ...
0
votes
1answer
81 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 ...
1
vote
2answers
53 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, ...
2
votes
0answers
50 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 ...
0
votes
1answer
58 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
1answer
25 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 .....
0
votes
0answers
63 views

Normal number and Kolmogorov complexity

For real number $r$, infinite sequence of its digits in base 10, (I mean 1/9=>1,1,1,1,1,1,1,1,1,1,1,1.....) I heard that if this sequence is the random sequence in the sense of kolmogorov complexity ...
-2
votes
1answer
31 views

Shuffling Cards by Grouping

Lets say I have 5 cards, a b c d and e. I group those as 2, 2 and 1, my first group contains a and b, second group contains c and d, and the last group contains only e. Then I mix those, by putting ...
-1
votes
1answer
84 views

What is polynomial-time random language?

What is polynomial-time random language? I have tried to found the definition by searching artilce, but failed. Any one give reference?
1
vote
2answers
75 views

How to make unlimited number of fair coin be equivalent to two fair dice that takes the sum of their outcomes?

I have an exercise in Randomized algorithm it takes me time to answer it but this king of question is new for me and I need a hint to begin with. Problem 1.3 [Motwani and Raghavan's textbook] (Due to ...
2
votes
2answers
186 views

Calculate mean value from given data

This question is about requesting some applicable algorithm rather than mathematical idea and is not part of any homework or study project. The solution may be obvious, but I can't see it by myself. ...
1
vote
0answers
67 views

Seeking general information about modal probability arithmetic

Imagine Peano Arithmetic extended with a modal operator $P_{n}^{\ge a/b}$, where $n$ is a variable possibly appearing free in the following expression and $a$ and $b$ are term symbols. Let $F_n$ ...
2
votes
1answer
93 views

The problem $K(x) \le K(y)$ is not decidable for Kolmogorov complexity $K$

Let $X$ be some finite alphabet. Given $(x,y) \in X^{\ast}\times X^{\ast}$, how to show that $K(x) \le K(y)$ is not decidable? I know that $K(x) \le k$ for some fixed $k$ is not decidable, so I tried ...
1
vote
0answers
97 views

Non-random movements

I know that the hedge fund Renaissance Technologies use computer-based models to predict price changes in financial instruments. These models are bases on analyzing as much data as can be gathered, ...
0
votes
1answer
2k views

Analysing a modification for Min-Cut Algorithm!

This exercise taken from the textbook "Randomized Algorithm" by Motwani and Raghavan. P.9, they give the following exercise to modify the min-cut algorithm: Exercise 1.2 Suppose that at each step ...
1
vote
0answers
55 views

Kolmogorov complexity measure of a formal system

Each formal system can be encoded in a binary string. For instance, you can use the input string that a pre-specified Turing machine needs in order to enumerate all the theorems in a theory in the ...
0
votes
1answer
481 views

Change in standard deviation when combining two sets of numbers

Say I have 2 Geiger counters that both generate a set of values (the counter measures background radiation). If I combine the two sets, how does the standard deviation of the new set compare to that ...
2
votes
1answer
134 views

“The digits used in artificial numbers are random while the real numbers aren't and their digits distribution is specific to their business”

Related to the question https://math.stackexchange.com/questions/1924178/tools-to-measure-the-nonrandomness-of-database, I'm somehow looking for some tools to measure the nonrandomness of databases. ...
3
votes
1answer
186 views

Are there strings with known Kolmogorov complexity?

I just looked into Kolmogorov complexity today and it appears to me that for a binary string of length $1$ (ex. '$0$') the Kolmogorov complexity must be $0$. It follows that Kolmogorov complexity ...
0
votes
2answers
314 views

Working with C++ for GF(2) [closed]

Pardon me if it is off topic.But, is there anyone who could suggest me some basics with how to get started with working with C++ for GF(2)?? I am new in C++.I am learning to working with arrays and ...
1
vote
1answer
96 views

Omega-model of WWKL consisting of random reals

I've been trying to show, as an exercise, that over $\mathrm{RCA_0}$ weak weak Kőnig's lemma (WWKL) does not imply weak Kőnig' lemma (WKL). I've been working on it by constructing an $\omega$-model ...
0
votes
1answer
97 views

PRNG for compression

I'm trying to intuitively grasp information theory. You have a string of size X that contains a lot of information, say it's a movie. You have a string of size N << X which is going to be the ...
1
vote
1answer
68 views

Expected number of jumps to just exceed $(1-\rho)$ quantile in the line segment $[0, 1]$

Suppose $X$ is random variable from some unknown distribution $f(X)$. I'm given a black-box/algorithm that takes a number $c\;: 0 \leq c < 1$ and outputs a number(randomly generated) using the ...
1
vote
0answers
79 views

question about isolation lemma.

Given the set $\mathcal{F}\in\mathcal{P}(\{1,...,m\})$, I need to provide it with probability $\frac{1}{2}$ a weight function $w:\{1,...,m\}\rightarrow\{1,...,n\}$ such that there will be a single ...
-2
votes
1answer
452 views

Prove that there exists a bipartite subgraph containing at least half of the edges in the original graph. [duplicate]

Prove that there exists a bipartite subgraph containing at least half of the edges in the original graph.
3
votes
1answer
187 views

Intuition on Martin-Löf-Test for finite strings

The followng example is from An Introduction to Kolmogorov Complexity and Its Applications, Example 2.4.1. and is concerned with Martin-Löf-Tests for finite strings: A string $x_1 x_2 \ldots x_n$ ...
1
vote
0answers
28 views

Calculation of arrival time of messages from 1 source through 2 different routes

I need to simulate sending messages from $A$ to $B$ as follows: Each message is sent $N$ times from $A$ on the same time, passes through a certain route $R_n$ and arrives at $B$. Travel time of $R_n$ ...
1
vote
1answer
128 views

Testing randomness

I'm looking for informations about randomness and especially - random numbers. I found some about random number generators, but for now, the question, that concerns me is how statistically differ ...
4
votes
4answers
662 views

Show the probability that the sum of these numbers is odd is 1/2

Setting Let $S$ be a set of integers where at least one of the integers is odd. Suppose we pick a random subset $T$ of $S$ by including each element of $S$ independently with probability $1/2$, Show ...
0
votes
1answer
133 views

Series of random numbers on a continuous function

At one point, I read about a function used to generate random numbers that follow a continuous pattern. By this I mean random numbers that as a series is random, but in which items tend to be ...
2
votes
1answer
194 views

Are there any Martin-Löf random reals that are computable?

For example, Chaitin's constant is both Martin-Löf random and uncomputable. Are there any examples of numbers that are Martin-Löf random but computable?