Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algorithmic-randomness]

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

2
votes
1answer
69 views

If $k$ balls are thrown into $n$ bins, how many positions $i$ are there such that, bin $i$ and $ i+1$ are empty?

Assume the $k$ balls are thrown independently and uniformly at random, into $n$ labeled bins. What is the expected number of positions $i$ such that the bins labeled $i$ and $i+1$ are both empty?
1
vote
1answer
53 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
16 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
29 views

Generate a random bi-connected graph

I am trying to find an algorithm which will generate a random graph G, where G is a bi-connected graph too. An efficient algorithm is appreciated but I am looking for a brute force algorithm which ...
0
votes
0answers
42 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
26 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
37 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
39 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 ...
0
votes
0answers
19 views

Probabilistic bound on kth statistic of the array

I am attempting to derive the claim on page 10, asking to prove $P(k_1 \leq k \leq k_2) \geq \text{very large}$. I suspect that 'very large' might be $1 - n^{-\alpha}$. Where $k_1, k_2$ are elements ...
1
vote
2answers
42 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
29 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
0answers
16 views

How to determine the scale of a smoothing kernel?

In the Gaussian kernel, there is filter = new int[7, 7] { { 1, 1, 2, 2, 2, 1, 1 }, { 1, 3, 4, 5, 4, 3, 1 }, { 2, 4, 7, 8, 7, 4, 2 }, { 2, 5, 8, 10, 8, 5, 2 }, { 2, 4, 7, 8, 7, 4, 2 }, { 1, 31, 4, 5, 4,...
0
votes
1answer
44 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
24 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
56 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
28 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
78 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
66 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
164 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
62 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
0answers
55 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
57 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
980 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
48 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
357 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
123 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. ...
2
votes
1answer
145 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
234 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
85 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
73 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
67 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
259 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.
2
votes
1answer
144 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
27 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
119 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
570 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
106 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
159 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?
1
vote
1answer
77 views

Randomness of a linear congruential genarator in jumbling values of an array

I am working on a school project and it requires a simple pseudo-random number generating algorithm. I thought of using a linear congruential generator for this purpose. This came to my mind as it ...
0
votes
1answer
60 views

$Pi(n) = Pi(n-2) + x\times [Pi(n-1)]$ for all convergent numerators and denominators. True?

Where $x = A001203$, $Pi = A002486$, $A002485$ $Pi(n) = Pi(n-2) + x\times [Pi(n-1)]$ for all $Pi > n+1 $ Hypothesis: This relation evaluates true for all $A002486$ and $A002485$. Lemma: All "...
2
votes
1answer
974 views

Find Average number of updates needed to find maximum number in an array

While calculating the largest number in a given array of size n, you would need a variable like largestNumberSoFar. You will keep updating ...
2
votes
0answers
108 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
5
votes
3answers
3k views

Understanding Sobol sequences

Can someone explain to me in simple terms, how Sobol sequences work? The wikipedia article is fairly technical. They look pretty interesting. So I shall describe (whatever little I know) in short the ...
1
vote
1answer
81 views

Non-computable c.e. sets are Kurtz random

I'm trying to directly show that non-computable c.e. sets are Kurtz random, without using the concept of genericity, but to little success. I assume by way of contradiction that $\emptyset'$ (for ...
3
votes
1answer
104 views

Computably enumerable sets are not algorithmically random

I am informed that no computably enumerable sets are algorithmically random. I tried to show it by constructing an ML test, and looked up the proof in Downey & Hirschfeldt, but in vain. I would ...
3
votes
1answer
87 views

Construction of a Kurtz random sequence that's not Martin-Löf random

How can one construct a Kurtz random sequence that's not Martin-Löf random? I'm also interested in the paper that included the first of such constructions. I suspect it was in Kurtz's dissertation, ...
7
votes
3answers
379 views

Probability that a vertex in the spanning tree of an $N$ x $N$ grid graph is a leaf

Suppose we have an $N$ x $N$ grid graph $G(V,E)$ and we construct a spanning tree of this graph in the following way. Start with a set $S$ which contains only the vertex at the top left corner of the ...
1
vote
0answers
61 views

Kolmogorov complexity proof of Lovasz local lemma

Roughly speaking, Kolmogorv Complexity proof of lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, for ...