Tagged Questions

Questions in probability theory

learn more… | top users | synonyms

1
vote
0answers
84 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and ...
6
votes
0answers
68 views

What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
13
votes
2answers
269 views

What is the expected depth of a randomly generated tree?

I thought about this problem a long time ago, but have no ideas about it. The generating algorithm is as follows. We assume there are $n$ discrete nodes numbered from $0$ to $n - 1$. Then for each ...
0
votes
1answer
47 views

References to learn more about graph laplacian.

I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces. Can someone give a pedagogic reference which ...
5
votes
0answers
97 views

Spectrum of absorbing random walk for regular graphs

I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as ...
3
votes
0answers
71 views

Probability distributions and computational complexity

Some probability distributions are easier to work with than others. Consider the following two problems. Given a number $n$, return $i$ with $0 \leq i < n$ with uniform probability, i.e. ...
0
votes
1answer
166 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
1
vote
1answer
47 views

Subspace-evasive set performance in the random case

A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough ...
7
votes
2answers
223 views

Maximizing the number of heads in $N$ tosses by choosing which coin to toss

Assume you have two coins $A,B$ with biases $P_A,P_B$ respectively. We would like to make $N$ coin tosses and get the maximal number of heads possible. Unfortunately, we know $P_B$, but $P_A$ is ...
21
votes
1answer
542 views

A flowchart for concentration bounds

When I teach tail bounds, I use the usual progression: If your r.v is positive, you can apply Markov's inequality If you have independence and also bounded variance, you can apply Chebyshev's ...
0
votes
1answer
135 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits will ...
0
votes
2answers
129 views

Determining the distribution of results of a simple algorithm

Setting Consider repeating the following process on the numbers $N=\{1, 2, 3, \ldots, n\}$: Pick an integer $k \in N$, uniformly at random. Pick a subset of $k$ elements from $N$, uniformly at ...
2
votes
1answer
67 views

Sufficient Statistics of $X$ from $Y$

I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they ...
4
votes
1answer
60 views

Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

I'd like to have proof that Chaitin's constant for lambda calculus and/or SKI combinatory logic is pretty small. I've found some approximations (accurate to about 63 binary digits) for truing machines ...
1
vote
0answers
86 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
1
vote
0answers
29 views

randomness extraction of real valued sequences of numbers

I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence. My first thought was to use the Von Neumann extractor. For a ...
1
vote
1answer
51 views

Policy Adjustment in Markov Decision Process

I was using MDP on my work to make optimal decision. I used discrete time, finite state MDP. I assumed that I will have an initial parameters, like the Reward/Cost, state transition probabilities and ...
6
votes
2answers
409 views

What is the probability of a virus spreading through a network given a virus source node?

Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. ...
1
vote
0answers
174 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
2
votes
0answers
111 views

How to find a merge tree for a set of words?

Consider a set $S \subseteq \Sigma^n$ where $\Sigma$ is a finite alphabet and $p : \Sigma \rightarrow [0,1]$ is a probability function. Let $T$ be a tree leaf-labeled by the elements of $S$. Consider ...
8
votes
1answer
84 views

$k$-wise independent probability spaces

I have been having a great deal of difficulty finding a reference that gives simple and straightforward explanation of the following: Suppose we have $n$ random variables $Y_1, \dots, Y_n$, each of ...
2
votes
0answers
60 views

Convergence of iterated stochastic matrices

(This question has been unsuccessfully asked on mathoverflow: http://mathoverflow.net/questions/161728/convergence-of-iterated-stochastic-matrices) It is well-known that for a stochastic aperiodic ...
5
votes
2answers
187 views

Subgraph of G whose maximum degree and minimum degree are of the same order

Consider a graph $G$ with max degree $\Delta_G$, min degree $\delta_G$ and average degree $d_G$. Is it possible to obtain a subgraph of $G$, say $G'$, such that $\Delta_{G'} = c_1d_{G}$, ...
6
votes
0answers
63 views

Fast convergence of a contagion process in special graphs

The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira): Define an indicator variable ...
6
votes
1answer
118 views

Independent set size in triangle-free graphs

Consider a triangle-free graph $G$. The notations used are: $\alpha(G) = $ the size of a largest independent set of $G$. $n(G) = $ the number of vertices in $G$. Theorem (Ajtai et al.): For a ...
1
vote
0answers
32 views

What is entropy of a variable described by Knightian uncertainty?

Given a discrete variable whose value is characterized by Knightian uncertainty, that is, belief and plausibility, as in Dempster-Shafer theory, what is its entropy?
3
votes
3answers
268 views

The use of crossovers in Genetic Algorithm

My questions concern the use of crossovers in genetic algorithms. The three basic ingredients of genetic algorithms are: selection mutation crossover If we think of genetic algorithm acting on ...
0
votes
1answer
66 views

Multiple independent random number streams

Having multiple streams of pseudo-random numbers known to be independent and with a uniform distribution I want to do Monte Carlo simulations in parallel. In other words, one thread will have a ...
5
votes
2answers
127 views

Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, ...
-3
votes
1answer
61 views

Why is the zero value ignored while deriving a ranking function for query terms in Probabilistic IR?

Take for instance equation 67 and 68 from this chapter: the value of $P(q|R=1,q)$ can become zero if the term is not present in the document, and as all probabilities are multiplied, the ...
1
vote
1answer
44 views

A theorem regarding statistically-hiding commitment schemes

Let $C_n$ be a non-interactive statistically-hiding commitment scheme, able to commit to an $n$-bit string. To commit to $m \in \{0,1\}^n$, the sender picks a random $r$ (of proper length), and sends ...
5
votes
2answers
179 views

Probability for an element to appear in at least one set

Say that we have $k$ sets, each with cardinality $N$, where the elements in each set are taken at random from $M \ge N$ possible ones. The elements in each set are known to be distinct. What is the ...
6
votes
1answer
177 views

correlation in an almost independent set of random variables

Suppose I have a set of $n$ binary random variables $X_1, \ldots, X_n$ that sit on a line, and assume that $\Pr(X_i=0)=\delta$ for all $i$. In addition, assume that any two subsets of variables that ...
4
votes
0answers
128 views

Sums of products of bernoulli random variables

Let $x_1 \ldots x_a,y_1 \ldots y_b$ be independent random variables taking values +1 or -1. Consider the sum $$S = \sum_{i,j} x_iy_j.$$ I wish to upper bound the probability $P(|S| > t)$. The ...
7
votes
1answer
559 views

Sum of Independent Exponential Random Variables

Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - ...
5
votes
0answers
121 views

Squares of random binary matrices

Are there results/techniques pertaining to the analysis of squares of random matrices ? More specifically, let $A$ be an $n\times n$ matrix such that each entry is $1$ or $-1$ independently and with ...
1
vote
1answer
61 views

Terminology for games with incomplete information and no prior beliefs

Can anyone please tell me what is the term used for games with incomplete information and there are no prior beliefs about other players' private information. For example, let $ v_i(a_i,\theta_i) $ ...
0
votes
1answer
116 views

Capacity planning algorithm resources

Let's say I have a machine with many boxes of different sizes. I want to put packages inside those boxes. Packages arrive at different time and then stay in the box for specific period of time. I need ...
26
votes
4answers
2k views

Does a noisy version of Conway's game of life support universal computation?

Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life." Do such ...
4
votes
0answers
122 views

The balls and bins model: bounding the marginal contributions in the m>>n regime

Consider the standard balls and bins process, where $m$ balls are thrown into $n$ bins, and consider the case where $m >> n$. Denote the load on bin $i$ by the RV $L_i$. Given a set $S ...
7
votes
0answers
112 views

Convergence speed in Lévy’s continuity theorem

I suppose the answer to my question follows from the proof of the Lévy’s continuity theorem, but probably one could suggest me a direct reference to the corresponding answer. The question is as ...
7
votes
1answer
140 views

Looking for a reference: equivalence of (semi)computable (semi)measures and PTMs

I'm working with computable probability distributions over all finite strings. These are usually formalized as the space of all semicomputable semimeasures. Informally: a probability distribution is ...
3
votes
0answers
93 views

Concentration Bounds for Dependent Rounding

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
2
votes
0answers
51 views

Set-systems with some version of independence

Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = ...
1
vote
2answers
211 views

Chernoff Bounds for settings with limited dependence

Could someone point me to a way of bounding the tail probability of sums of bernoulli variables each generated by the same distribution but the condition of independence is only partially satisfied. ...
3
votes
0answers
69 views

A sampling and learning question

Suppose there is an oracle that returns a number $b \in \mathbb{Z}_{n}$ whenever I press the button. We have $b = a + e$, where $a \in \mathbb{Z}_n$ is a fixed number and $e$ is sampled according to ...
16
votes
1answer
678 views

The complexity of sampling (approximately) the Fourier transform of a Boolean function

One thing that quantum computers can do (possibly even with just BPP + log-depth quantum circuits) is to approximate-sample the Fourier transform of a Boolean $\pm 1$-valued function in P. Here and ...
5
votes
2answers
149 views

Behaviour of Labelled Markov Processes

Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of ...
3
votes
1answer
181 views

Boundedness of expected reward Markov chain

This is a repost of a question I asked on math.SE. The problem: I have an infinite Markov chain $M$ over the natural numbers, with transition probabilities $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose ...
25
votes
2answers
320 views

Current tightest bounds for critical 3-SAT density

I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or ...