Es bien sabido que una caminata aleatoria en la cuadrícula bidimensional volverá al origen con probabilidad 1. También se sabe que la misma caminata aleatoria en TRES dimensiones tiene una probabilidad estrictamente menor que 1 de regresar al origen . Mi pregunta es: ¿Hay algo en el medio? Por...
Un importante artículo de 2003 de Childs et al.introdujo el "problema de los árboles combinados": un problema que admite una aceleración cuántica exponencial que es diferente a casi cualquier otro problema que conozcamos. En este problema, se nos da un gráfico exponencialmente grande como el que se...
El tiempo de conmutación en un gráfico conectado se define como el número esperado de pasos en una caminata aleatoria que comienza en , antes de que se visite el nodo y luego se vuelva a alcanzar el nodo . Básicamente es la suma de los dos tiempos de golpeo y .i j i H ( i , j ) H ( j , i )G = ( V,...
Estoy interesado en las propiedades de los gráficos dirigidos al azar con un grado externo fijoddd . Me estoy imaginando un modelo de gráfico aleatorio donde cada vértice elige d vecinos (digamos, con reemplazo) uar Pregunta : ¿Se sabe algo sobre la distribución estacionaria y los tiempos de...
Dada una caminata aleatoria en un gráfico, el tiempo de cobertura es la primera vez (número esperado de pasos) que cada vértice ha sido golpeado (cubierto) por la caminata. Para gráficos conectados no dirigidos, se sabe que el tiempo de cobertura está limitado por . Hay dígrafos fuertemente...
En el artículo Quantum Random Walks Hit Exponencialmente más rápido ( arXiv: quant-ph / 0205083 ) Kempe da una noción del tiempo de golpeo para caminatas cuánticas (en el hipercubo) que no es muy popular en la literatura de la caminata cuántica. Se define de la siguiente manera: One-Shot Quantum...
Versión rápida ¿Existen modelos de la decoherencia cuántica para la caminata en la línea de tal manera que podemos sintonizar el pie de propagación como para cualquier 1 / 2 ≤ k ≤ 1 ?Θ ( tk)Θ(tk)\Theta(t^k)1 / 2 ≤ k ≤ 11/2≤k≤11/2 \leq k \leq 1 Motivación Las caminatas aleatorias clásicas...
Deje ser un gráfico conectado no regular cuyo grado está acotado. Supongamos que cada nodo contiene un token único.G = ( V, E)G=(V,E)G= (V, E) ¿Quiero barajar uniformemente los tokens entre el gráfico usando solo intercambios locales (es decir, el intercambio de tokens entre dos nodos adyacentes)?...
Deje ser un gráfico simple no dirigido en n vértices ym bordes.G=(V,E)G=(V,E)G=(V,E)nnnmmm Estoy tratando de determinar el tiempo de ejecución esperado de algoritmo de Wilson para generar un árbol de expansión aleatoria de . Allí, se muestra que es O ( τ ) , donde τ es el tiempo medio de golpeo :...
Considere el siguiente problema. nnnv1,⋯,vn∈Rv1,⋯,vn∈Rv_1, \cdots, v_n \in \mathbb{R}S⊆{1,⋯,n}S⊆{1,⋯,n}S \subseteq \{1,\cdots,n\}maxi∈Svimaxi∈Svi\max_{i \in S} v_i Este problema es fácil: podemos usar la búsqueda binaria para encontrar el argmax con consultas O(logn)O(logn)O(\log n) . es...
Para un proyecto en el que estoy trabajando, debería generar árboles de expansión aleatorios con altura acotada. Básicamente hago lo siguiente: 1) Generar un árbol de expansión 2) Verificar la viabilidad, si es posible, mantenerlo. 1) Comenzando desde un árbol de expansión mínimo (Prim o...
(Mi pregunta original aún no ha sido respondida. He agregado más aclaraciones). Al analizar caminatas aleatorias (en gráficos no dirigidos) al ver la caminata aleatoria como una cadena de Markov, requerimos que el gráfico no sea bipartito para que se aplique el teorema fundamental de las cadenas...
Estoy buscando un teorema que diga algo como esto: si el tiempo de cobertura de una cadena de Markov reversible es pequeño, entonces la brecha espectral es grande. Aquí la brecha espectral significa, es decir, ignoramos el valor propio más pequeño de la cadena.1 - | λ2El |1-El |λ2El...
Existe un método trivial para simular una caminata aleatoria a través de un gráfico exponiendo una matriz de adyacencia estocástica, pero el problema se vuelve más difícil si solicita que la caminata aleatoria se evite por sí misma. En otras palabras, el proceso debe atravesar el gráfico utilizando...
Defina como un gráfico dirigido al azar ( vértices; colocamos el borde entre dos vértices con probabilidad ).n pG(n,p)G(n,p)G(n, p)nnnppp ¿Cuáles son los resultados conocidos para el siguiente problema? Fijar dos vértices vvv y uuu . ¿Cuál es la probabilidad de que haya al menos una ruta (de...