Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T13:29:20.742Z Has data issue: false hasContentIssue false
  • English
  • Français

Percolation and best-choice problem for powers of paths

Part of: Special processes Stochastic processes

Published online by Cambridge University Press:  22 June 2017

Fabricio Siqueira Benevides  and
Małgorzata Sulkowska
Fabricio Siqueira Benevides*
Affiliation:
Federal University of Ceará
Małgorzata Sulkowska*
Affiliation:
Wrocław University of Science and Technology
*
* Postal address: Department of Mathematics (Bloco 914), Federal University of Ceará, Av. Humberto Monte, s/n, 60.455-760, Fortaleza, Ceará, Brazil. Email address: [email protected]
** Postal address: Department of Computer Science, Faculty of Fundamental Problems of Technology, Wrocław University of Science and Technology, Grunwaldzki Sq. 13, 50-377 Wrocław, Poland. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The vertices of the kth power of a directed path with n vertices are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already appeared. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). We give upper and lower bounds for the asymptotic behaviour of pn,kn1/(k+1), where pn,k is the probability of success under the optimal algorithm. In order to derive the upper bound, we consider a model in which the selector obtains some extra information about the edges that have already appeared. We give the exact asymptotics of the probability of success under the optimal algorithm in this case. In order to derive the lower bound, we analyse a site percolation process on a sequence of the kth powers of a directed path with n vertices.

Keywords

Site percolationsecretary problemsequence of graphsgraph powerpath

MSC classification

Primary: 60G40: Stopping times; optimal stopping problems; gambling theory
Secondary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 54 , Issue 2 , June 2017 , pp. 343 - 362
Copyright
Copyright © Applied Probability Trust 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Artin, E. (1964). The Gamma Function. Holt, Rinehart and Winston, New York. Google Scholar
[2] Broadbent, S. R. and Hammersley, J. M. (1957). Percolation processes. I. Crystals and mazes. Phil. Camb. Phil. Soc. 53, 629–641. Google Scholar
[3] Feller, W. (1966). An Introduction to Probability Theory and Its Applications, Vol. II, John Wiley, New York. Google Scholar
[4] Ferguson, T. S. (1989). Who solved the secretary problem? Statist. Sci. 4, 282–296. Google Scholar
[5] Freij, R. and Wästlund, J. (2010). Partially ordered secretaries. Electron. Commun. Prob. 15, 504–507. Google Scholar
[6] Garrod, B. and Morris, R. (2013). The secretary problem on an unknown poset. Random Structures Algorithms 43, 429–451. Google Scholar
[7] Garrod, B., Kubicki, G. and Morayne, M. (2012). How to choose the best twins. SIAM J. Discrete Math. 26, 384–398. Google Scholar
[8] Georgiou, N., Kuchta, M., Morayne, M. and Niemiec, J. (2008). On a universal best choice algorithm for partially ordered sets. Random Structures Algorithms 32, 263–273. Google Scholar
[9] Gnedin, A. V. (1992). Multicriteria extensions of the best choice problem: sequential selection without linear order. In Strategies for Sequential Search and Selection in Real Time (Contemp. Math. 125; Amherst, MA, 1990), American Mathematical Society, Providence, RI, pp. 153–172. Google Scholar
[10] Goddard, W., Kubicka, E. M. and Kubicki, G. (2013). An efficient algorithm for stopping on a sink in a directed graph. Operat. Res. Lett. 41, 238–240. Google Scholar
[11] Grimmett, G. (1989). Percolation. Springer, New York. Google Scholar
[12] Grzesik, A., Morayne, M. and Sulkowska, M. (2015). From directed path to linear order—the best choice problem for powers of directed path. SIAM J. Discrete Math. 29, 500–513. Google Scholar
[13] Kaźmierczak, W. (2013). The best choice problem for a union of two linear orders with common maximum. Discrete Appl. Math. 161, 3090–3096. Google Scholar
[14] Kaźmierczak, W. (2016). The best choice problem for posets; colored complete binary trees. J. Combinatorial Optimization 31, 13–28. CrossRefGoogle Scholar
[15] Kaźmierczak, W. and Tkocz, J. (2017). The secretary problem for single branching symmetric trees. Preprint. Google Scholar
[16] Kozik, J. (2010). Dynamic threshold strategy for universal best choice problem. In 21st Internat. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (Discrete Math. Theoret. Comput. Sci. Proc. AM), Association of Discrete Mathematics and Theoretical Computer Science, Nancy, pp. 439–451. Google Scholar
[17] Kubicki, G. and Morayne, M. (2005). Graph-theoretic generalization of the secretary problem: the directed path case. SIAM J. Discrete Math. 19, 622–632. Google Scholar
[18] Kumar, R., Lattanzi, S., Vassilvitskii, S. and Vattani, A. (2011). Hiring a secretary from a poset. In Proc. 12th ACM Conf. on Electronic Commerce, ACM, New York, pp. 39–48. Google Scholar
[19] Lindley, D. V. (1961). Dynamic programming and decision theory. Appl. Statist. 10, 39–51. Google Scholar
[20] Morayne, M. (1998). Partial-order analogue of the secretary problem: the binary tree case. Discrete Math. 184, 165–181. CrossRefGoogle Scholar
[21] Preater, J. (1999). The best-choice problem for partially ordered objects. Operat. Res. Lett. 25, 187–190. Google Scholar
[22] Przykucki, M. (2012). Optimal stopping in a search for a vertex with full degree in a random graph. Discrete Appl. Math. 160, 339–343. Google Scholar
[23] Przykucki, M. and Sulkowska, M. (2010). Gusein-Zade problem for directed path. Discrete Optimization 7, 13–20. Google Scholar
[24] Stadje, W. (1980). Efficient stopping of a random series of partially ordered points. In Multiple Criteria Decision Making Theory and Application (Lecture Notes Econom. Math. Systems 177), Springer, Berlin, pp. 430–447. Google Scholar
[25] Sulkowska, M. (2012). The best choice problem for upward directed graphs. Discrete Optimization 9, 200–204. Google Scholar
[26] Tkocz, J. (2017). Best choice problem for almost linear orders. Preprint. Google Scholar