The pr.probability tag has no wiki summary.
5
votes
0answers
95 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
38 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
0answers
39 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 ...
14
votes
0answers
321 views
Does a noisy version of Conway's game of life support universal computation?
Quoting Wikipedia: It is known that 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 ...
4
votes
0answers
60 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 ...
5
votes
0answers
56 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
121 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 ...
2
votes
0answers
63 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
36 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
113 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
60 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 ...
11
votes
1answer
433 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 ...
4
votes
2answers
130 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
171 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 ...
23
votes
2answers
244 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 ...
-2
votes
1answer
62 views
By using which probability distribution is the optimal search tree a linear chain? [closed]
By using which probability distribution is the optimal search tree a linear chain?
Thanks for your help.
20
votes
2answers
505 views
Balls and Bins analysis in the $m \gg n$ regime: gaps
Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and ...
11
votes
4answers
406 views
Reverse Chernoff bound
Is there an reverse Chernoff bound which bounds that the tail probability is at least so much.
i.e if $X_1,X_2,\ldots,X_n$ are independent binomial random variables and $\mu=\mathbb{E}[\sum_{i=1}^n ...
3
votes
1answer
178 views
Coupon collector - the effect of randomization
Given a set $S = \{1, ..., n\}$, an element is randomly drawn with replacement from $S$. Let's say we got the following sequence $X = \{x _1, ..., x _k\}$ until all elements of $S$ are seen, where $x ...
3
votes
1answer
203 views
Estimator for sum of independent and identically distributed (iid) variables
This is a repost of a question at math.stackexchange, but I was told by a reliable source that people around here might be able to help me, so I thought I'd give it a shot.
Consider the Chernoff ...
1
vote
0answers
89 views
Distribution of number of unique items in a sample
Suppose we're sampling a discrete random variable from a distribution f, n times. Is there a simple analytical formulation for the expected number of unique items we obtain, or for the distribution of ...
7
votes
2answers
124 views
Guessing a low entropy value in multiple attempts
Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice ...
5
votes
1answer
205 views
Random walk returning probability
Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
21
votes
3answers
905 views
Number of distinct nodes in a random walk
Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically ...
1
vote
1answer
98 views
question about probability ranking principle
I am studying IR and
I am not clearly understand "probability ranking principle" ( I tried to google the definition, but i couldn't find clear answer.)
I am assuming that it's system which ...
7
votes
1answer
236 views
expected number of sets generated by greedy set cover ?
I see most of the analysis for the greedy set cover analyses the approximation ratio. However, assume that each element in $T$ belong with a constant probability to one of the sets of $S$ (where $S = ...
6
votes
0answers
136 views
Testing the degree of a vertex
Let's say we have a graph $G$ with $n$ vertices. Given $\epsilon>0$ and a specific vertex $v$, consider the problem of deciding whether $\mathrm{deg}(v) < \frac{\epsilon}{3}n$ or ...
8
votes
2answers
423 views
High probability events without low probability coordinates
Let $X$ be a random variable taking values in $\Sigma^n$ (for some large alphabet $\Sigma$), which has very high entropy - say, $H(X) \ge (n- \delta)\cdot\log|\Sigma|$ for an arbitrarily small ...
3
votes
0answers
115 views
Tree search guided by a probabilistic oracle
I'm trying to find a solution for the following problem.
I have a tree $T$ of branching factor $b$ and depth $d$. For the moment, I only care about the case where I restrict $b=2$, but I would be ...
9
votes
0answers
281 views
Sampling from Multivariate Gaussian with Graph Laplacian (inverse) Covariance
We know from e.g. Koutis-Miller-Peng (based on work of Spielman & Teng), that we can very quickly solve linear systems $A x = b$ for matrices $A$ that are the graph Laplacian matrix for some ...
10
votes
0answers
170 views
Cheeger's inequality for directed graphs?
Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
1
vote
0answers
198 views
application for the Kchinchine inequality in Computer Science
The classical Kchinchine inequality states that for vector $a=(a_1, \ldots, a_{2m})\in R^{2m}$, for $p\geq 2$, and for independent Rademacher random variables $r_1, \ldots, r_{2m}$, one has
$$
...
12
votes
2answers
210 views
What's the bias of random polynomials with low degree over GF(2)?
I have a question concerning low-degree polynomials and probability:
What is the (assyptotic behavior of the) probability that a
random* polynomial, $p$, over GF(2), with degree $\le d$ and n ...
-3
votes
2answers
107 views
Any program function or something to compute the integral of normal distribution? [closed]
Let the normal pdf defined as: $P(x, \bar{x}, \sigma) = \exp\left(\frac{-(x-\bar{x})^2}{2\sigma^2}\right) / (\sigma \sqrt{2\pi})$. In my program I need ti use $P(x>n)$, but I don't know how to find ...
6
votes
0answers
157 views
Cover time and spectral gap for reversible random walks
I am looking for a theorem which say something like this: if the cover time of a reversible Markov chain is small, then the spectral gap is large. Here the spectral gap means $1-|\lambda_2|$, that is, ...
4
votes
0answers
89 views
Problem about machine scheduling [closed]
I am re-posting the problem http://mathoverflow.net/questions/92783/random-task-scheduling-problem here because I think people here are more familiar with this topic.
Assume there are $m$ tasks, each ...
6
votes
1answer
535 views
Throwing Balls into Bins, estimate a lowerbound of its probability
This is not a homework, though it looks like. Any reference is welcome. :-)
Scenario: There are $n$ different balls and $n$ different bins (labled from 1 to $n$, from left to right). Each ball is ...
2
votes
1answer
155 views
Generate random permutation via iid uniforms — is inverse transformation possible?
A very common technique in the analysis of algorithms involving random permutations is to have each element $x$ select a rank $\rho(x)$ uniformly at random from the real interval $[0,1]$. The ...
-1
votes
1answer
80 views
Issue in understanding conditional likelihood for a producton rule
The Equation1 in paper in link explains how to assign probability to a production rule. Fig1 explains with an example. Now, I have a problem in understanding how to work with this formula since it ...
-2
votes
1answer
114 views
Dual of a Reversible Markov Chain [closed]
Let a reversible Markov process $m_{t+1}=m_t P$, where $t$ is time that has a stationary distribution $\pi$. I saw in a paper that the dual system was defined as $x_{t+1}=P x_t$. Can anyone give me ...
9
votes
5answers
318 views
Computing the approximate population of a bloom filter
Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.
Is it possible to approximate the number of elements inserted into the bloom filter?
...
0
votes
1answer
241 views
is it by Chebychev's inequality? [closed]
Let x be random variables with mean zero and variance 1.
Let n be natural number, t>0, C>0.
Let also $P(x^2\geq n)\geq C/(n^t)$.
Show, if $t\geq4$, then $P(x^2\geq n)\leq C/(n^2)$.
I got so fare, ...
7
votes
2answers
551 views
Order of drawing colored balls from a bag
We're looking for an upper bound on (or a method to compute) probabilities of the following type: Suppose I put 12 yellow balls, 18 red balls, 7 white balls, and 2 green balls in a bag. Then I start ...
9
votes
3answers
461 views
Technical question about random walks
(My original question still has not been answered. I have added further clarifications.)
When analyzing random walks (on undirected graphs) by viewing the random walk as a Markov chain, we require ...
10
votes
0answers
308 views
Is Bayesian updating computationally unfeasible?
Bayesian theory is a very popular theory of probabilities based upon a subjective framework of beliefs. However, subjects and beliefs have to be embodied, meaning to be feasible, it ought to be ...
5
votes
4answers
303 views
Small $\epsilon$-nets for points and half-planes without VC dimension
I have recently learned the proof of Haussler and Welzl of the following theorem.
Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ ...
2
votes
1answer
373 views
Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime
i have some question concerning the class PP and PPT machines.
1) PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability ...
4
votes
3answers
320 views
Computational complexity of random sampling
I am using some randomized algorithms (particle filters) and I would like to know what is the computational complexity of obtaining one random sample of a continuous distribution (for instance from a ...
25
votes
2answers
663 views
Drunken birds vs drunken ants: random walks between two and three dimensions
It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly ...
4
votes
2answers
788 views
Multiplication of normal distributions
Suppose X_1, ..., X_k are iid standard Gaussian variables, for some k > 1.
Then, what is the distribution of X := X_1 * ... * X_k ? Can it be approximated by a Gaussian, maybe for large k ?
