User pradipta - MathOverflow

Completion time of a process on a tree

2013-01-24T11:02:16Z

Given is a constant degree rooted tree of depth $D$. It is also known that the total number of nodes in the tree is at most $D^2$. There is a probabilistic process with discrete time steps on the nodes that work as follows:

A node becomes eligible to participate in the process when all of its children have succeded.
Once eligible, the node succeeds in each time step with iid probably $\frac12$. Once successful, it is "done", i.e. stays succeeded.

I would like a bound on how many steps it requires for all nodes to succeed with probability $1 - \delta$ where $\delta$ is potentially much smaller than $\frac1{D^2}$.

I can see a bound of $O((D + \log{\frac{1}{\delta}})\log D)$ as outlined below. I was wondering if the $\log D$ is necessary?

Outline of argument for $O((D + \log{\frac{1}{\delta}})\log D)$: Consider to be the number of steps required for the depth of tree of unsuccessful nodes to reduce by 1. Since there are at most $D^2$ leaves at any given time, the expected time for this reduction is $\log D$ steps. The situations for different depths are essentially independent (can be written as martingale), and then a concentration inequality would give us the required bound.

Minimum spanning tree of a random graph

2012-09-14T17:55:51Z

Consider $n$ points arbitrarily located on the plane. Consider a random graph $G$ drawn from $G(n, \frac12)$ on these points (i.e. the Erdos-Renyi random graph where every edge is selected with probability $\frac12$).

What is known about the geometry of the minimum spanning tree of such a graph? I am interested in pointers to any literature on this, but something like the following might be a concrete example:

Thm. With high probability, the Minimum Spanning Tree has weight within a factor of $\alpha$ of the MST on the complete graph on the same points.

Lower bound on sum of independent random variables

2012-01-27T17:44:40Z

Assume $0 < a_i \leq 1$ for $i = 1, 2 \ldots n$. I am interested in the random sum $X = \sum_i a_i X_i$ where $X_i$ are iid random Bernoulli variables with some mean $p \in (0, 0.5)$. I would like to know if one can relate $P(X \leq 1)$ to $P(X \leq \delta)$ for some $\delta < 1$. Specifically, what are the tightest bounds of the form

$$P(X \leq \delta) \geq f(\delta) P(X \leq 1)$$

for some function $f(\delta)$?

Coin flipping and a recurrence relation

2011-02-16T15:16:28Z

How can one solve the following recurrence relation?

$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$

$f(0) = 0$

As it happens, I can show $f(n) = \Theta(\log n)$ through other means (see below). But I'd like to know how to solve the recurrence "directly".

The recurrence relation comes from the following coin flipping problem. There are $n$ independent, unbiased coins, and we toss all of then for a number of rounds. Let $T(n)$ be the first round when each coin has got head at least once (ie, $T(n) = \text{arg} \min_t \text{s.t.} H_t(i) \geq 1; \forall i \in [n]$, where $H_t(i)$ is the number of heads the $i^{th}$ coin has got in the first $t$ rounds). Then one can see that $E(T(n))$ fulfills the recurrence relation mentioned above.

To see that $E(T(n)) = O(\log n)$, note that we reduce the number of coins who haven't gotten head yet by a factor of 2, in expectation. The $\log n$ bound follows routinely from that. On the other direction (ie, $E(T(n)) = \Omega(\log n)$), let $S = \log n/20$. Then at time $S$ with high probability, a large number of coins will still be "headless", from which the lower bound follows.

Comparing two Markov chains

2011-11-30T23:18:01Z

I thought that this question is more appropriate for math.stackexchange, where I asked it, but seeing how I got no response, here it goes:

I am interested in the question of the positive recurrence of a Markov chain that "converges" to another Markov chain known to be positive recurrent. The following is, in the context of queueing theory, a concrete example of what I mean.

Consider a system where a single server is serving two clients. Time is slotted. For client $i \in \{1, 2\}$, the number of packets arriving in each time step is a iid Bernoulli random variable with probability $p_i$.

Each client has queues of infinite capacity.

Assume $p_1 + p_2 < \frac{1}{8}$.

At each time slot, a client with non-empty queue may choose to submit one packet to the server for processing. This packet will be processed and leave the relevant queue if and only if the other client did not submit a packet in that time slot.

Now consider the following simple algorithm. Assume that client $i$ knows $p_i$. Then at each time slot, client $i$ (if its queue is non-empty) will submit a packet to the server with iid probability $2 p_i$. Let $j$ be the other client.

The probability of a packet submitted by client $i$ being processed is at least $1 - 2 \cdot p_j > \frac{3}{4}$. Thus, the probability of the size of a non-empty queue at client $i$ reducing by $1$ is at least $2 \cdot p_i \times \frac{3}{4} > p_i$. Since the departure process has a higher rate than the arrival process, it is clear that the corresponding Markov chain is positive recurrent and the queues are stable.

Here comes my question. Assume the clients do not know their own $p_i$'s. Naturally, they could approximate it as follows: at time $T$, the approximation $\hat p_i(T)$ is defined by $\hat{p_i}(T) = $$\min \left\{ 1, \frac{A(T)}{T} \right\}$, where $A(T)$ is the number of packets that have arrived up to time $T$. The clients can now use $\hat p_i(T)$ instead of $p_i$ in the above algorithm.

It seems to me that since $\hat p_i(T)$ converges almost surely to $p_i$, the resulting Markov chain will be positive recurrent too. But I am not sure this simply can be stated as true, and/or how to show that this holds.

Thanks.

Partitioning a matrix with bounded row sums

2010-12-15T14:30:50Z

Let $A$ be a $n \times n$ matrix with non-negative entries $a_{ij}$, where $a_{ij}$ is the entry in the $i^{th}$ row and $j^{th}$ column. Assume $\sum_{1 \leq j \leq n} a_{ij} \leq 1$ for all $1 \leq i \leq n$. Also assume $a_{ii} = 0$ for all $1 \leq i \leq n$.

I want to partition the index set $I = \{1, 2 \ldots n\}$ into minimum number of sets $I_1, I_2, \ldots I_t$ so that the column sum is bounded by $1$ in each sub-matrix defined by the sets, or more formally:

$\cup_{1 \leq k \leq t} I_k = I$
For all $1 \leq k \leq t$, $\sum_{i \in I_k}a_{ij} \leq 1$ for all $j \in I_k$
The number $t$ is minimized

I can construct examples where $t$ has to be at least $2$, on the other hand, $t = \Theta(\log n)$ would suffice for all such matrices. I am wondering if a tighter bound exists.

Motivation: this is a sort of generalization of the coloring problem in bounded out-degree digraphs. If a di-graph has out-degree upper bounded by $k$ it can be colored with $k + 1$ colors.

Maximum of a set of sums of iid random variables

2011-01-27T05:43:28Z

Consider some probability distribution $D$ over non-negative reals with finite expectation $\mu$. Now for any positive $T$ consider sums of $T$ iid random variables drawn from $D$. A single sum of this sort would be $S(T) = \sum_{i = 1}^T x_i$ where each $x_i$ is a iid random sample from $D$.

We will consider $n$ such sums $S_1(T), S_2(T) \ldots S_n(T)$.

My question: Is it true that for any distribution $D$ and any finite positive $n$, there exists a finite positive $T$ (which may be a function of $n$ and $D$) such that $E(\max_{1 \leq j \leq n}S_j(T)) \leq 2 T \mu$?

This is true for, say, Bernoulli random variables, but I'd like to know the mildest condition under which a statement like this can be made. For example, is it true for all distributions with finite $4^{th}$ moments?

Answer by Pradipta for Partitioning a matrix with bounded row sums

2010-12-16T15:58:01Z

Ok, I think there are examples where $\Omega(\log n)$ colors are needed.

Here’s an example, let $a_{ij} = \frac{1}{i}$ for $j < i$ and $a_{ij} = \frac{1}{j^2}$ for $j > i$. Then $\sum_{j} a_{ij} = \frac{i-1}{i} + \sum_{j > i} \frac{1}{j^2} = O(1)$. Of course, the bound is $O(1)$ instead of $1$, but that can be normalized and all that.

However, note that $\sum_j a_{j1} = \Omega(\log n)$ and if we only have $o(\log n)$ partitions, this sum cannot be "distributed" into small enough parts.

Stability of discrete queue (new twist)

2010-11-11T11:35:46Z

Hi, I am new to queueing theory. I am interested in a question that I feel should be fairly basic, yet I haven’t really found a clear solution to it. Hopefully somebody here can help me.

We have a single server system, with an infinite queue, and with slotted time. At the beginning of every slot, a number of jobs arrive in the queue. The number of jobs $X$ is a random variable over the non-negative integers, with expectation $\mu$. After these jobs arrive, the server processes some jobs, which leave the queue. The number of jobs the server can process is a Bernoulli random variable $C$. That is, $C = 1$ with some probability $p$, and $0$ otherwise. To state what is probably obvious, if $C = 1$, the queue size is reduced by $1$ (if the queue was non-empty), and the queue remains unchanged if $C= 0$ or if the queue was empty. Both $C$ and $X$ are iid across time.

I want to understand the conditions under which this system is stable. By stable, I mean $\sup_{n \geq 1} E(Q(n)) < M$ for some finite $M$, where $Q(n)$ is the size of the queue at the beginning of time slot $n$, and $E(Q(n))$ is the expectation of $Q(n)$. I am not necessarily interested in a explicit value of $M$, just knowledge that it is finite is fine. I am hoping that the condition would be $\mu < p$ or something like that.

I realize that probably some sort of assumption on the distribution on $X$ is needed, which is fine. Assumptions like finite variance, strong law of large numbers, or even large deviation inequalities are OK with me.

Edit: Additionally, I am interested in what would happen if $E(C)$ was not a fixed $p$ but $p(t)$ (ie, a function of time). Here $p(t)$ itself is a random variable where $E(p(t)) = p$ for all $t$, and $p(t)$ converges to $p$ almost surely. This question appears to be related to "time dependent Markov chains". However, the references for time dependent Markov chains that I could find do not consider $p(t)$ to be a random variable it self (such as http://portal.acm.org/citation.cfm?id=990738.990783). Asmussen’s book talks about time dependent properties of Markov chains, but that appears to be quite different.

Comment by Pradipta

2013-01-28T16:40:16Z

actually the tree cannot consist D disjoint paths of length D from the root since it is constant degree tree (assuming D is larger). I wonder if that improves the running time further.

Comment by Pradipta

2013-01-26T12:55:01Z

sounds perfect! let me just ruminate on this for a bit more, and I'll accept the answer. Thanks!

Comment by Pradipta

2012-09-16T03:29:52Z

Thanks for the pointers! They seem to be only slightly different models (randomly placed points etc), but I will definitely take a look.

Comment by Pradipta

2011-03-02T00:00:02Z

You’re right...I must have been not thinking.

Comment by Pradipta

2011-02-18T14:47:05Z

That’s great to know, Mike.

Comment by Pradipta

2011-02-17T16:50:42Z

Thanks. Great answer.

Comment by Pradipta

2011-02-17T16:02:36Z

Yes, I tried that. Didn't get anywhere.

Comment by Pradipta

2011-02-17T15:37:43Z

Very useful comment, Mike.

Comment by Pradipta

2011-02-16T16:28:18Z

Why does "quantum computation shatters complexity theory"? I thought, for example, that it wasn't known in quantum computation makes NP-hard problems easier.

Comment by Pradipta

2011-02-16T15:33:00Z

yeah. with probability $\frac{1}{2^n}$ no coin succeeds in round 1, thus you are back where you started.

Comment by Pradipta

2011-02-16T15:24:57Z

I think its working now.

Comment by Pradipta

2011-02-16T15:18:01Z

something's wrong. I'll fix this.

Comment by Pradipta

2011-02-10T00:36:00Z

Isn't this the recurrence relation for Bell Numbers?

Comment by Pradipta

2011-01-28T16:11:28Z

Very nice. I'm curious about the quantitative bound as well, as it appears to mean that $T$ polynomial in $n$ suffices, which is really great.

Comment by Pradipta

2011-01-27T21:03:57Z

Guys, many many thanks. I'll read through these detailed answers and then respond. Thanks again :)